In C++ , display the following graphs as an acyclic component graph using the al

Question

In C++, display the following graphs as an acyclic component graph using the algorithm described below

1. Call Depth First Search on the graph G (DFS(G)) to compute time stamp (start, finish) for each vertex in the graph

2. Compute the transpose of the graph G with a set of vertices V and edges E. The transpose of the graph G(V, E) is defined as the graph GT (V, ET ), where ET = {(v, u) : (u, v) ? E}. That is, ET consists of the edges of G with their directions reversed.

3. Call DFS(GT ), and run the vertices in order of decreasing finishing times as computed in step 1.

4. All the vertices reached from a given vertex selected in step 3 form one strongly connected component.

Explanation / Answer

import java.util.InputMismatchException; import java.util.Scanner; import java.util.Stack; public class DFS { private Stack stack; public DFS() { stack = new Stack(); } public void dfs(int adjacency_matrix[][], int source) { int number_of_nodes = adjacency_matrix[source].length - 1; int visited[] = new int[number_of_nodes + 1]; int element = source; int i = source; System.out.print(element + " "); visited[source] = 1; stack.push(source); while (!stack.isEmpty()) { element = stack.peek(); i = element; while (i

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---