C++中的鄰接列表實現

Question

我正在尋找C++中圖形的簡潔和精確的鄰接列表表示。我的節點只是節點ID。這是我如何做到的。只是想知道專家是怎麼想的。有沒有更好的辦法？

這是類實現（沒有什麼幻想，現在不關心公共/私有方法）

#include <iostream> 
#include <vector> 
#include <fstream> 
#include <sstream> 

using namespace std; 

class adjList { 
public: 
    int head; 
    vector<int> listOfNodes; 
    void print(); 
}; 

void adjList :: print() { 
    for (int i=0; i<listOfNodes.size(); ++i) { 
     cout << head << "-->" << listOfNodes.at(i) << endl; 
    } 
} 

class graph { 
public: 
    vector<adjList> list; 
    void print(); 
}; 

void graph :: print() { 
    for (int i=0; i<list.size(); ++i) { 
     list.at(i).print(); 
     cout << endl; 
    } 
} 

我的主要函數解析一行輸入文件行。每一行是解釋如下：

<source_node> <node1_connected_to_source_node> <node2_connected_to_source_node <node3_connected_to_source_node> <...> 

這裏是主要的：

int main() 
    { 
     fstream file("graph.txt", ios::in); 
     string line; 
     graph g; 
     while (getline(file, line)) { 
      int source; 
      stringstream str(line); 
      str >> source; 
      int node2; 
      adjList l; 
      l.head = source; 
      while (str >> node2) { 
       l.listOfNodes.push_back(node2); 
      } 
      g.list.push_back(l); 
     } 
     file.close(); 
     g.print(); 
     getchar(); 
     return 0; 
    } 

我知道我應該補充addEdge（）函數adjList類中，而不是從主直接修改它的變量（），但是，現在我只是想知道最好的結構。

編輯： 我的方法有一個缺點。對於具有大量節點的複雜圖形，節點確實是一個結構/類，在這種情況下，我將通過存儲整個對象來複制值。在那種情況下，我想我應該使用指針。例如，對於無向圖，我將在adjList中存儲節點對象的副本（節點1和2之間的連接意味着1的鄰接列表將有2個，反之亦然）。我可以通過將節點對象的指針存儲在adjList而不是整個對象中來避免這種情況。檢查通過這種方法獲益的dfs實現。我需要確保每個節點只被訪問一次。擁有同一節點的多個副本將會使我的生活更加艱難。沒有？

在這種情況下，我的類定義將改變這樣的：

#include <iostream> 
#include <vector> 
#include <fstream> 
#include <sstream> 
#include <map> 

using namespace std; 

class node { 
public: 
    node() {} 
    node(int id, bool _dirty): node_id(id), dirty(_dirty) {} 
    int node_id; 
    bool dirty; 
}; 

class adjList { 
public: 
    node *head; 
    vector<node*> listOfNodes; 
    void print(); 
    ~adjList() { delete head;} 
}; 

void adjList :: print() { 
    for (int i=0; i<listOfNodes.size(); ++i) { 
     cout << head->node_id << "-->" << listOfNodes.at(i)->node_id << endl; 
    } 
} 

class graph { 
public: 
    vector<adjList> list; 
    void print(); 
    void dfs(node *startNode); 
}; 

void graph::dfs(node *startNode) { 
    startNode->dirty = true; 
    for(int i=0; i<list.size(); ++i) { 
     node *stNode = list.at(i).head; 
     if (stNode->node_id != startNode->node_id) { continue;} 
     for (int j=0; j<list.at(i).listOfNodes.size(); ++j) { 
      if (!list.at(i).listOfNodes.at(j)->dirty) { 
       dfs(list.at(i).listOfNodes.at(j)); 
      } 
     } 
    } 
    cout << "Node: "<<startNode->node_id << endl; 
} 

void graph :: print() { 
    for (int i=0; i<list.size(); ++i) { 
     list.at(i).print(); 
     cout << endl; 
    } 
} 

這是我如何實現main（）函數。我正在使用地圖<>以避免重複對象。只有在前面沒有定義的時候才創建一個新對象。通過其ID檢查對象的存在。

int main() 
{ 
    fstream file("graph.txt", ios::in); 
    string line; 
    graph g; 
    node *startNode; 
    map<int, node*> nodeMap; 
    while (getline(file, line)) { 
     int source; 
     stringstream str(line); 
     str >> source; 
     int node2; 
     node *sourceNode; 
     // Create new node only if a node does not already exist 
     if (nodeMap.find(source) == nodeMap.end()) { 
       sourceNode = new node(source, false); 
       nodeMap[source] = sourceNode; 
     } else { 
       sourceNode = nodeMap[source]; 
     } 
     adjList l; 
     l.head = sourceNode; 
     nodeMap[source] = sourceNode; 
     while (str >> node2) { 
      // Create new node only if a node does not already exist 
      node *secNode; 
      if (nodeMap.find(node2) == nodeMap.end()) { 
       secNode = new node(node2, false); 
       nodeMap[node2] = secNode; 
      } else { 
       secNode = nodeMap[node2]; 
      } 
      l.listOfNodes.push_back(secNode); 
     } 
     g.list.push_back(l); 
     startNode = sourceNode; 
    } 
    file.close(); 
    g.print(); 
    g.dfs(startNode); 
    getchar(); 
    return 0; 
} 

