第7章 图结构

可以看出，图中所有顶点的位置都是平等的，可以将任意一个顶点看成是第一个或最后一个顶点，也无法将其排列成一个线性序列或层次关系。在实际操作中，为了方便起见，需要将所有顶点按照某个任意选定的顺序排列起来（排列与图中顶点之间的关系无关）。所以，“顶点在图中的位置”是指该顶点在这个人为的随意排列中的位置（或序号）。同理，可以对某个顶点的所有邻接点按照某个任意选定的顺序进行排列。

7.1.3图的基本操作

对于图结构，常用的操作有以下几种：

（1）创建CreateGraph(&G,V,VR) 根据顶点集V和关系（边或弧）集VR构造图G；

（2）查找LocateVex(G,u) 函数功能是，如果图G中存在信息等于u的顶点则返回该顶点在G中的位置，否则返回0；

（3）提取GetVex(G,v) 函数功能是，返回图G中顶点v的信息；

（4）修改PutVex(&G,v,value) 函数功能是，修改图G中顶点v的信息为value；

（5）邻接点FirstAdjVex(G,v) 函数功能是，返回图G中顶点v的第一个邻接点在G中的位置，操作不成功时返回0； （6）下一个邻接点NextAdjVex(G,v,w) 函数中v,w是图G的顶点，且w是v的一个邻接点。函数功能是，返回顶点v相对于w的下一个邻接点所在的位置，如果w是v的最后一个邻接点则返回0；

（7）插入顶点InsertVex(&G,v) 函数功能是，在图G中插入顶点v；

（8）删除顶点DeleteVex(&G,v) 函数功能是，在图G中删除顶点v以及相关的边或弧； （9）插入弧InsertArc(&G,v,w) 函数功能是，在图G中增加边(v,w)或弧； （10）删除弧DeleteArc(&G,v,w) 函数功能是，在图G中删除边(v,w)或弧；

（11）深度优先遍历DSFTraverse(G,v,Visit()) 函数功能是，从顶点v开始按深度优先遍历图G，其中Visit()是关于顶点的操作函数；

（12）广度优先遍历BSFTraverse(G,v,Visit()) 函数功能是，从顶点v开始按广度优先遍历图G，其中Visit()是关于顶点的操作函数。

7.2 图的存储表示与实现

图是一种复杂结构其存储方法也比较多，在实际应用中，一般需要根据具体的图形和要进行的操作来选取适当的存储结构。图的常用存储结构有：邻接矩阵表示法、邻接表表示法、十字链表表示法和多重链接表表示法。

7.2.1邻接矩阵表示法

邻接矩阵表示法是图的一种顺序存储表示法。用两个数组分别存储数据元素（顶点）的信息和元素之间所存在的关系(边或弧)的信息。该表示法既可用于表示无向图也可用于表示有向图。

1．邻接矩阵的定义

-.171.-

第7章 图结构

设G=(V,VR)是一个图，含有n个顶点，那么G的邻接矩阵是表示G中顶点之间相邻关系的n阶方阵An×n，下面分别根据有权图和无权图给出矩阵A的定义。

如果G是无权图，则A的定义为：

?1A[i][j]???0如果G是有权图，则A的定义为：

(vi,vj)?VR或?vi,vj??VR其它情况

?wijA[i][j]???0(vi,vj)?VR或?vi,vj??V（权值wij?0）R其它情况(为操作统一此处用0而非?)

【例7.1】分别给出图7.1、图7.3中各图的邻接矩阵。

在图7.1(a)、图7.1(b)中，图的顶点顺序按v1,v2,v3,v4,v5,v6排列时的邻接矩阵分别如图7.9(a)、图7.9(b)所示；在图7.3(a)、图7.3(b)中，图的顶点顺序分别按A,B,C,D和A,B,C,D,E排列时的邻接矩阵分别如图7.9(c)、图7.9(d)所示。

