资源描述：
《数据结构 第7章 图 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),(v1,v4),(v2,v3),(v3,
5、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。无向图G312430111101011011010G3的邻接矩阵图7-9邻接矩阵表示312001100110有向图G4G4的邻
7、接矩阵图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．网的邻接矩阵表示类似地可以定义网的邻接矩阵为：wij若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j
8、]=0若i=j∞其它情形网及网的邻接矩阵见图7-10。图7-10网及邻接矩阵示意图5312436124897(a)网G5(b)网G5的邻接矩阵0074937284219863160003．图的邻接矩阵数据类型描述用邻接矩阵表示法表示图或网，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：#definen6/*图的顶点数*/#definee8/*图的边（弧）数*/typedefcharvextype；/*顶点的数据类型*/typedeffloatadjtype；/*权值类型*/typedefstruct{vextyp
9、evexs[n]；adjtypearcs[n][n]；}graph；7.2.2邻接表1．图的邻接表表示将每个顶点的边用一个单链表链接起来，若干个顶点可以得到若干个单链表，每个单链表都有一个头结点，所有头结点组成一个一维数组，称这样的链表为邻接表。例如，图7-8所示的无向图G3和有向图G4的邻接表见图7-11所示((b)有向图G4的邻接表(c)有向图G4的逆邻接表图7-11邻接表示例有向图G4123424^134^24^123^(a)无向图G31243(b)无向图G3的邻接表图7－11：邻接表示例12323^3^1^1233^1
