我试图找出有一种方法可以在 adj 矩阵图中找到最大的连通分量。比如这样:
0000000110
0001100000
0000000000
0100000010
0100000100
0000000100
0000000000
1000110000
1001000000
0000000000
我用 Google 搜索了这个问题,但一直在努力寻找任何东西,我还阅读了关于图论的 wiki 文章,但没有任何乐趣。我认为他们一定是解决这个问题的算法。任何人都可以指出我正确的方向,并给我一些建议,告诉我应该怎么做才能自己解决这个问题吗?
最佳答案
应用连通分量算法。
对于无向图,只需选择一个节点并进行广度优先搜索。如果在第一个 BFS 之后还有剩余的节点,则选择一个剩余的节点并进行另一个 BFS。 (每个 BFS 都有一个连通分量。)
请注意,有向图需要稍微强大的算法才能找到强连通 组件。 Kosaraju 的算法浮现在脑海中。
计算 (1) 中每个连通分量中的节点数。选择最大的一个。
关于java - 在 adj 矩阵图中找到最大的连通分量?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10392605/