《图及其应用》PPT课件

《《图及其应用》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章图17.1抽象数据类型图的定义7.2图的存储表示7.3图的遍历7.4最小生成树7.6最短路径问题7.5拓扑排序、关键路径2熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。2.熟练掌握图的两种搜索路径的遍历：深度优先搜索和广度优先搜索的算法。3.图的算法应用。学习提要3图(Graph)：图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)。其中：V(G)是顶点的非空有限集，E(G)是边的有限集合，边是顶点的无序对或有序对。有向图：有向图G是由两个集合V(G)和E(G)组成

2、。其中：V(G)是顶点的非空有限集E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头。无向图：无向图G是由两个集合V(G)和E(G)组成的。其中：V(G)是顶点的非空有限集，E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v），并且（v,w)=(w,v)图的定义和术语4例：有向图245136G1图G1中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例：无向图15732

3、4G26图G2中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}5有向完备图：n个顶点的有向图最大边数是n(n-1)。无向完备图：n个顶点的无向图最大边数是n(n-1)/2。213213有向完备图无向完备图6权：与图的边或弧相关的数。网：带权的图例14523753186427子图：如果图G(V,E)和图G’(V’,E’),满足：V’V，E’E，则称G’为G的子图。3562451363568顶点的度无向图中，顶点的度为与每个顶点相连

4、的边数。有向图中，顶点的度分成入度与出度。入度：以该顶点为头的弧的数目。出度：以该顶点为尾的弧的数目。245136G1顶点2入度：1出度：3顶点4入度：1出度：0157324G26顶点5的度：3顶点2的度：49路径：路径是顶点的序列V={Vi,0,Vi,1,……Vi,n}，满足(Vi,j-1,Vi,j)∈E或∈E，(1≤j≤n)。路径长度：沿路径边的数目或沿路径各边权值之和。回路：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径叫~简单回路：除了第一个顶点和最后一个顶点外，其余

5、顶点不重复出现的回路。G1245136路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，310157324G26路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，111连通：从顶点V到顶点W有路径，则说V和W是连通的。连通图：图中任意两个顶点都是连通的图。连通图24513612连通分量：非连通图的每一个连通部分。强连通图：有向图中，如果对每一对Vi,Vj∈V,Vi≠Vj,从Vi

6、到Vj和从Vj到Vi都存在路径，则称G是强连通图。强连通图356245136非连通图连通分量137.2图的存储表示一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示四、无向图的邻接多重表存储表示14Aij=0(i,j)VR1(i,j)VR图的数组(邻接矩阵)存储表示BACDFE定义:矩阵的元素为特点：对称矩阵顶点的度数FirstAdjVex(G,v);NextAdjVex(G,v,w);如何求?ABCDEFABCDEF15从无向图的邻接矩阵可以得出如下结论（1）矩阵是对称的，可压缩存储（上（

7、下）三角）;（2）第i行或第i列中1的个数为顶点i的度;（3）矩阵中1的个数的一半为图中边的数目;（4）很容易判断顶点i和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。011110101101101016有向图的邻接矩阵ABECD从有向图的邻接矩阵可以得出如下结论（1）矩阵不一定是对称的;（2）第i行中1的个数为顶点i的出度;（3）第i列中1的个数为顶点i的入度;（4）矩阵中1的个数为图中弧的数目;（5）很容易判断顶点i和顶点j是否有弧相连.ABCDEABCDE17网的邻接矩阵表示类似地可以定义网的邻接矩阵为：wij若

8、（i,j）∈E(G)或〈i,j〉∈E(G)∞其它情形A[i][j]=123451234518constMAX_VERTEX_NUM=20;//最大顶点个数typedefenum{DG,DN,AG,AN}GraphKind;//类型标志{有向图,有向网,无向图,无向网}type