Java用邻接表存储图的示例代码

目录
  • 一、点睛
    • 1.无向图
    • 2.无向图的链接表
    • 3.说明
    • 4.无向图
  • 二、邻接表的数据结构
    • 1.节点
    • 2.邻接点
  • 三、算法步骤
  • 四、实现
  • 五、测试

一、点睛

邻接表是图的一种链式存储方法,其数据结构包括两部分:节点和邻接点。

用邻接表可以表示无向图,有向图和网。在此用无向图进行说明。

1.无向图

2.无向图的链接表

3.说明

节点 a 的邻接点是节点 b、d,其邻接点的存储下标为1、3,按照头插法(逆序)将其放入节点 a 后面的单链表中。

节点 b 的邻接点是节点 a、c、d,其邻接点的存储下标为0、2、3,按照头插法(逆序)将其放入节点 b 后面的单链表中。

节点 c 的邻接点是节点 b、d,其邻接点的存储下标为1、3,按照头插法(逆序)将其放入节点 c 后面的单链表中。

节点 d 的邻接点是节点 a、b、c,其邻接点的存储下标为0、1、2,按照头插法(逆序)将其放入节点 d 后面的单链表中。

4.无向图

邻接表的特点如下 如果无向图中有 n 个节点、e 条边,则节点表中有 n 个节点,邻节点表有 2e 个节点。

节点的度为该节点后面单链表中的节点数。

二、邻接表的数据结构

1.节点

包括节点信息 data 和指向第 1 个邻接点的指针 first。

2.邻接点

包括该邻接点的存储下标 v 和指向下一个邻接点的指针 next,如果是网的邻接点,则还需增加一个权值域 w,如下图所示。

三、算法步骤

1 输入节点数和边数。

2 依次输入节点信息,将其存储到节点数组 Vex[] 的 data 域中,将 Vex[] first 域置空。

3 依次输入每条边依附的两个节点,如果是网,则还需要输入该边的权值。

如果是无向图,则输入 a b,查询节点 a、b 在节点数组 Vex[] 中存储下标 i、j,创建一个新的邻接点 s,让 s.v = j;s.next=null;然后将节点 s 插入第 i 个节点的第 1 个邻接点之前(头插法)。在无向图中,从节点 a 到节点 b 有边,从节点 b 到节点 a 也有边,因此还需要创建一个新的邻接点 s2,让 s2.v = i;s2.next=null;然后让 s2 节点插入第 j 个节点的第 1 个邻接点之前(头插法)。

如果是无向图,则输入 a b,查询节点 a、b 在节点数组 Vex[] 中存储下标 i、j,创建一个新的邻接点 s,让 s.v = j;s.next=null;然后将节点 s 插入第 i 个节点的第 1 个邻接点之前(头插法)。

如果是无向网或有向网,则和无向图或有向图的处理方式一样,只是邻节点多了一个权值域。

四、实现

package graph;

import java.util.Scanner;

public class CreateALGraph {
    static final int MaxVnum = 100;  // 顶点数最大值

    public static void main(String[] args) {
        ALGraph G = new ALGraph();
        for (int i = 0; i < G.Vex.length; i++) {
            G.Vex[i] = new VexNode();
        }
        CreateALGraph(G); // 创建有向图邻接表
        printg(G); // 输出邻接表
    }

    static int locatevex(ALGraph G, char x) {
        for (int i = 0; i < G.vexnum; i++) // 查找顶点信息的下标
            if (x == G.Vex[i].data)
                return i;
        return -1; // 没找到
    }

    // 插入一条边
    static void insertedge(ALGraph G, int i, int j) {
        AdjNode s = new AdjNode();
        s.v = j;
        s.next = G.Vex[i].first;
        G.Vex[i].first = s;
    }

    // 输出邻接表
    static void printg(ALGraph G) {
        System.out.println("----------邻接表如下:----------");

        for (int i = 0; i < G.vexnum; i++) {
            AdjNode t = G.Vex[i].first;
            System.out.print(G.Vex[i].data + ":  ");
            while (t != null) {
                System.out.print("[" + t.v + "]\t");
                t = t.next;
            }
            System.out.println();
        }
    }

