Appreciate a step by step explanation with code for this problem. In this proble

Question

Appreciate a step by step explanation with code for this problem.

In this problem you will implement a linear time strongly connected components algorithm, like Tarian's or Kosaraju s Algorithm using Python. Given an undirected graph G you first create the reverse graph GE in linear time. Next, you run an undirected connected components method processing the vertices in decreasing post order. This method utilizes a depth-first search is trivially adapted to check if a graph is connected and, more generally, to assign each node v an integer ccnumlv identifying the connected component to which it belongs.Its pseudocode can be shown as: procedure previsit(v) where cc needs to be initialized to zero and to be incremented each time the DFS procedure searches the graph. The overall program should be carried out in OIV+E time. Vis #of vertices and E is of edges. The Python script should read the graph file name from the command line. Each line of the graph file will have two integers representing a direpted edge from u to v The code should output all strongly connected components.

Explanation / Answer

algorithm tarjan is input: graph G = (V, E) output: set of strongly connected components (sets of vertices) index := 0 S := empty for each v in V do if (v.index is undefined) then strongconnect(v) end if end for function strongconnect(v) // Set the depth index for v to the smallest unused index v.index := index v.lowlink := index index := index + 1 S.push(v) // Consider successors of v for each (v, w) in E do if (w.index is undefined) then // Successor w has not yet been visited; recurse on it strongconnect(w) v.lowlink := min(v.lowlink, w.lowlink) else if (w is in S) then // Successor w is in stack S and hence in the current SCC v.lowlink := min(v.lowlink, w.index) end if end for // If v is a root node, pop the stack and generate an SCC if (v.lowlink = v.index) then start a new strongly connected component repeat w := S.pop() add w to current strongly connected component until (w = v) output the current strongly connected component end if end function

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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