關於如何接近有向圖的想法

Question

我正在嘗試使用有向圖（我知道但從未實現過）來模擬運輸網絡來編寫程序。

用戶將輸入一個行星名稱，後跟一個表示圖形中總節點數量的整數。然後用戶將逐一瀏覽每個節點。他們會給它一個名字，給出節點所擁有的鄰居數量，然後給出具體名稱。輸入將如下所示。

some_planet 4 
node1 2 node2 node3 
node2 1 node4 
node3 1 node4 
node4 1 node1 

然後我只輸出node1無法到達的節點。但是，我有一些關於實現這個問題的問題。

1）最重要的是存儲這些東西。什麼是簡單的方法？我想到一個LinkedList，並認爲我會鏈接位置。然後，我可以將指針彈出到與它相對應的任何輸入。但是，我不知道如何做最後一部分。

2）下一個大搜索圖表。我正計劃進行遞歸深度優先搜索。你看到這個算法有什麼問題嗎？我需要以這種方式分別搜索每個節點，但是我必須增加這個。我可以把所有東西都放在for循環中嗎？

recursive-d-first-search(graph G, node start, node find) 
    if(start == find) 
    return true; 

    else 
    for every neighbor n of start 
     success = recursive-d-first-search(graph G, node n, node find); 
     if(success) 
     return true; 

    return false; 

Answer 1

1. 我想你只需要使用鄰接矩陣來存儲整個圖形的連接關係。 在你的情況下，它應該是這樣的：

   1 2 3 4 
   
   1 0 1 1 0 
   
   2 0 0 0 1 
   
   3 0 0 0 1 
   
   4 1 0 0 0 
   

2. 如果使用鄰接矩陣，我覺得breadth-first search可能是一個不錯的選擇，因爲它很容易理解和執行。同時，您需要一個隊列來存儲要檢查的下一個節點，以及一個列表來存儲已檢查哪些節點。

   例如，要檢查node1無法到達的節點，只需檢查第1行並查看它有2和3，並把2和3排隊。然後檢查行2以查看它有4，將2列出，並將4放入隊列。然後使用for循環來執行相同的操作。

   最後，你只需要檢查哪些節點不在列表中。

Answer 2

您也可以使用Boost::Graph，如果你不喜歡重新發明輪子...