    // 创建有向图邻接表
    static void CreateALGraph(ALGraph G) {
        int i, j;
        char u, v;

        System.out.println("请输入顶点数和边数:");
        Scanner scanner = new Scanner(System.in);
        G.vexnum = scanner.nextInt();
        G.edgenum = scanner.nextInt();
        System.out.println("请输入顶点信息:");

        for (i = 0; i < G.vexnum; i++)//输入顶点信息,存入顶点信息数组
            G.Vex[i].data = scanner.next().charAt(0);
        for (i = 0; i < G.vexnum; i++)
            G.Vex[i].first = null;
        System.out.println("请依次输入每条边的两个顶点u,v");

        while (G.edgenum-- > 0) {
            u = scanner.next().charAt(0);
            v = scanner.next().charAt(0);
            i = locatevex(G, u); // 查找顶点 u 的存储下标
            j = locatevex(G, v); // 查找顶点 v 的存储下标
            if (i != -1 && j != -1)
                insertedge(G, i, j);
            else {
                System.out.println("输入顶点信息错!请重新输入!");
                G.edgenum++; // 本次输入不算
            }
        }
    }
}

// 定义邻接点类型
class AdjNode {
    int v; // 邻接点下标
    AdjNode next; // 指向下一个邻接点
}

// 定义顶点类型
class VexNode {
    char data; // VexType为顶点的数据类型,根据需要定义
    AdjNode first; // 指向第一个邻接点
}

// 定义邻接表类型
class ALGraph {
    VexNode Vex[] = new VexNode[CreateALGraph.MaxVnum];
    int vexnum; // 顶点数
    int edgenum; // 边数
}

五、测试

白色为输出,绿色为输入

以上就是Java用邻接表存储图的示例代码的详细内容,更多关于Java邻接表存储图的资料请关注我们其它相关文章!

(0)

