Clearly list strongly connected components in order of discovery and show clearl

Question

Clearly list strongly connected components in order of discovery and show clearly the algorithm used with clear explanation for good feedback thanks.

SCC Graph Theory: Please show full explanation and clear explanation for goodfeedback and full points thanks 5. (20 points) Graph a. (10 pts) Find the strongly connected component the strongly connected components of the following graph G. List all full points. strongly connected components in the order of discovery Show steps to earn b. (10 pts) Design an algorithm that adds fewest edges to G so that G contains a single connected component. Please provide an intuition first.

Explanation / Answer

a. A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.

Here to find ssc of a graph using Kosaraju's algorithm.

From the above graph,we have 3 strongly connected component. a-h-e-b-a,c-d-i-g-c,a-j-h-e-b-a

Next we need to find child of a-j,h,c child of b-a,c child of c-d child of d-i child of e-b

child of f-d,l child of g-c child of h-e child of i-g child of j-h child of l-0

Steps of Kosaraju's algorithm.

1. Do a DFS on the original graph, keeping track of the finish times of each node. This can be done with a stack, when some DFS finishes put the source vertex on the stack. This way node with highest finishing time will be on top of the stack.

2. Reverse the original graph, it can be done efficiently if data structure used to store the graph is an adjacency list.

3. Do DFSon the reversed graph, with the source vertex as the vertex on top of the stack. When DFS finishes, all nodes visited will form one Strongly Connected Component. If any more nodes remain unvisited, this means there are more Strongly Connected Component's, so pop vertices from top of the stack until a valid unvisited node is found. This will have the highest finishing time of all currently unvisited nodes.

Here we have to maintain visited queue and stack by finish time.

We starts from node b.it has child a which is not visited so we ll put it in visited queue:b,a

a has child j,c,h so put them in visited queue:b,a,j,c,h,e since e child of h.

Then we put them in stack by finish time:node e,b,a,j,h has no more children to explore so we put them in stack with an order of h,j,a,b,e.

Next we come to node c and d entry of visited queue:b,a,j,c,h,e,d,i,g

Stack by finish time:g,i,d,c,h,j,a,b,e

Then we reverse the graph and pop the nodes present in stack.

Here we pop nodes and put them in visited queue.1st popped node is g which has child i according to reverse oder.

so queue will be:gidc which is a scc graph

then g,i,d,c is popped from stack.

Remaining visited queue:g,i,d,c,a,b,e,h,j

also they pop d nodes:h,j,a,b,e so abehj is scc graph.

b.The number of strongly connected components can only decrease as the number of edges increase. If the edge is between two vertices that are already in the same strongly connected component, the number of components will not change. If the edge connects two vertices that belong to distinct scc’s, then the number of components will decrease by at most one.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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