Show the ordering of vertices produced by TOPOLOGICAL-SORT when it is run on the dag of Figure 22.8, under the assumption of Exercise 22.3-2.
Give a linear-time algorithm that takes as input a directed acyclic graph G = (V, E) and two vertices s and t, and returns the number of paths from s to t in G. For example, in the directed acyclic graph of Figure 22.8, there are exactly four paths from vertex p to vertex v: pov, por yv, posr yv, and psr yv. (Your algorithm only needs to count the paths, not list them.)
Add a field to the vertex representation to hold an integer count. Initially, set vertex t’s count to 1 and other vertices’ count to 0. Start running DFS with s as the start vertex. When t is discovered, it should be immediately marked as finished (BLACK), without further processing starting from it. Subsequently, each time DFS finishes a vertex v, set v’s count to the sum of the counts of all vertices adjacent to v. When DFS finishes vertex s, stop and return the count computed for s.
Give an algorithm that determines whether or not a given undirected graph G = (V, E) contains a cycle. Your algorithm should run in O(V) time, independent of |E|.
An undirected graph is acyclic (i.e., a forest) iff a DFS yields no back edges. Since back edges are those edges (u, v) connecting a vertex u to an ancestor v in a depth-first tree, so no back edges means there are only tree edges, so there is no cycle.
So we can simply run DFS. If find a back edge, there is a cycle. The complexity is O(V ) instead of O(E + V ). Since if there is a back edge, it must be found before seeing |V | distinct edges. This is because in a acyclic (undirected ) forest, |E| ≤ |V | - 1
Prove or disprove: If a directed graph G contains cycles, then TOPOLOGICAL-SORT (G) produces a vertex ordering that minimizes the number of "bad" edges that are inconsistent with the ordering produced.
该结论是不成立的. 选择不同的起始点, 拓扑排序(按书上的深度优先遍历实现)会给出不同的序列, 不能保证坏边的数目最少.
先说明坏边的含义:
假设拓扑排序生成的结点序列为 a,b,c,d , 则对于该序列来说有向边 d -> a 为坏边, a -> d 不是.
考虑如下反例:
对于以下图 G:
a
/ ^\
/ \\
V \V
b ------> c 若从 a 点开始, 得到序列 a, b, c, 则有 1 条坏边 c -> a
若从 b 点开始, 得到序列 b, c, a, 则有 2 条坏边 a -> c, a -> b
所以结论不成立
Another way to perform topological sorting on a directed acyclic graph G = (V, E) is to repeatedly find a vertex of in-degree 0, output it, and remove it and all of its outgoing edges from the graph. Explain how to implement this idea so that it runs in time O(V + E). What happens to this algorithm if G has cycles?
首先,运行DFS或者是BFS可以在O(V+E)的时间内统计出每个点的入度和出度,以后在删除边的时候要维护这些信息. 每次输出入度为0的那个点并删除其出边,并维护信息,因此有E条边和V个点,所以要执行O(V)次输出和O(E)次的删除.所以总的运行时间是O(V+E)
如果图有回路,那么有时候可能没有入度为0的点.
Follow @louis1992 on github to help finish this task.