欢迎来到天天文库
浏览记录
ID:16259980
大小:231.00 KB
页数:4页
时间:2018-08-08
《图的邻接表表示法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、图的邻接表表示法图的邻接表表示法类似于树的孩子链表表示法。对于图G中的每个顶点vi,该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表,这个单链表就称为顶点vi的邻接表(AdjacencyList)。1.邻接表的结点结构(1)表结点结构adjvex next邻接表中每个表结点均有两个域:①邻接点域adjvex存放与vi相邻接的顶点vj的序号j。②链域next将邻接表的所有表结点链在一起。注意:若要表示边上的信息(如权值),则在表结点中还应增加一个数据域。(2)头结点结构vertexfirstedge顶点vi邻接表的头结点包含两个域:①顶点域vert
2、ex存放顶点vi的信息②指针域firstedgevi的邻接表的头指针。注意:①为了便于随机访问任一顶点的邻接表,将所有头结点顺序存储在一个向量中就构成了图的邻接表表示。②有时希望增加对图的顶点数及边数等属性的描述,可将邻接表和这些属性放在一起来描述图的存储结构。2.无向图的邻接表对于无向图,vi的邻接表中每个表结点都对应于与vi相关联的一条边。因此,将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。【例】对于无向图G5,其邻接表表示如下面所示,其中顶点v0的边表上三个表结点中的顶点序号分别为1、2和3,它们分别表示关联于v0的三条边(v0,v1),
3、(v0,v2)和(v0,v3)。4 注意:n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。3.有向图的邻接表对于有向图,vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此,将有向图的邻接表称为出边表。【例】有向图G6的邻接表表示如下面(a)图所示,其中顶点v1的邻接表上两个表结点中的顶点序号分别为0和4,它们分别表示从v1射出的两条边(简称为v1的出边):和。注意:n个顶点e条边的有向图,它的邻接表表示中有n个顶点表结点和e个边表结点。4.有向图的逆邻接表在有向图中,为图中每个顶点vi建立一个
4、入边表的方法称逆邻接表表示法。入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。【例】G6的逆邻表如上面(b)图所示,其中v0的人边表上两个表结点1和3分别表示射人v0的两条边(简称为v0的入边):和。注意:n个顶点e条边的有向图,它的邻接表表示中有n个顶点表结点和e个边表结点。5.邻接表的形式说明及其建表算法(1)邻接表的形式说明varhead,next,point:array[0..2001]oflongint;/*邻接表的表首顶点为head,后继指针为next,顶点序列为point*/p:longint;pr
5、ocaddedge(a,b:longint);/*(a,b)进入邻接表*/vart:longint;{inc(p);point[p]←b;/*增加顶点b*/ifhead[a]=0/*(a,b)进入邻接表*/thenhead[a]←p4else{t←head[a];whilenext[t]<>0dot←next[t];next[t]←p};/*else*/};/*addedge}*/ (2)邻接表的形式说明 constn=10;e=20;{n为顶点数,e为边数}typeedge=^edgenode;edgenode=record{边节点信息}adjvex
6、:1..n;{边的终点(链接点)}weight:integer;{该边上的权,无权图可以省去}next:edge;{指向下一条边的链接}end;vex=recordvertex:integer;firstedge:edge;end;vars:edge;g=array[1..n]ofvex;beginread(n,e);{n为顶点数,e为边数}fori:=1tondobeginread(g[i].vertex);{读入顶点信息表}g[i].firstedge:=nil;{表头指针初始化}end;fork:=1toedo{建立邻接表}beginread(i,
7、j,w);{读入一条边的起点、终点及权值}new(s);s^.adjvex:=j;{新节点赋值}s^.weight:=w;s^.next:=g[i].firstedge;g[i].firstedge:=s;new(s);s^.adjvex:=i;{新节点赋值}s^.weight:=w;s^.next:=g[j].firstedge;g[j].firstedge:=s;end;end. 该算法的时间复杂度是O(n+e)。 注意:4 ①建立有向图的邻接表更简单,每当读入一个顶点对序号时,仅需生成一个邻接序号为j的边表结点,将其插入到vj的出边表头部即可
8、。 ②建立网络的邻接表时,需在边表的每个结点中增加一个存储边上权的数据域。
此文档下载收益归作者所有