DFS强烈连接组件的困境(DFS strongly connected components dilemma)

DFS强烈连接组件的困境(DFS strongly connected components dilemma)

问题：将问题1中图的顶点集合分解为强连通分量（SCC）。 也就是说，指定第一个强连通组件中的哪些顶点，以及第二个等等。

是否有人能够确认我已正确完成此操作？ 即当我到达顶点4时，我可以选择使第一个SCC为1,7,2,4,3（如图所示）或1,7,2,4,6,5，这取决于我选择哪种方式旅行。 有没有这方法，或者我可以简单地选择？

订购：

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

SCC：

1,7,2,4,3

五

8

6

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?

order:

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

SCC:

1,7,2,4,3

5

8

6

最满意答案

强连通的组件是{1,2,3,4,5,6,7}。 如果你没有得到，你的算法（或你的实现）有一个错误。 有一个强连通组件的定义，以及一些众所周知的算法; 在维基百科（以及许多其他互联网资源）中都可以轻松找到这两种文本，并且很可能在您的教科书和/或课程笔记中找到。 （如果你没有课程笔记，你很容易找到类似课程的一些。）

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.)