显然，图的邻接矩阵有以下特点：

(1) 当图中顶点的排列顺序确定后，该图的邻接矩阵是唯一确定的；

(2) 无向图的邻接矩阵是对称的，可以采用压缩存储的方法仅存入其下三角（或上三角）部分的元素即可；

(3) 在无向图中，顶点vi的度是其邻接矩阵A的第i行元素的和，即：TD(vi)??A[i][j]；

j?0n?1(4) 在有向图中，顶点vi的出度是其邻接矩阵A的第i行元素的和，而入度是A的第i列元素的和，所以vi 的度可以表示为：TD(vi)??A[i][j]??A[j][i]（n为图中顶点的个数）。

j?0j?0n?1n?12．邻接矩阵的存储表示与实现 (1)邻接矩阵的类型定义

typedef enum{DG,DN,UDG,UDN}GKind; //图的类型GKind{有向图,有向网,无向图,无向网}

-.172.-

第7章 图结构

typedef int VType; //为便于操作，定义顶点类型VType为int 型 struct VNode{int flag;VType vex;}; //顶点与访问情况类型VNode{访问次数,顶点信息} struct MGraph{ //定义图的邻接矩阵类型MGraph VNode* vexs; //描述顶点的数组指针vexs VType* arcs; //邻接矩阵的数组指针arcs int vexnum,arcnum; //顶点数vexnum和边或弧数arcnum GKind kind; //图的种类标志kind };

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

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

(3)邻接矩阵的建立操作

函数的功能是，根据图G的种类标志kind建立图G的所有信息。 #include\

void CreateGraph_MG(MGraph& G,GKind kind) { int i,j,k; VType u,v; cout<<\输入顶点数vexnum和弧数arcnum:\ cin>>G.vexnum>>G.arcnum; G.kind=kind; G.vexs=new VNode[G.vexnum]; //为G.vexs分配存储空间 G.arcs=new VType[G.vexnum*G.vexnum]; //为G.arcs分配存储空间 cout<<\按某种顺序输入\.vexnum<<\个顶点的值:\\n\ for(i=0;i>G.vexs[i].vex; //输入所有顶点的信息到G.vexs中 } for(i=0;i

-.173.-

第7章 图结构

}

else cout<<\输入图中\.arcnum<<\条边(弧)和权的信息u v w:\\n\

for(k=0;k>u>>v; } //根据顶点信息找到所在位置 while(!((i=LocateVex_MG(G,u))&&(j=LocateVex_MG(G,v)))); i--,j--; //i,j从位置值转换为下标值 G.arcs[i*G.vexnum+j]=1; if(G.kind==DN||G.kind==UDN) cin>>G.arcs[i*G.vexnum+j]; //输入相应边或弧的权重w if(G.kind==UDG||G.kind==UDN) //无向图的邻接矩阵是对称的 G.arcs[j*G.vexnum+i]=G.arcs[i*G.vexnum+j]; }

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

函数功能是，显示输出图G的邻接矩阵G.arcs。 void DisplyMG(MGraph G) { int i,j; for(i=0;i

(5)演示程序主函数

程序中分别建立有向图G1、无向图G2、有向网G3和无向网G4的邻接矩阵，并显示输出每个邻接矩阵的数据信息。

void main()

{ MGraph G1,G2,G3,G4; GKind gk1=DG,gk2=UDG,gk3=DN,gk4=UDN; cout<<\建立一个有向图的邻接矩阵G1:\\n\ CreateGraph_MG(G1,gk1); cout<<\建立一个无向图的邻接矩阵G2:\\n\ CreateGraph_MG(G2,gk2); cout<<\有向图G1的邻接矩阵为:\\n\ DisplyMG(G1); cout<<\无向图G2的邻接矩阵为:\\n\ DisplyMG(G2); cout<<\ cout<<\建立一个有向网的邻接矩阵G3:\\n\

-.174.-