数据结构第七章图(4).ppt

1、第四节 图的连通性问题,一、 无向图的连通分量和生成树 1、 无向图的连通分量 连通分量（Connected Components）,无向图的连通分量 We can use the two elementary graph searchs to create additional，more interesting，graph operations. For illustrative purposes，let us look at the problem of determining whether or not an undirected graph is connected.,无向图的连通分

2、量 We can implement this operation by simply calling either DFS（0）or BFS（0）and then determining if there are any unvisited vertices.,无向图的连通分量 在对无向图进行遍历时，对于连通图，仅需从图 中任一顶点出发，进行深度优先搜索或宽度优先 搜索，便可访问到图中的所有顶点 对于非连通图，则需要从多个顶点出发进行搜索， 而每一次从一个新的起始点出发进行搜索过程中 得到的顶点访问顺序恰恰为其各个连通分量中的 顶点集,无向图的连通分量 例如：图7.3中的G3是非连通图，按照

3、图7.14中 所示的邻接链表进行深度优先搜索， 三次调用 DFS过程 这三个顶点集分别加上所有依附于这下顶点的边， 便构成了非连通图G3的三个连通分量,2、 生成树（Spanning Trees） A spanning tree is any tree that consists solely of edges in G and that includes all the vertices in G. 一个连通图的生成树是一个极小连通子图，它 含有图中全部顶点，但只有足以构成一棵树的 n-1条边,生成树 When graph G is connected，a depth first searc

4、h or breadth first search starting at any vertex visits all the vertices in G. The search implicitly partitions the edges in G into two sets：T（for tree edges）and N（for nontree edges）.,生成树 T is the set of edges used or traversed during the search and N is the set of remaining edges. The edges in T fo

5、rm a tree that includes all vertices of G.,生成树 As we just indicated，we may use either dfs or bfs to create a spanning tree. When dfs is used，the resulting spanning tree is known as a depth first spanning tree. When bfs is used，the resulting spanning tree is known as a breadth first spanning tree.,二、

6、 最小生成树 Minimum cost spanning tree 也称为最小代价生成树,最小代价生成树 The cost of a spanning tree of a weighted undireted graph is the sum of the costs（i.e. weights）of the edges in the spanning tree. A minimum cost spanning tree of least cost.,最小代价生成树 There are three different algorithms can be used to obtain a mini

7、mum cost spanning tree of a connected undirected graph. All three use an algorithms design strategy called the greedy method（贪婪算法）.,最小代价生成树 We shall refer to the three algorithms as： Kruskals algorithm Prims algorithm Sollins algorithm,最小代价生成树 In the greed method，we construct an optimal （最优的）solutio

8、n in stages. At each stages，we make a decision that is the best decision（using some criterion）at this time. Since we cannot change this decision later，we make sure that the decision will reach in a feasible solution.,最小代价生成树 The greedy method can be applied to a wide variety of programming problems.

9、 Typically，the selection of an item at each stage is based on either a least cost or a highest profit criterion.,Prims algorithm Prims algorithm，like Kruskals，constructs the minimum cost spanning tree one stage at one time . However，at each stage of the algorithm，the set of selected edges forms a tr

10、ee，by contrast， the set of selected edges in Kruskals algorithm forms a forest at each stage.,Prims algorithm Prims algorithm begins with a tree，T，that contains a single vertex. This may be any of the vertices in the original graph.,Prims algorithm Next，we add a least cost edges（u，v）to T so that T （

11、u，v） is also a tree. We repeat this edge addition step until T contains n-1 edges.,Prims algorithm To make sure that the added edge does not from a cycle，at each step we choose the edge（u，v） such that exactly one of u or v is inT. 典例分析,T= ； TV= 0； / start with vertex 0 and no edges while T contains

12、fewer than n-1 edges let u，v be a least cost edge such that uTV and v not TV； if there is no such edge break；,add v to TV； add u，v to T； if T contains fewer than n-1 edges printf（”No spanning treen”）；,第五节 有向无环图及其应用,一、 有向无环图（directed acycline graph，DAG） 一个无环的有向图称为有向无环图，简称DAG图,有向无环图 DAG图是一类较有向图更一般的特殊有

13、向图 P179图7.21：显示了有向树、DAG图和有向图 的区别,有向无环图 DAG图是描述含有公共子式的表达式的有效工具 P179典例分析 若利用DAG图，则可实现对相同子式的共享， 从而节省存储空间,有向无环图 检查一个有向图是否存在环比无向图要复杂 对于无环图来说，若深度优先遍历过程中遇到 回边（即指向已访问过的顶点的边），则肯定 存在环,二、 拓扑排序（Topological Sort） A topological order is a linear ordering of the vertices of a directed graph,拓扑排序 拓扑排序的算法 在有向图中选择一个没

14、有前驱的顶点且输出之 从图中删除该顶点和所有以它为尾的弧,拓扑排序 重复上述两步，直到全部顶点均已全部输出， 或者当前图中不存在无前驱的顶点为止 后一种情况则说明有向图中肯定存在环,拓扑排序 拓扑排序的详细算法 以邻接表作为存储结构 把邻接表中所有入度为0的顶点进栈,拓扑排序 栈非空时，输出栈顶元素Vj并退栈 在邻接表中查找Vj的直接后继Vk，把Vk的入度 减1 若Vk的入度为0则进栈,拓扑排序 重复上述操作直至栈空为止 若栈空时输出的顶点个数不是n，则有向图有环 否则，拓扑排序完毕,邻接表结点 typedef struct node int adjvex； / 顶点域 struct node

15、 *nextarc； / 链域 JD；,表头结点 typedef struct node int in； / 入度域 struct node *link； / 链域 TD； TD gM； / g0不用,Status TopologicalSort（ALGraph G） / 有向图G采用邻接表存储结构 / 若G无回路，则输出G的顶点的一个拓扑排序序列 并返回OK；否则ERROR； FindInDegree（G，indegree）； InitStack（S）；,for（i=0；iG.vernum；+i） / 建零入度顶点栈S if（!indegreei） Push（S，i）； / 入度为0者进栈 count=0； / 对输出顶点计数 while（!StackEmpty（S） Pop（G，i）； print