9

私はグラフ理論を始めたばかりです。リンクされたリストを使用して隣接リストをコーディングする方法がわかりません。たとえば、このグラフ (無向) があるとします。

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

どのようにコーディングするのですか？隣接行列を使用してそれを行う方法は知っていますが、隣接リストと連結リスト (c++) を使用してコーディングする方法は?

4

3 に答える 3

14

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

A -> {B, C}

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

C -> {A、B}

D -> {B, E}

E -> {B, D}

のようなものから始めstd::vector<std::list<vertex>>ます。ただし、頂点は一意であるため、これよりもうまくいく可能性がありmapます。さらに、頂点はエッジ リストに 1 回しか表示されないため、 に変更し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
    //...
 };
于 2013-01-03T04:51:42.293 に答える
3

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

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;

これを行うには多くの方法があります。グラフで何をしようとしているのかを知らずに、これ以上何かを提案することは困難です。

于 2013-01-03T04:44:14.233 に答える