实现图形ADT在C++中

c++
graph

2010-09-18 39 views -1 likes

-1

我想实现图形ADT在C++中这里是代码实现图形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; 
}

来源

2010-09-18 user466444

@ user444288：我想，您需要描述更多或为我们添加更多代码来检查它的性能。 – bjskishore123 2010-09-18 10:46:04

回答

~~没有多少你展示这些代码，只是接口的实现。~~

表示图形的另一种主要方式是通过adjacency matrix。

哪种方式表示图更好取决于您的应用程序。

来源

2010-09-18 10:43:49

有几种表示图的方法。

邻接表
邻接矩阵
边列表（这是您的实现似乎什么来定）。

实现的选择实际上取决于你将要使用它的方式。邻域列表对于稀疏图非常快速且紧凑，并且通常被大多数算法优选。邻接矩阵通常更容易实现，并且一些算法（如Flowd-Warshall都配对最短路径算法）需要它。当你需要的只是边缘时，边缘列表是有用的。在使用Kruskal算法的实现中。

很难说这个特定的实现是否适合您的目的，而不知道它将用于什么目的。

来源

2010-09-18 11:09:58 MAK

实现图形ADT在C++中

回答

相关问题