algorithmgraphdepth-first-searchstrongly-connected-graph

DFS strongly connected components dilemma


Question: Divide the set of vertices of the graph in Problem 1 into strongly connected components (SCC). Namely, specify which vertices are in the first strongly connected component, which in the second, and so on.

is any one able to confirm ive done this correctly? namely when i reach vertex 4 i have the option to make the first SCC either 1,7,2,4,3 (as shown) or 1,7,2,4,6,5 depending on which way i choose to travel. Is there a method to this, or can i simply just choose?

enter image description here

order:

1,2,7,3,4,5,8,6

SCC:

1,7,2,4,3

5

8

6


Solution

  • The strongly connected component is {1,2,3,4,5,6,7}. If you don't get that, your algorithm (or your implementation) has a bug. There is a definition of Strongly Connected Component, and several well-known algorithms; both can be found easily in Wikipedia (and many other internet resources) and, most likely, in your textbook and/or course notes. (If you don't have course notes, you'll easily find some for similar courses.)