《算法导论课件第8讲图的算法1章节》由会员分享，可在线阅读，更多相关《算法导论课件第8讲图的算法1章节（23页珍藏版）》请在金锄头文库上搜索。
1、1,第4章 图的算法,图的搜索问题 拓扑排序 强连通分支,2,拓扑排序,Problem: Given a set of jobs, (e.g. courses, etc.) with prerequisite constraints, output the jobs in an order that does not violate any of the prerequisites.,3,拓扑排序,This lecture shows how depth-first search can be used to perform a topological sort of a directed a
2、cyclic graph, or a “dag“ as it is sometimes called. A topological sort of a dag G = (V, E) is a linear ordering of all its vertices such that if G contains an edge (u, v), then u appears before v in the ordering. (If the graph is not acyclic, then no linear ordering is possible.) A topological sort
3、of a graph can be viewed as an ordering of its vertices along a horizontal line so that all directed edges go from left to right. Topological sorting is thus different from the usual kind of “sorting“ studied in the above.,4,拓扑排序,运用深度优先搜索，对一个有向无回路图（有时称为dag）进行拓扑排序。结果为该图所有顶点的一个线性序列。 性质：如果G包含边(u, v), ，
4、则在该序列中， u就出现在v的前面（如果图是有回路的，就不可能存在这样的线性序列）. 一个拓扑排序可以看成是图中所有顶点艳水平线排列而成的一个序列，使得所有的有向边均从左指向右。,5,早上穿衣的过程,Directed acyclic graphs are used in many applications to indicate precedences among events.,(a) Each directed edge (u, v) means that garment u must be put on before garment v. The discovery and finish
5、ing times from a depth-first search are shown next to each vertex. (b) The same graph shown topologically sorted. Its vertices are arranged from left to right in order of decreasing finishing time. Note that all directed edges go from left to right.,6,早上穿衣的过程,(a) 每一个有向边 (u, v)都意味着必须先穿衣服 u 再穿衣服 v. 深度
6、优先搜索中的发现和完成时间都在每个顶点的旁边示出. (b) 经过拓扑排序后的同一图形。图中的各个顶点按照完成时间的递降顺序，至左向右排列。注意所有的有向边都是从左指向右的.,7,The following simple algorithm topologically sorts a dag. TOPOLOGICAL-SORT(G) 1 call DFS(G) to compute finishing times fv for each vertex v 2 as each vertex is finished, insert it onto the front of a linked list
7、 3 return the linked list of vertices,拓扑排序算法思想,8,拓扑排序算法思想,1 调用DFS(G)计算每个节点的完成时间fv； 2 当每个节点完成后，把它插入链表前端； 3 返回由节点组成的链表。,9,拓扑排序算法复杂度,The figure (b) shows how the topologically sorted vertices appear in reverse order of their finishing times. We can perform a topological sort in time (V + E), since dept
8、h-first search takes (V + E) time and it takes O(1) time to insert each of the |V| vertices onto the front of the linked list.,10,拓扑排序性质,Lemma A directed graph G is acyclic if and only if a depth-first search of G yields no back edges.,Theorem TOPOLOGICAL-SORT (G) produces a topological sort of a di
9、rected acyclic graph G.,11,拓扑排序性质,Lemma 一个有向图 G 是无回路的，当且仅当对 G进行深度优先搜索时没有得到反向边。,Theorem TOPOLOGICAL-SORT (G) 产生一个有向无回路的图 G的拓扑排序。,12,作业,1. Show how depth-first search works on this graph. Assume that the for loop of lines 5-7 of the DFS procedure considers the vertices in alphabetical order, and assum
10、e that each adjacency list is ordered alphabetically. Show the discovery and finishing times for each vertex, and show the classification of each edge.,2. Show the parenthesis structure of the depth-first search shown in the Figure.,13,作业,1.说明深度优先搜索在下图上是如何进行的。假定DFS过程的第5-7行for循环按字母表顺序考察各个顶点，并假定每个临接表都
11、是按照字母顺序排序的。说明每个顶点的发现和完成时间，并给出每条边的分类。,2. 对上图所示的深度优先搜索，给出其括号结构。,14,作业,3.在1假设下，说明TOPOLOGICAL-SORT (G) 运行于下图中所示的有向无回路图上时，所产生的顶点顺序。,15,强连通分支,定义 图的强连通分支：A strongly connected component of a directed graph G = (V, E) is a maximal set of vertices C V such that for every pair of vertices u and v in C, we have
12、 both and ; that is, vertices u and v are reachable from each other.,利用深度优先搜索把有向图分解为强连通分支是其经典应用。,16,强连通分支,Our algorithm for finding strongly connected components of a graph G = (V, E) uses the transpose of G, which is defined to be the graph GT = (V, ET), where ET = (u, v) : (v, u) E. That is, ET co
13、nsists of the edges of G with their directions reversed. Given an adjacency-list representation of G, the time to create GT is O(V + E). It is interesting to observe that G and GT have exactly the same strongly connected components: u and v are reachable from each other in G if and only if they are
14、reachable from each other in GT.,17,强连通分支算法,The following linear-time (i.e., (V + E)-time) algorithm computes the strongly connected components of a directed graph G = (V, E) using two depth-first searches, one on G and one on GT. STRONGLY-CONNECTED-COMPONENTS (G) 1 call DFS (G) to compute finishing
15、 times fu for each vertex u 2 compute GT 3 call DFS (GT), but in the main loop of DFS, consider the vertices in order of decreasing fu (as computed in line 1) 4 output the vertices of each tree in the depth-first forest formed in line 3 as a separate strongly connected component .,18,强连通分支算法,强连通分支算法
16、的主要思想： 调用DFS(G)以计算出每个节点u的完成时间fu; 计算GT; 调用DFS(GT),但是在DFS的主循环里按fu递减的顺序考虑各结点(和第1步一样计算)； 输出第3步中产生的深度优先森林中每棵树的结点，作为各自独立的强连通分支。,19,强连通分支查找算法,Strategy: Phase 1: A standard depth-first search on G is performed, and the vertices are put in a stack at their finishing times Phase 2: A depth-first search is performed on GT, the transpose graph. To start a search, vertices are popped off the stack. A strongly connected component in the graph is identified by the name
