第7章 图结构

CreateGraph_MG(G3,gk3); cout<<\建立一个无向网的邻接矩阵G4:\\n\ CreateGraph_MG(G4,gk4); cout<<\有向网G3的邻接矩阵为:\\n\ DisplyMG(G3); cout<<\无向网G4的邻接矩阵为:\\n\ DisplyMG(G4);

}程序运行演示结果为：

建立一个有向图的邻接矩阵G1:

输入顶点数vexnum和弧数arcnum:6 8↙ 按某种顺序输入6个顶点的值: 1 2 3 4 5 6↙

输入图中8条边(弧)的信息u v:

1 2 1 4 3 1 3 6 4 3 5 4 6 1 6 5↙ 建立一个无向图的邻接矩阵G2:

输入顶点数vexnum和弧数arcnum:6 7↙ 按某种顺序输入6个顶点的值: 1 2 3 4 5 6↙

输入图中7条边(弧)的信息u v:

1 2 1 4 2 3 2 6 5 3 5 6 5 4↙ 有向图G1的邻接矩阵为: 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0

无向图G2的邻接矩阵为: 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 1

0 1 0 0 1 0

*************************************** 建立一个有向网的邻接矩阵G3:

输入顶点数vexnum和弧数arcnum:4 4↙ 按某种顺序输入4个顶点的值: 1 2 3 4↙

输入图中4条边(弧)和权的信息u v w: 1 2 7 1 3 1 3 4 5 4 1 9↙ 建立一个无向网的邻接矩阵G4:

输入顶点数vexnum和弧数arcnum:5 5↙ 按某种顺序输入5个顶点的值: 1 2 3 4 5↙

输入图中5条边(弧)和权的信息u v w: 1 2 9 4 1 8 4 2 3 4 5 1 3 5 12↙ 有向网G3的邻接矩阵为: 0 7 1 0 0 0 0 0 0 0 0 5 9 0 0 0

无向网G4的邻接矩阵为: 0 9 0 8 0 9 0 0 3 0 0 0 0 0 12 8 3 0 0 1 0 0 12 1 0

说明：

（1）程序演示中建立的是图7.1、图7.3中4个图的邻接矩阵：G1.arcs、G2.arcs、G3.arcs、G4.arcs。从运行结果可以看出与图7.9的形式一致。

（2）在图的邻接矩阵存储结构上也容易实现其它基本操作，比如，对于无向图G中返回顶点v的第一个邻接点位置的基本操作函数：int FirstAdjVex_MG(MGraph G,VType v)。

算法的实现过程是： 1) 根据顶点信息v，通过调用函数int LocateVex_MG(MGraph G,VType v)找到v在G中的位置i；

2) 在G的邻接矩阵中寻找第i行中第一个非零元素所在的列号j； 3) 如果j存在函数返回j+1，否则返回0值。

类似地可以给出函数：int NextAdjVex_MG(MGraph G,VType v,VType w)的算法实现代码。 （3）用邻接矩阵表示有n个顶点的图G时，查找边（或弧）的时间复杂度为O(n2)。由于邻接矩阵的存储空间仅与顶点数n有关，而与边无关，因此，当图G的顶点较多而边数又很少时，其边的查找效率会很低。为此，下面给出图的另一种存储结构，即图的邻接表表示法。

-.175.-

第7章 图结构

7.2.2邻接表表示法

图的邻接表表示是把图的每个顶点的邻接顶点用一个链表来表示。一般地，用顺序存储的方式来表示图中n个顶点的信息，另外，对图中每个顶点v建立一个单链表，用于表示与v相邻接的所有顶点的位置（下标）。链表中每个结点有两个域值：一个是顶点位置（下标）域，用于表示该邻接点的序号；另一个是指针域，用于指向下一个邻接点。

1．邻接表的定义

(1) 表结点 在邻接表中，对图中的每个顶点建立一个单链表，顶点v所对应的单链表中的结点（表示依附于该顶点的边或以v为尾的弧）称为表结点。图的表结点中包含有顶点位置域(adjvex)、指向下一条边（弧）的指针域（nextarc）；而网的表结点中还要有表示相应权值的域（weight）。

(2) 头结点 在邻接表中每个单链表上附设一个结点，称为头结点。每个头结点由3个域组成：结点信息域(data)、结点访问次数域(flag)和指向链表中第一个结点的指针域(nextarc)。图中的所有头结点以顺序结构存储。

