|
Size: 3943
Comment:
|
Size: 2096
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 49: | Line 49: |
| === Topological Sort === '''Definition''' 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.) '''Theorem (Topological Sort Correctness)''' Topologoical-Sort(G) produces a topological sort of a DAG G. '''Proof''' Suppose that DFS is run on a given DAG G=(V,E) to determin finish times for its vertices. It suffices to show that for any pair of distinct vertices u,v∈V, if there is an edge in G from u to v, then f[v]<f[u]. Consider edge (u,v) explored by DFS(G). When this edge is explored, v cannot be gray, since then v would be an ancestor of u and (u,v) would be a back edge, contradicting that this is a DAG (Theorem DAG No Back Edges). Therefore, v must be either white or black. If v is white, it becomes a descendent of u and so f[v]<f[u]. If v is black, it has already been finished, so that f[v] has already been set. Since we are still exploring from u we have not set a timestamp for f[u] and thus f[v]<f[u]. Thus for any edge (u,v) in a DAG, we have f[v]<f[u]. (EOP) === Strongly Connected Components === '''Definition (StronglyConnectedComponents)''' A strongly connected component of a directed graph G=(V,E) is a maximal set of vertices C⊆V such that ∀u,v∈C, we have both u--->v and v--->u. (---> signifies a path) '''Algorithm (FindingStronglyConnectedComponents)''' Strongly-Connected-Components(G) 1. call DFS(G) to compute finishing times f[u] for each vertex u 1. compute G^{T} 1. call DFS(G^{T}), but in the main loop of DFS, consider the vertices in order of decreasing f[u] (as computed in line 1) 1. output the vertices of each tree in the depth-first forest formed in line 3 as separte strongly connected components. attachment:SCC.jpg |
* TopologicallySortingDag * StronglyConnectComponents |
Depth First Search
DFS(G)
for each vertex u∈V[G]
- do color[u]=white
- [u]=nil
- time=0
for each certex u∈V[G]
- do if color[u]=white
- then DFS-Visit(u)
DFS-Visit(u)
- color[u]=gray
- time=time+1
- discover[u]=time
for each v∈Adj[u] //explore edges
- do if color[v]=white
- then [v]=u
- DFS-Visit(v)
- color[u]=black
- time++
- finish[u]=time
- These could be easily combined into an algorithm that uses a stack.
Properties
- DFS may result in different trees based on the order in which adjacent verticies are visited, but this will not change the effectiveness of the results.
Running Time (V+E)
- The Predecessor subgraph forms a depth-first forest composed of several depth-first trees.
Theorems and Definitions
Theorem The start and finish times of each vertex visited expresses a correctly formed parenthesis structure. That is if (v...(u, then u)...v) where left parenthesis denotes discovery time and right parenthesis denotes finish time.
Definition We can classify edges based on the DFS forest G_{}
Tree edges are edges in the depth-first forest G_{}. Edge (u,v)∈Tree-Edge if v was first discovered while exploring (u,v)
- Back edges are those edges (u,v) connecting vertex u to an ancestor v. Self loops are considered back edges.
- Forward Edges are those nontree edges (u,v) connecting a vertex u to a descendent v.
- Cross edges are all other edges. They can go between vertices in the same DFT as long as one vertex is not an ancestor of the other, or they can go between vertices in two different DFTs in the same forest.
We can always redraw a graph such that all forward and tree edges go down and all back edges go up.
Theorem (Theorem DAG No Back Edges) A directed graph is acyclic iff a depth-first search yields no "back" edges.