在这个非定向图中，我如何从一个组件跳转到另一个组件？

Question

自从远程学习这件事开始后，我真的很难理解数据结构，这个问题真的让我大跌眼镜。我完全不知道如何从代码开始，更不用说把我的观点表达出来了。任何帮助都会非常感激......

Answer 1

在图中选择任意一个节点。那个节点属于某个组件，它和其他一些潜在的节点一起在那里。所以运行一个BFS，把那个节点和所有可以到达的节点都刷成金色。这就是一个组件。

现在选择另一个节点。有两件事必须是真的。首先，可能是这个节点已经被涂成了金色。在这种情况下，你已经算出了包含它的组件。第二，它可能是未涂色的。在这种情况下，你还没有计算它的组件，所以把它和所有从它那里可以到达的节点涂成金色，这就是你的第二个组件。

你觉得你能不能把这个想法推广开来，让你把所有的组件都算进去？

至于运行时间--这样每个节点会被访问多少次？请记住，你只给每个节点刷一次金，而且每个边缘只在课程或刷节点的过程中被访问。