《《算法与数据结构》教学课件-第9章 图--c语言描述（第2版）张乃孝编著》由会员分享，可在线阅读，更多相关《《算法与数据结构》教学课件-第9章 图--c语言描述（第2版）张乃孝编著（106页珍藏版）》请在金锄头文库上搜索。
1、9图9.1 基本概念9.5 最短路径9.2 图的周游 9.6 拓扑排序9.3 存储表示 9.7 关键路径9.4 最小生成树重点内容概述:图的深度优先搜索与广度优先搜索 最小生成树的Prim算法 最小生成树的Kruskal算法 单源最短路径Dijkstra算法 所有顶点对之间最短路径的Floyd算法 图的应用：拓扑排序和关键路径9.1 图的基本概念:图是由顶点的有穷非空集合V和边（顶点的偶 对）的集合E组成，记为G = ( V ，E ) 。 v0v1v2G1v0v3v2v1G2v0v1v2v6v5v4v3G3V(G1) = v0,v1,v2E(G1) = ,V(G2) = v0,v1,v2,v3
2、E(G2) = (v0,v1),(v0,v2),(v0,v3),(v1,v2),(v1,v3),(v2,v3)V(G3) = v0,v1,v2,v3,v4,v5,v6E(G3) = (v0,v1),(v0,v2),(v1,v3),(v1,v4),(v2,v5),(v2,v6)有向图和无向图有向图定义:若图中的每条边都是有方向的表示:有向图中的边是由两个顶点组成的有序对，有序对 用尖括号表示如表示一条有向边，vi是边的始点，vj是边的终点。 和代表两条不同的有向边。无向图定义:若图中每条边都是无方向的表示:无向图中的边是由两个顶点组成的无序对，无序对 用圆括号表示无向图中(vi ,vj)和(vj
3、 ,vi)代表同一条边。在本章中，对所讨论的图加了以下两个约束其一是 不考虑顶点到其自身的边，即若(vi ,vj)或是 E(G)中的边，则vi vj；其二是图中不允许一条边重复出 现，即如果(vi ,vj)或是E(G)中的边，则是唯一 的。 图G的顶点数n和边数e满足以下关系l若G是有向图，则0en(n-1)有向完全图：有n(n-1)条边的有向图l若G是无向图，则0en(n-1)/2。无向完全图：有n(n-1)/2条边的无向图完全图具有最多的边数。如图G2就是一个具有4个顶点的无向 完全图，边数为:4*(4-1)/2=12。相关概念完全图有向完全图l关联与邻接l若是一条有向边，则称顶点vi邻
4、接到vj，或顶点vj邻接于vi，边 与顶点vi，vj相关联。l若(vi,vj)是一条无向边，则vi和vj是相 邻顶点，(vi,vj)是与顶点vi和vj相关联 的边。l度：与顶点v相关联的边数称为顶点的度，记为 D(v)。 如G2中顶点v0的度为3，l入度：若G是一个有向图，则以顶点v为终点的 边的数目称为v的入度，记为ID(v)；l出度：以v为始点的边的数目称为v的出度，记 为OD(v)。 有向图中顶点v的度为其入度和出度之和，即 D(v)=ID(v)+OD(v)。 如图G1中顶点v1的入度为1，出度为2，度为3度、入度和出度无论是有向图还是无向图，顶点数n，边数e和度 数之间满足以下关系 =
5、n1ii)/2D(ve设有图G=(V，E)和G=(V，E)，如果V是V的子 集，E是E的子集，则称G是G的子图。子图G1如下图给出了有向图G1的若干子图。143212431121243路径与路径长度路径与路径长度l路径:图G=(V，E)中，若存在顶点序列vi0, vi1, , vin，使得(vi0, vi1)，( vi1, vi2)， (vin-1, vin)都在E中(若是有向图，则使得，都在E中) ，则称从顶点vi0到vin存在一条路径l 路径长度:路径上的边数。l 简单路径:若路径上的顶点除vi0和vin可以相同 外,其它顶点都不相同.l 回路或环:起点和终点相同的简单路径l如图G1中顶点
6、序列v0,v1,v0是一长度为2 的有向环；lG2中顶点序列v0,v1,v2,v3是一条从顶点v0到v3的长度 为3的路径，顶点序列v0,v1,v3,v0,v2是一条从顶点v0 到v2的长度为4的路径，但不是简单路径，顶点序列 v0,v1,v3,v0是一长度为3的环。G1G2根与有根图根与有根图l有向图中，若存在一顶点v，从该顶点有 路径可以到图中其它所有顶点，则称此有 向图为有根图，v称为图的根。l有根图中的根可能是不唯一的 连通图与连通分量连通图与连通分量l连通：图G=(V，E)中，若从vi到vj有一条路径(从 vj到vi也一定有一条路径)，则称vi和vj是连通的l连通图：若V(G)中任意
7、两个不同的顶点vi和vj都 是连通的(即有路径)，则称G为连通图l连通分量：无向图G中的最大连通子图称为G的连 通分量l强连通图：有向图G=(V，E)中，若V(G)中任意 两个不同的顶点vi和vj都存在从vi到vj以及从vj和 vi的路径，则称图G是强连通图l强连通分量：有向图的最大强连通子图称为图的 强连通分量l如图G2和G3都是连通图l如图G4是非连通图，它的两个连通分量H1和H2G2G3G4如左图G1是非强连通图它的两个强连通分量如右图所示G1网络与带权图网络与带权图 l若图的每条边都赋上一个权，则称为带权图l带权的连通图称为网络。通常权是具有某种意 义的数，下图为一个网络。9.1.2
8、抽象数据类型ADT Graph is operation 创建一个空图 Graph createGraph ( ) 判断图g是否空图，是则返回1，否则返回0 int isNullGraph ( g ) 找图中的第一个顶点，如果图是空图则返回NULL Vertex firstVertex ( g ) 找图中顶点vi的下一个顶点 Vertex nextVertex ( g , vi ) 查找图中值为value的顶点 Vertex searchVertex ( g , value )在图g中增加一个值为value的顶点 Graph addVertex ( g , value ) 在图g中删除一个顶点
9、和与该顶点相关联的所有边 Graph deleteVertex ( g , vertex ) 在图g中删除一条边e（ 或者(vi,vj) ） Graph deleteEdge ( g , vi , vj )在图g中增加一条边或者(vi,vj) Graph addEdge ( g , vi , vj )判断图g中是否存在一条指定边或者(vi,vj)int findEdge ( g , vi , vj )找图g中与顶点v相邻的第一个顶点Vertex firstAdjacent ( g , v )/v与返回顶点构成的边也称为与v相关联的第一条边。找图g中与vi相邻的，相对相邻顶点vj的，下一个相邻顶
10、点Vertex nextAdjacent ( g , vi , vj )/vi与返回值构成的边也称为是vi与vj构成的边的下一条边end ADT Graph9.2 图的周游图的周游是从图中某个顶点出发，按照某种方 式系统地访问图中的所有顶点，使每个顶点仅 被访问一次。也称图的遍历。连通图或强连通图：则从图中任意一顶点出发都可 以访问图中所有顶点。由于图中每个顶点都可能与图中其它多个顶点邻接 并存在回路，为了避免重复访问已访问过的顶点， 在图的周游中，通常对已访问的顶点作标记。图的遍历通常有两种方法：深度优先搜索和广度优 先搜索。它们对有向图和无向图都适用。深度优先周游深度优先周游(Depth_
11、First Traversal) 的策略又称为深度优先搜索（Depth_first Search），具体思想是从图的指定顶点v出 发，先访问顶点v，并将其标记为已访问过，然 后依次从v未被访问过的邻接顶点w出发进行深 度优先搜索，直到图中与v相连通的所有顶点都 被访问过。如果图中还有未被访问的顶点，则 从另一未被访问过的顶点出发重复上述过程， 直到图中所有顶点都被访问过为止。 l对图进行深度优先周游时，按访问顶点 的先后次序所得到的顶点序列，称为该 图的深度优先周游序列，简称DFS。l从上述的搜索方法可知，周游过程是一 个递归的过程。V7V6V3V2V5V1V8V4例子：v1v2 v4 v8v
12、5v3v6v7void dft ( Graph g ) Vertex v ; for ( v =firstVertex ( g ) ; v != NULL ; v = nextVertex ( g , v ) )if ( v.mark = FALSE ) dfs ( g , v ) ; void dfs ( Graph g , Vertex v ) Vertex v1; v.mark = TRUE ; for ( v1 = firstAdjacent ( g , v ); v1 != NULL ; v1=nextAdjacent ( g ,v, v1 ) )if (v1.mark=FALSE)
13、dfs ( g ,v1 ); 广度优先周游广度优先周游(Breadth_First Traversal)的策略又 称为广度优先搜索（Breadth_First Search），具体思 想是从图的指定顶点v出发，先访问顶点v，并将其标记 为已访问过，接着依次访问v的所有相邻结点w1，w2， ，wx，然后，再依次访问与w1，w2，wx邻接的所有 未被访问过的顶点，以此类推，直到所有已访问顶点的相 邻结点都被访问过为止。如果图中还有未被访问过的顶点 ，则从某个未被访问过的顶点出发进行广度优先搜索，直 到所有顶点都被访问过为止。 广度优先周游得到的顶点序列称为广度优先周游序列 ，简称BFS序列V7V6
14、V3V2V5V1V8V4例子：V1v2 v3 v4v5v6v7v8算法：void bft ( Graph g ) Vertex v ; for ( v =firstVertex ( g ) ; v != NULL ; v = nextVertex ( g , v ) )if ( v.mark = FALSE ) bfs ( g , v ) ; void bfs ( Graph g , Vertex v ) Vertex v1 , v2; Queue q ;/* 队列元素的类型为Vertex* */q = createEmptyQueue ( ) ; enQueue ( q ,v ) ; v.m
15、ark=TRUE; while ( !isEmptyQueue(q) ) v1 =frontQueue ( q ) ; deQueue ( q );v1.mark = TRUE; v2 =firstAdjacent ( g ,v1 ); while ( v2!=NULL ) if ( v2.mark = FALSE )enQueue ( q, v2 );v2 = nextAdjacent ( g , v1 , v2 ) ; l图的结构较复杂，任意两个顶点间都可能存在联系，因 而图的存储方法也很多，应根据具体的应用和施加的操 作选择图的存储表示法 9.3 图的存储邻接矩阵表示法邻接表表示法邻接多重表表示法、图的十字链表等9.3.1 邻接矩阵表示法邻接矩阵是表示顶点间相邻关系的矩阵 设G=(V，E)为具有n个顶点的图，其邻接矩 阵为具有以下性质的n阶方阵。 的权 ，则其邻接矩阵的所有对角线的值为0，其他元素 定义为 83032V2:813- 133032V1:13- 13302220V3:13- 192220V4:19终点 从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj- 2120V6:2051 64320 85623013 717329Dijkstra算法