在图7.10中分别给出邻接表表结点的结构示图(a)和头结点的结构示图(b)。

例如，图7.11分别给出有向图G1和无向图G2的一种邻接表表示结构。

由于图中顶点的排列次序可以不同，每个顶点的邻接点的排列顺序也可以不同，所以，一个图的邻接表表示不唯一。

用邻接表表示具有n个顶点和e条边的无向图时，需要一个由n个元素组成的顺序表（表头结点表）和由2e个结点组成的n个单链表。而表示n个顶点和e条弧的有向图时，需要一个由n个元素组成的顺序表和由e个结点组成的n个单链表。当图中边（或弧）的数目远远少于图的顶点数目时，邻接表所需的存储空间要比邻接矩阵所需的少。

2．逆邻接表

-.176.-

第7章 图结构

在图G的邻接表中，顶点v的相邻元素可以通过遍历该顶点对应的单链表求得，设该链表中结点的个数为k那么，G为无向图时k表示v的度，G为有向图时k表示v的出度。如果求顶点v的入度，则需要遍历邻接表中的所有单链表，统计与v的序号相同的结点个数。这样处理很不方便，为此，仿照邻接表，建立一个逆邻接表，即对每个顶点v建立一个单链表，把所有邻接于v的顶点链接在一起，此时该单链表的长度即为v的入度。

例如，图7.11(a)所示的有向图可用逆邻接表表示为图7.12。

3．邻接表的存储表示与实现 (1)邻接表存储结构的类型定义

定义单链表结点类型ArcNode：

struct ArcNode{ int adjvex,weight;ArcNode* nextarc;}; 定义链表头结点结构类型VexNode：

struct VexNode{VType data;int flag;ArcNode* nextarc;}; 定义邻接表存储结构的类型ALGraph： struct ALGraph{ VexNode* vertices; //定义头结点数组指针vertices int vexnum,arcnum; //顶点数vexnum和边或弧数arcnum GKind kind; //图的种类标志kind };

(2)查找图中顶点位置的操作

函数的功能是，返回顶点u在图G中的位置，查找失败返回0值。 int LocateVex_AL(ALGraph G,VType u) { int i; for(i=0;i

(3)邻接表的建立操作

函数的功能是，根据图G的种类标志kind建立G的邻接表表示的存储结构。 #include\

void CreateGraph_AL(ALGraph& G,GKind kind) { int i,j,k;

-.177.-

第7章 图结构

}

VType u,v;

ArcNode* pr,*pr1; G.kind=kind;

cout<<\输入顶点数和边(弧)数vexnum arcnum:\cin>>G.vexnum>>G.arcnum;

G.vertices=new VexNode[G.vexnum]; //为顶点数组分配内存空间 cout<<\按某种顺序输入\.vexnum<<\个顶点的值:\\n\for(i=0;i

{ G.vertices[i].flag=0; //flag=0表示该顶点未被访问 cin>>G.vertices[i].data; //输入所有顶点的信息到vex中 G.vertices[i].nextarc=NULL; //设定初始的单链表为空 }

if(G.kind==DG||G.kind==UDG) cout<<\输入图中\.arcnum<<\条边(弧)的信息u v:\\n\else cout<<\输入图中\.arcnum<<\条边(弧)和权的信息u v w:\\n\

for(k=0;k>u>>v;} while(!((i=LocateVex_AL(G,u))&&(j=LocateVex_AL(G,v)))); i--,j--; //i,j从位置值转换为下标值 pr=new ArcNode; //动态分配单链表结点pr pr->adjvex=j; pr->weight=0; if(G.kind==DN||G.kind==UDN)cin>>pr->weight; //输入对应边（弧）的权值 pr->nextarc=G.vertices[i].nextarc; //将结点pr插入到第i个链表的首部 G.vertices[i].nextarc=pr; if(G.kind==UDG||G.kind==UDN) //对于无向图(或网)将结点pr1插入到第j个链表的首部 { pr1=new ArcNode; //动态分配单链表结点pr1 pr1->adjvex=i; pr1->weight=pr->weight; pr1->nextarc=G.vertices[j].nextarc; G.vertices[j].nextarc=pr1; //将结点pr1插入到第j个链表的首部 }//end switch }//end for

(4)显示输出邻接矩阵的操作

函数功能是，显示输出图G的邻接链表中的所有信息。 void DisplyAL(ALGraph G)//显示邻接矩阵G { int i;

-.178.-