import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
class DepthFirstOrder {
private boolean[] visited; // visited[v] = true if v connected to s
private Stack reversePost; // all vertices in reverse DFS porst order
public DepthFirstOrder(Digraph G) {
// initialize data structures
this.visited = new boolean[G.V()];
this.reversePost = new Stack<>();
for(int v = 0; v < G.V(); v++) {
if(!visited[v]) {
dfs(G, v);
}
}
}
// is there a path from s to v?
public boolean isVisited(int v) {
return visited[v];
}
private void dfs(Digraph G, int v) {
// recursive DFS does the work
visited[v] = true;
for (int w : G.adj(v))
if(!visited[w])
dfs(G, w);
reversePost.push(v);
}
/** returns all vertices in “reverse DFS postorder” */
public Stack reversePost() {
return reversePost;
}
private static Digraph prepareGraph() {
int[][] edges = new int[][] {
{0, 5}, {0, 2},
{0, 1}, {3, 6},
{3, 5}, {3, 4},
{5, 2}, {6, 4},
{6, 0}, {3, 2},
{1, 4}
};
Digraph G = new Digraph(7);
// add all edges
for(int i = 0; i < edges.length; i++) {
int v = edges[i][0];
int w = edges[i][1];
G.addEdge(v, w);
}
return G;
}
static class Digraph {
private final int V; // number of vertices
private final List[] adj; // adjacency lists... 0 to V-1
/** create an empty digraph with V vertices */
public Digraph(int V) {
this.V = V;
this.adj = new ArrayList[V]; // create empty graph with V vertices
for(int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
/** add a directed edge v→w */
public void addEdge(int v, int w) {
// add edge v-w
adj[v].add(w);
}
/** Iterator for vertices pointing from v */
public Iterable adj(int v) {
return adj[v];
}
/** number of vertices */
public int V() {
return V;
}
/** number of edges */
public int E() {
int countEdges = 0;
for(int v = 0; v < V; v++) {
countEdges += adj[v].size();
}
return countEdges;
}
/** reverse of this digraph */
Digraph reverse() {
return null;// TODO
}
/** string representation */
public String toString() {
return "TODO";
}
}
public static void main (String[] args) {
System.out.println("Find port order and topological order ");
Digraph G = prepareGraph();
System.out.println("V: " + G.V());
System.out.println("E: " + G.E());
DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
Stack postOrder = depthFirstOrder.reversePost();
Stack reverse = new Stack<>();
System.out.print("topological order :");
while(!postOrder.isEmpty()) {
int i = postOrder.pop();
System.out.print(i + ", ");
reverse.push(i);
}
System.out.print("\nPost order :");
while(!reverse.isEmpty()) {
System.out.print(reverse.pop() + ", ");
}
}
}
Find port order and topological order
V: 7
E: 11
topological order :3, 6, 0, 1, 4, 5, 2,
Post order :2, 5, 4, 1, 0, 6, 3,
Comments
Post a Comment