在邻接表存储结构上实现图的基本操作,画出图的邻接表存储结构

　　00-1010一、点睛之笔1。无向图2。无向图的链表3。描述4。无向图2。邻接表1的数据结构。节点2。伴随点3。算法步骤4。实施5。测试。

　　00-1010邻接表是图的链式存储方法，其数据结构包括节点和邻接两部分。

　　邻接表可以用来表示无向图、有向图和网络。这里用无向图来说明。

目录

一、点睛

　　00-1010节点A的邻点是节点B和D，邻点的存储下标是1和3。按照头插入法(逆序)把它们放在节点A后面的单链表中。

　　节点B的相邻点是节点A、C、D，它们的存储下标是0、2和3。按照头插入法(逆序)，放入node B后面的单链表中。

　　节点C的邻点是节点B和D，邻点的存储下标是1和3，按照头插入法(逆序)放入节点C后面的单链表中。

　　节点D的相邻点是节点A、B和C，它们的存储下标是0、1和2。按照头插入法(逆序)，放入node D后面的单链表中。

　　00-1010邻接表的特点如下：如果无向图中有n个节点和e条边，则节点表中有n个节点，相邻节点表中有2e个节点。

　　一个节点的度是该节点后面的单链表中节点的个数。

1.无向图

　　00-1010包括节点信息数据和首先指向第一个相邻点的指针。

　　00-1010包括存储的相邻点的下标V和指向下一个相邻点的指针next。如果是网络的邻点，需要添加一个权重字段W，如下图所示。

　　00-1010 1输入节点和边的数量。

　　2依次输入节点信息，存储在节点数组Vex[]的数据字段中，Vex[]第一个字段为空。

　　3依次输入连接到每条边的两个节点。如果是网络，还需要输入边的权重。

　　如果是无向图，输入ab，查询节点A和B将下标I和J存储在节点数组Vex[]中，新建一个相邻点S，使S . v=J；s.next=null然后在第I个节点的第一个相邻点之前插入节点S(头插入法)。在无向图中，从节点A到节点B有边，从节点B到节点A也有边，因此需要创建一个新的邻点s2，使S2 . v=I；s2.next=null然后让s2节点插在第j个节点的第一个邻点之前(头插入法)。

　　如果是无向图，输入ab，查询节点A和B将下标I和J存储在节点数组Vex[]中，新建一个相邻点S，使S . v=J；s.next=null然后在第I个节点的第一个相邻点之前插入节点S(头插入法)。

　　如果是无向图或有向图，除了相邻节点多一个权域外，处理方式和无向图或有向图一样。

2.无向图的链接表

包装图；导入Java . util . scanner；公共类create algraph { static final int MaxVnum=100；//最大顶点数是public static void main(string[]args){ algorithm g=new algorithm()；for(int I=0；即凸面长度；I){ G . Vex[I]=new Vex node()；} create algraph(G)；//创建有向图邻接表printg(G)；//输出邻接表}静态int locate vex (graph g，char x){ for(int I=0；维克斯纳姆；I) //找到下标if (x==G.Vex[i]。data)返回顶点信息的I；return-1；//未找到}//插入一条边静态空插入边(Algraph G，int I，int J) {adj nodes 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邻接表存储图的资料请关注盛行IT其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。