隣接リストグラフ表現の実装

Question

私はグラフ理論から始めました。私はリンクリストを使って隣接リストをコード化する方法を理解できません。たとえば、私がこのグラフを持っている場合（無向）：

A--------B 
|  /|\ 
| /| \ 
| /| \ 
| / | \ 
| / | \ 
|/ |  \ 
|/ |  \ 
C  E-------D 

どうすればいいですか？私は隣接行列を使ってそれを行う方法を知っていますが、隣接リストとリンクリスト（C++）を使ってコードする方法はありますか？

Answer 1

隣接リストは単なるリストのベクトル/アレイです。グラフの各要素は配列内の要素であり、隣接リストにエッジが追加されます。したがって、のように見える：

A - > {B、C}を

B - > {A、C、D、E}

C - > {A、B}

D - > {B、E}

E - > {B、D}

だから我々はstd::vector<std::list<vertex>>のようなもので始まります。しかし、頂点は一意であるため、これよりもうまくいくので、mapを利用することができます。さらに、頂点はエッジリストに一度しか表示されないため、std::map<vertex, std::set<vertex>>に変更します。

だから、とのようなものを開始します

struct vertex 
{ 
    // 
}; 

class undirected_graph 
{ 
private: 
    std::map<vertex, std::set<vertex>> graph_container; 
public: 
    void add_vertex(const vertex& v) { //add a vertex to the map } 
    void add_edge(const vertex& v, const vertex& u) { //look up vertex in map and add to the vertex adjacency list } 
    //Other methods 
    //... 
}; 

Answer 2

隣接リストは、グラフのエッジを表す一連のオブジェクトに過ぎません。

struct edge { 
    node *nodes[2]; 

    edge(node *a, node *b) { 
     if (a < b) { // define canonical order of edges for undirected graph 
      nodes[0] = a; 
      nodes[1] = b; 
     } else { 
      nodes[0] = b; 
      nodes[1] = a; 
     } 
    } 
}; 

リンクリストは特に実用的ではありません。通常、エッジの順序を定義し、std::setまたはstd::mapに入れます。

bool operator< (edge const &lhs, edge const &rhs) { 
    if (lhs.nodes[0] < rhs.nodes[0]) return true; 
    if (rhs.nodes[0] < lhs.nodes[0]) return false; 
    return lhs.nodes[1] < rhs.nodes[1]; 
} 

typedef std::set<edge> graph; 

これを行うには多くの方法がありますが、それはあなたがグラフをどうするつもり何を知らなくても、より多くの何を示唆するのは難しいです。