- Transitive Closure: a directed graph G∗, which has the same vertices of G, and has an edge (u, v) whenever G has a directed path from u to v.
- If a graph is represented as an adjacency list or adjacency map, O(n(n + m)) by graph traversals, i.e. DFS
- Transitive closure supports O(1) time lookup
Floyd-Warshall algorithm
- compute the tranitive closure of G that is based on the series of rounds to compute each Gk.
- start with Gk = G(k−1)
- add to Gk the directed edge (vi,vj) if directed graph Gk−1 contains both the edges (vi,vk) and (vk,vj).
- O(n3) running time
- suited for the use of an adjacency matrix, where a single bit can be used to designate the reachability
Input: A directed graph G with n vertices Output: The transitive closure G∗ of G let v1,v2,..., vn be an arbitrary numbering of the vertices of G G0 = G for k = 1 to n do Gk = G(k-1) for all i, j in {1,...,n} with i! = j && i,j != k do if both edges (vi,vk) and (vk,vj) are in G(k−1) then add edge (vi,vj) to Gk return GnJava Implementation
- directly modify the original graph, repeatedly adding new edges to the closure
public class FloydWarshall { public static <V, E> void transitiveClosure(Graph<V, E> g) { for (Vertex<V> k : g.vertices()) { for (Vertex<V> i : g.vertices()) { if (i != k && g.getEdge(i, k) != null) { for (Vertex<V> j : g.vertices()) { if (j != i && j != k && g.getEdge(k, j) != null) { if (g.getEdge(i, j) == null) g.insertEdge(i, j, null); } } } } } }
近期评论