第二個編輯 後烏爾裏希·埃克哈特建議把在節點類鄰接表，這裏是我認爲這是一個更好的數據結構來存儲圖形並進行DFS（），Dijkstra算法（）種的操作。請注意，鄰接表在節點類中被合併。

#include <iostream> 
#include <vector> 
#include <fstream> 
#include <sstream> 
#include <map> 

using namespace std; 

class node { 
public: 
    node() { 
    } 
    node(int id, bool _dirty): node_id(id), dirty(_dirty) { 
     //cout << "In overloaded const\n"; 
    } 
    int node_id; 
    bool dirty; 
    vector<node*> listOfNodes; 
}; 

class graph { 
public: 
    vector<node*> myGraph; 
    void dfs(node* startNode); 
}; 

void graph::dfs(node* startNode) { 
    startNode->dirty = true; 
    for (int j=0; j<startNode->listOfNodes.size(); ++j) { 
      if (!startNode->listOfNodes.at(j)->dirty) { 
       dfs(startNode->listOfNodes.at(j)); 
      } 
     } 

    cout << "Node: "<<startNode->node_id << endl; 
} 

我們可以做得比這更好嗎？

Answer 1

有幾件事情可以改進，但一般來說你的方法是合理的。注：

• 您正在使用int爲索引到一個容器，它會給你一些編譯器警告，因爲容器的大小可能會超過大小可表示爲int。相反，使用size_t。
• 將您的for (int i=0; i<list.size(); ++i)重寫爲for(size_t i=0, size=list.size(); i!=size; ++i)。使用!=而不是<將與迭代器一起使用。讀取和存儲一次的大小可以更容易地進行調試，甚至可能更高效。
• 在打印循環內，您有list.at(i).print();。 list.at(i)將驗證索引是否有效，如果不是，則引發異常。在這個非常簡單的情況下，我確信索引是有效的，所以使用list[i]代替速度更快。此外，它隱含地記錄索引是有效的，而不是你期望它是無效的。
• print()函數應該是不變的。
• 我不明白int head是什麼。這是節點的某種ID嗎？並不是ID簡單地在graph::list裏面的索引？如果它是索引，則可以使用元素的地址減去第一個元素的地址按需計算，因此不需要冗餘存儲。另外，考慮在讀取時驗證該索引，所以您沒有任何邊緣到達不存在的頂點。
• 如果你不關心封裝在節點級別（這是合理的！），你也可以把它作爲一個結構，這可以節省一些輸入。
• 存儲指針而不是索引是棘手的，但可以提高速度。問題是，對於閱讀，你可能需要一個指向尚不存在的頂點的指針。有一種黑客可以在不使用額外存儲的情況下執行此操作，它需要先將索引存儲在指針值中（使用reinterpret_cast），然後再讀取數據，然後再將數據調整爲實際地址。當然，你也可以使用第二遍來驗證你沒有任何邊緣到達根本不存在的頂點（這是at(i)函數變得有用的地方），所以這第二遍驗證了一些保證無論如何，這是件好事。

上明確要求，下面是如何索引存儲在一個指針的例子：

// read file 
for(...) { 
    size_t id = read_id_from_file(); 
    node* node_ptr = reinterpret_cast<node*>(id); 
    adjacency_list.push_back(node_ptr); 
} 

/* Note that at this point, you do have node* that don't contain 
valid addresses but just the IDs of the nodes they should finally 
point to, so you must not use these pointers! */ 

// make another pass over all nodes after reading the file 
for(size_t i=0, size=adjacency_list.size(); i!=size; ++i) { 
    // read ID from adjacency list 
    node* node_ptr = adjacency_list[i]; 
    size_t id = reinterpret_cast<size_t>(node_ptr); 
    // convert ID to actual address 
    node_ptr = lookup_node_by_id(id); 
    if(!node_ptr) 
     throw std::runtime_error("unknown node ID in adjacency list"); 
    // store actual node address in adjacency list 
    adjacency_list[i] = node_ptr; 
} 

我敢肯定，這部作品在一般情況下，雖然我不是100％肯定，如果這是保證工作，這就是爲什麼我不願意在這裏發表。不過，我希望這也能明白爲什麼我要問究竟「頭」是什麼。如果它實際上只是一個容器中的索引，則不需要它，既不在文件內，也不在內存中。如果它是從某個文件中檢索到的節點的某種名稱或標識符，那麼您絕對需要它，但不能將其用作索引，那裏的值也可以使用1或1000開始其ID，你應該捕捉並處理而不會崩潰！