實現圖形ADT在C++中

Question

我想實現圖形ADT在C++中這裏是代碼

#include <iostream> 
using namespace std; 
struct Edge{ 

    int v,w; 
    Edge(int t=-1,int k=-1):v(t),w(k){} 

}; 
class Graph { 

public: 
    Graph(int,bool); 
    ~Graph(); 
    int V() const; 
    int E() const; 
    bool directed() const; 
    int remove(Edge); 
    int insert(Edge); 
    bool edge(int,int); 
     class AdjIterator{ 

      public: 
AdjIterator(const Graph&,int); 
       int beg(); 
       int nxt(); 
       bool end(); 


     }; 


}; 
int main(){ 




    return 0; 


} 

有多好是根據代碼性能的這種實現的？ 編輯： 我已經加入此代碼

template<class Graph> 
vector<Edge> edge(Graph& G){ 
    int E=0; 
    vector<Edge>a(G.E()); 
     for (int v=0;v<G.V();v++){ 
      typename Graph::AdjIterator A(G,v); 
      for (int w=A.beg();w!=A.end();w=A.nxt()) 
       if (G.directed() || v<w) 
    a[E++]=Edge(v,w); 

     } 

     return a; 
} 

Answer 1

沒有多少你展示這些代碼，只是接口的實現。

表示圖形的另一種主要方式是通過adjacency matrix。

哪種方式表示圖更好取決於您的應用程序。

Answer 2

有幾種表示圖的方法。

1. 鄰接表
2. 鄰接矩陣
3. 邊列表（這是您的實現似乎什麼來定）。

實現的選擇實際上取決於你將要使用它的方式。鄰域列表對於稀疏圖非常快速且緊湊，並且通常被大多數算法優選。鄰接矩陣通常更容易實現，並且一些算法（如Flowd-Warshall都配對最短路徑算法）需要它。當你需要的只是邊緣時，邊緣列表是有用的。在使用Kruskal算法的實現中。

很難說這個特定的實現是否適合您的目的，而不知道它將用於什麼目的。