数据结构C描述电子教案第7章ppt课件.ppt

《数据结构C描述电子教案第7章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录7.6拓扑排序7.1图的基本概念7.2图的存贮结构7.3图的遍历7.4生成树和最小生成树7.5最短路径退出7.1图的基本概念7.1.1图的定义图是由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二元组定义为：G=（V,E）。例如，对于图7-1所示的无向图G1和有向图G2，它们的数据结构可以描述为：G1=(V1,E1),其中V1={a,b,c,d},E1={(a,b),(a,c),(a,d),(b,d),(c,d)},而G2=(V2,E2)，其中V2={1,2,3},E2={<1,2>,<1,3>,<2,3>,<3,1>}

2、。7.1.2图的基本术语1.有向图和无向图在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。如图7-1中，G1为无向图，G2为有向图。在无向图中，一条边（x,y）与（y,x）表示的结果相同，用圆括号表示，在有向图中，一条边与表示的结果不相同，故用尖括号表示。〈x,y>表示从顶点x发向顶点y的边，x为始点，y为终点。有向边也称为弧，x为弧尾，y为弧头,则〈x,y>表示为一条弧,而〈y,x>表示y为弧尾，x为弧头的另一条弧。2.完全图、稠密图、稀疏图具有n个顶点，n(n-1)/2条边的图，称为完全无向图

3、，具有n个顶点，n(n-1)条弧的有向图,称为完全有向图。完全无向图和完全有向图都称为完全图。对于一般无向图，顶点数为n，边数为e，则0≤e≤n(n-1)/2。对于一般有向图，顶点数为n，弧数为e，则0≤e≤n(n-1)。当一个图接近完全图时，则称它为稠密图，相反地，当一个图中含有较少的边或弧时，则称它为稀疏图。3.度、入度、出度在图中，一个顶点依附的边或弧的数目，称为该顶点的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。另外，若图中有n个顶点，e条边

4、或弧，第i个顶点的度为di，则有e=4.子图若有两个图G1和G2，G1=(V1,E1)，G2=(V2,E2)，满足如下条件：V2V1，E2E1，即V2为V1的子集，E2为E1的子集，称图G2为图G1的子图。图和子图的示例具体见图7-2。5．权在图的边或弧中给出相关的数，称为权。权可以代表一个顶点到另一个顶点的距离，耗费等，带权图一般称为网。带权图的示例具体见图7-3。6．连通图和强连通图在无向图中，若从顶点i到顶点j有路径，则称顶点i和顶点j是连通的。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图。连通图和非连通图示例见图

5、7-4。在有向图中，若从顶点i到顶点j有路径，则称从顶点i和顶点j是连通的，若图中任意两个顶点都是连通的，则称此有向图为强连通图，否则称为非强连通图。强连通图和非强连通图示例见图7-5。7．连通分量和强连通分量无向图中，极大的连通子图为该图的连通分量。显然，任何连通图的连通分量只有一个，即它本身，而非连通图有多个连通分量。对于图7-4中的非连通图，它的连通分量见图7-6。有向图中，极大的强连通子图为该图的强连通分量。显然，任何强连通图的强连通分量只有一个，即它本身，而非强连通图有多个强连通分量。对于图7-5中的非强连通图，它的强连通分量见图7-

6、7。8．路径、回路在无向图G中，若存在一个顶点序列Vp,Vi1，Vi2，…，Vin，Vq,使得（Vp,Vi1）,(Vi1,Vi2),…..，(Vin,Vq)均属于E（G），则称顶点Vp到Vq存在一条路径。若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。起点和终点相同的路径称为回路，简单路径组成的回路称为简单回路。路径上经过的边的数目称为该路径的路径长度。9．有根图在一个有向图中，若从顶点V有路径可以到达图中的其它所有顶点，则称此有向图为有根图，顶点V称作图的根。10．生成树、生成森林连通图的生成树是一个极小连通子图，

7、它包含图中全部n个顶点和n-1条不构成回路的边。非边通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。7.2图的存贮结构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。2．从无向图的邻接矩阵可以得出

8、如下结论（1）矩阵是对称的;（2）第i行或第i列1的个数为顶点i的度;（3）矩阵中1的个数的一半为图中边的数目;（4）很容易判断顶点i和顶点j之间是否