相关推荐

  • java实现图的邻接表存储结构的两种方式及实例应用详解

    前言 本篇来谈一谈图的邻接表实现的两种方式,首先我们明确一点"学会图的邻接表实现的关键点在于":你所建立的图的邻接表的对象是什么! 首先我们看一下<算法导论>中关于图的邻接表的定义: 图G=(V,E)的邻接表表示有一个包含 |V| 个列表的数组Adj所组成,其中每个列表对应于V中的一个顶点,对于每一个u∈V,邻接表Adj[u]包含所有满足条件(u,v)∈E的顶点v,亦即,Adj[u]包含图G中所有和顶点u相邻的顶点.(或者他也可能指向这些顶点的指针),每个邻接表中的顶点一般

  • 邻接表无向图的Java语言实现完整源码

    邻接表无向图的介绍 邻接表无向图是指通过邻接表表示的无向图. 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边. 上图右边的矩阵是G1在内存中的邻接表示意图.每一个顶点都包含一条链表,该链表记录了"该顶点的邻接点的序号".例如,第2个顶点(顶点C)包含的链表所包含的节点的数据分别是"0,1,3":而这"

  • Java用邻接表存储图的示例代码

    目录 一.点睛 1.无向图 2.无向图的链接表 3.说明 4.无向图 二.邻接表的数据结构 1.节点 2.邻接点 三.算法步骤 四.实现 五.测试 一.点睛 邻接表是图的一种链式存储方法,其数据结构包括两部分:节点和邻接点. 用邻接表可以表示无向图,有向图和网.在此用无向图进行说明. 1.无向图 2.无向图的链接表 3.说明 节点 a 的邻接点是节点 b.d,其邻接点的存储下标为1.3,按照头插法(逆序)将其放入节点 a 后面的单链表中. 节点 b 的邻接点是节点 a.c.d,其邻接点的存储下标

  • Java用邻接矩阵存储图的示例代码

    目录 一.点睛 1.无向图的邻接矩阵 2.有向图的邻接矩阵 3.网的邻接矩阵 二.算法步骤 三.实现 四.测试 一.点睛 邻接矩阵通常采用一个一维数组存储图中节点的信息,采用一个二维数组存储图中节点之间的邻接关系. 邻接矩阵可以用来表示无向图.有向图和网. 1.无向图的邻接矩阵 在无向图中,若从节点 Vi 到节点 Vj 有边,则邻接矩阵 M[i][j] = M[j][i ]= 1,否则 M[i][j] = 0. 无向图的邻接矩阵的特定如下. a 无向图的邻接矩阵是对称矩阵,并且是唯一的. b 第

  • Java中树的存储结构实现示例代码

    一.树 树与线性表.栈.队列等线性结构不同,树是一种非线性结构. 一棵树只有一个根节点,如果一棵树有了多个根节点,那它已经不再是一棵树了,而是多棵树的集合,也被称为森林. 二.树的父节点表示法 树中除根节点之外每个节点都有一个父节点,为了记录树中节点与节点之间的父子关系,可以为每个节点增加一个parent域,用以记录该节点的父节点. package com.ietree.basic.datastructure.tree; import java.util.ArrayList; import ja

  • 图的邻接表存储表示示例讲解

    复制代码 代码如下: //---------图的邻接表存储表示------- #include<stdio.h>#include<stdlib.h> #define MAX_VERTEXT_NUM 20 typedef int InfoType;typedef char VertextType; typedef struct ArcNode{    int adjvex;    struct ArcNode *nextArc;    InfoType *info;}ArcNode;

  • C++实现图的邻接表存储和广度优先遍历实例分析

    本文实例讲述了C++实现图的邻接表存储和广度优先遍历方法.分享给大家供大家参考.具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 0 2 0 3 2 3 2 4 1 4 输入结束(此行不必输入) 注:0 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示       0 2表示该图的第0个顶点和第2个定点有边相连,如上图中的a->c所示       2 3表示该图的

  • golang MySQL实现对数据库表存储获取操作示例

    目录 新建数据库 config.go gameblog.go http Simplify server.go comment.go gameblog.go server.go postman test api Axios gamelist.go HTTP gamelist.go server.go Axios 新建数据库 将部分数据存储至Mysql,使用axios通过golang搭建的http服务器获取数据. sql DROP DATABASE VUE; create database if n

  • Java 重命名 Excel 工作表并设置工作表标签颜色的示例代码

    通常在一份Excel文档中可能包含多个内容不同的工作表,而他们的默认名都为Sheet1.Sheet2.Sheet3等.为了方便我们的查找和操作,我们可以将这些工作表重新命名并设置不同的工作表标签颜色.本文就将介绍如何借助Free Spire.XLS for Java来完成这些操作. 产品导入: 1. 下载Free Spire.XLS for Java包并解压缩,然后将lib文件夹下的Spire.Xls.jar包作为依赖项导入到Java应用程序中. 2. 直接通过Maven仓库安装JAR包,按如下

  • C语言邻接表建立图详解

    目录 有向图 无向图 邻接表存图进行拓扑排序 总结 有向图 代码: #include<stdio.h> #include<stdlib.h> #include<string.h> #include<stack> using namespace std; #define maxn 200 int v, e; //表结点 typedef struct _Enode { int ivex; //该边所指向的节点位置 int value;//如果边有权值的话,就对其

  • 基于Java实现QQ登录注册功能的示例代码

    目录 前言 实现代码 登录页面 注册页面 效果展示 前言 本文主要应用的技术有:GUI.JDBC.多线程 实现的功能具体如下: 1.登录功能 2.注册功能 3.是否隐藏密码的选择以及实现功能 4.选择性别功能 5.密码与确认密码功能 6.登录页面实时展示当前的时间 7.当登录时用户名与密码在数据库中没有相匹配的数据,则会跳转到注册页面上去. 8.同样,注册完毕后,数据会运用JDBC将数据写入数据库中,然后跳转回登录页面. 实现代码 登录页面 import javax.swing.*; impor

随机推荐