数据结构-图.ppt

《数据结构-图.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7章图数据结构（C描述）目录7.1图的基本概念7.2图的存储结构7.3图的遍历7.4图的生成树和最小生成树7.5图的应用7.1图的基本概念图(Graph)是一种比线性表和树结构更复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和直接后继；在树形结构中，数据元素之间有着明显的层次关系结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图状结构被用于描述各种复杂的数据对象，在自然科学、社

2、会科学和人文科学等许多领域有着非常广泛的应用。7.1.1图的定义图(Graph)是由非空的顶点集合和一个描述顶点之间关系的边（或者弧）的集合组成，其形式化定义为：G＝（V，E）V＝{vi

3、vi∈VertexType}E＝{(vi,vj)

4、 vi,vj∈V}其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(vi,vj)表示一条边。无向图G1有向图G2例如：对于下图中的无向图G1,对应顶点集和边集为：V(G1)＝{v1,v2,v3,v4,v5}；E(G1)＝{(v1,v2

5、),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}对于下图中的有向图G2,对应顶点集和边集为：V(G2)＝{v1,v2,v3,v4,v5}；E(G2)＝{,,,,,,}7.1.2图的基本术语有向图和无向图完全图、稠密图、稀疏图度、入度、出度子图路径连通图权和网7.2图的存储结构图是一种结构复杂的数据结构，表现在不仅各个顶点的度可以千差万别，而且顶点之间的逻辑关系也错综复杂。从图的定义可知，一个图的信息包括两部分，即图中顶

6、点的信息以及描述顶点之间的关系（边或者弧）的信息。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方面的信息。下面介绍几种常用的图的存储结构。7.2.1邻接矩阵1．图的邻接矩阵表示在邻接矩阵表示中，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。若（i,j）∈E(G)或〈i,j〉∈E(G),则矩阵中第i行第j列元素值为1，否则为0。图的邻接矩阵定义为：1若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j]=0其它情形例如,对图7-8所示的无向图和有向图,它们的邻接矩阵见图7-9。无向图G312430111101011

7、011010G3的邻接矩阵图7-9邻接矩阵表示312001100110有向图G4G4的邻接矩图7-9邻接矩阵表示2．从无向图的邻接矩阵可以得出如下结论（1）矩阵是对称的;（2）第i行或第i列1的个数为顶点i的度;（3）矩阵中1的个数的一半为图中边的数目;（4）很容易判断顶点i和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。3．从有向图的邻接矩阵可以得出如下结论（1）矩阵不一定是对称的;（2）第i行中1的个数为顶点i的出度;（3）第i列中1的个数为顶点i的入度;（4）矩阵中1的个数为图中弧的数目;（5）很容易判断顶点i和顶点j是否有弧相连.4．

8、网的邻接矩阵表示类似地可以定义网的邻接矩阵为：wij若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j]=0若i=j∞其它情形网及网的邻接矩阵见图7-10。图7-10网及邻接矩阵示意图5312436124897000007493728421986316(a)网G5(b)网G5的邻接矩阵3．图的邻接矩阵数据类型描述用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：#definen6/*图的顶点数*/#definee8/*图的边（弧）数*/typedefcha

9、rvextype；/*顶点的数据类型*/typedeffloatadjtype；/*权值类型*/typedefstruct{vextypevexs[n]；adjtypearcs[n][n]；}graph；4．建立无向图的邻接矩阵voidcreatadj(graph&g){inti,j,k;for(k=0;k

10、,&j);//输入一条边(i,j)g.arcs[i][j]=1;g.arcs[j][i]=1;}}该算法的时