大家好，欢迎来到IT知识分享网。
邻接表
基本概念
当图比较稀疏并且用邻接矩阵表示时，邻接矩阵的利用率太低，造成一定的资源浪费。邻接表就是为了节省图的存储空间而提出来的一种链式存储结构。该链式结构中，为图中的每一个顶点Vertex建立一个单链表。在该单链表中，各个结点由3个链域组成：adjvex邻接点、指向下一个边的nextarc和该边对应的信息info。如下图所示：
另外，为了表示图中的所有的顶点，邻接表结构中采用了一个结构体数组AdjList[num]。数组元素是一个有两个链域（顶点信息和该顶点的对应的第一条弧）的结构体。其具体如下所示：
当用邻接表表示上图时，如下图所示：
从上图可以看出，单链表1 表示与第一个顶点v1相连的3条弧，其中链表中的各个结点中的第一个链域表示与该结点相邻接的其他顶点在顶点数组中的位置。与第一个顶点v1相连的分别是顶点2，顶点3和顶点4，因此该链表中的三个结点的第一个链域分别为3，2和1。其他依次类推。另外，需要注意的是，邻接表表示有向图和无向图的一些区别。
基本操作
1、构造图的邻接表
Status createGraph(ALGraph &G, string kind, int vertexNum, int arcNum){ //采用邻接表构造图（有向或无向图） G.kind = kind; G.vertexNum = vertexNum; G.arcNum = arcNum; //初始化顶点信息 for(int i = 0; i<G.vertexNum; i++){ cin>>G.vertices[i].data; G.vertices[i].firstArc = NULL; } cout<<"Try to input arcs info"<<endl; for(int j = 0; j<G.arcNum; j++){ cout<<"please input two nodes of "<<j+1<<"-th arc"<<endl; VertexNode node1, node2; cin>>node1.data>>node2.data; insertArc(G, node1, node2);//插入弧 } return 1; }
2、打印邻接图
Status printALGraph(ALGraph &G){ for(int i = 0; i<G.vertexNum; i++){ cout<<i<<" "<<G.vertices[i].data; ArcNode *arc = G.vertices[i].firstArc; while(arc){ cout<<"-->"<<arc->adjvex; arc = arc->nextArc; } cout<<"-->NULL"<<endl;免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/153677.html
