网络与图论问题

您有N台计算机，[Ca，Cb]表示a连接到b，并且此连接是对称和传递的。问题是编写一个程序检查所有计算机是否互相连接并互相通话。网络与图论问题

时间有效的算法是优选的。

2010-01-15 SIVA

您应该将此作为家庭作业 – 2010-01-15 14:46:47

@Tristram：我为他标记了“可能 - 作业”...... – 2010-01-15 14:54:50

@SIVA，你已经做了什么来解决这个问题，以及你对你的解决方案有什么问题？ – atk 2010-01-15 17:48:16

这叫做Graph Connectivity。阅读有关它，你可以解决你的问题。

2010-01-15 14:40:56

对多次不遍历节点的图的任何搜索都应该足够。有很多选择： http://www.algorithmist.com/index.php/Graph_Connectivity 我可能会选择DFS或BFS。

2010-01-15 14:46:28

，因为你说一个时间有效的算法是preferable.thus DFS为U..notice最好的算法在网络计算机的边缘是尺寸小 DFS： http://en.wikipedia.org/wiki/Depth-first_search

2012-04-18 13:47:35

注意：网络电脑的边缘大小很小 – 2012-04-18 16:47:47

回答