網絡與圖論問題

您有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

回答