C++圖形implemation

Question

可能重複：
Graph implementation C++

嗨

我想知道一個快速的寫在C實現圖形的++。我需要數據結構易於操作和使用圖算法（如BFS，DFS，Kruskal，Dijkstra ...）。 我需要一個算法奧林匹克這個實現，所以編寫數據結構越容易越好。

你可以提出這樣的DS（主要結構或類，以及它們中的內容）。我知道鄰接列表和鄰接矩陣是主要的可能性，但我的意思是更詳細的代碼樣本。

例如，我想了解這個DS上次我不得不實施DFS的曲線圖：

struct Edge { 
    int start; 
    int end; 
    struct Edge* nextEdge; 
} 

，然後用於大小爲n的在其第i代替含有邊緣列表中的一個陣列（結構邊緣）表示從第i個節點開始的邊。

但是當試圖在這個圖上的DFS時，我不得不寫一個50行的代碼，並且有大約10個while循環。

有什麼'好'的實現？

Answer 1

而不是維護邊緣內的nextEdge列表，你應該分別實現它們。

struct Edge 
{ 
int start; 
int end; 
}; 

由於您使用C++和它是一個奧林匹克競賽，更好地利用一切STL所提供的。

因此，將邊緣存儲在矢量內。這對迭代Edges而不是節點的算法會有幫助。

如果您需要遍歷從節點到節點（BFS，DFS），最好維護一個鄰接列表。

再次使用一個矢量數組來達到此目的。

vector<int> adj[MAXNODE];