You run the strongly connected components algorithm on the following graph You r

Question

You run the strongly connected components algorithm on the following graph

You run the strongly connected components algorithm on the following graph. Assume that all ties are broken alphabetically (in DFS, for instance). Show the components you get, in the order you get them, along with all relevant work. Show the final underlying component graph. The graph is given in adjacency matrix format.

Explanation / Answer

import java.util.HashMap; import java.util.InputMismatchException; import java.util.Map; import java.util.Scanner; import java.util.Stack; public class StrongConnectedComponents { private int leader = 0; private int[] leader_node; private int explore[]; private int finishing_time_of_node[]; private int finishing_time = 1; private int number_of_nodes; private Stack stack; private Map finishing_time_map; public StrongConnectedComponents(int number_of_nodes) { this.number_of_nodes = number_of_nodes; leader_node = new int[number_of_nodes + 1]; explore = new int[number_of_nodes + 1]; finishing_time_of_node = new int[number_of_nodes + 1]; stack = new Stack(); finishing_time_map = new HashMap(); } public void strongConnectedComponent(int adjacency_matrix[][]) { for (int i = number_of_nodes; i > 0; i--) { if (explore[i] == 0) { dfs_1(adjacency_matrix, i); } } int rev_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1]; for (int i = 1; i

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.