第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其它情况
A[i][j]???wij?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 -.173.- 第7章 图结构 } else cout<<\输入图中\.arcnum<<\条边(弧)和权的信息u v w:\\n\ for(k=0;k (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.- 第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.- 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《第7章 图结构》习题解答(2)在线全文阅读。
相关推荐：