0

単純な隣接リストを実装しようとしています。配列のインデックスがその時点での頂点のキーであることを理解しています。

例：フォーマットのエッジがある場合:(開始、終了、コスト）（1,2,4）（2,3,5）（1,3,27）（3,4,8）

私は次のような配列を持っているでしょう

[0]-> null

[1]-> 2 | 4-> 3 | 27-> null

[2]-> 3 | 5-> null

[3]-> 4 | 8-> null

1つの問題は、エッジを保持するコンテナにはポインタがありますが、それらに挿入された要素（エッジ）にはないということです。道に迷いました。

コメントにコードを入れる方法がわからないので、この投稿を編集します。

struct Node{
       Edge *head;
       Node *next;
}

Node *root;

void adjacencyList::insert(const Edge &edge)
{

  if(root == NULL)
   {
      root = new Node;
      root->head = edge;
    }
  else
    {
      while(root != NULL)
        {          
          root = root->next;
          if(root == NULL);
          {
            root = new Node;
            root->head = edge;
            root = root ->next;

          }
        }
     }
}

エッジオブジェクトには3つのプロパティ（ソース、宛先、コスト）があります。現在、これはリンクリストにエッジを追加し続けるだけです。リストをソースごとに分けるにはどうすればよいですか？

4

1 に答える 1

2

隣接リストはリンクリストである必要はありません。たとえそうであったとしても、（侵入的な）リンクリストを自分で実装するのではなく、既存の実装を使用してください。

しかし、ここに行きます。（ノード、コスト）ペアのベクトルを持っているだけです：

typedef std::pair<int, int> weighted_node_t;
typedef std::vector<std::vector<weighted_node_t>> graph_t;

次に、グラフを次のように表すことができます（C ++ 11初期化構文を使用）。

graph_t graph{
    {},
    {{2, 4}, {3, 27}},
    {{3, 5}},
    {{4, 8}}
};

ここで、グラフをトラバースしたいとします（深さ優先探索）。次のようにします（ここでも、よりクリーンなため、C ++ 11構文）。

void dfs(graph_t const& graph, std::vector<bool>& visited, int node) {
    visited[node] = true;
    for (auto const& neighbor : graph[node])
        if (not visited[neighbor])
            dfs(graph, visited, neighbor.first);
}

そしてそれをこのように呼んでください：

std::vector<bool> visited(graph.size());
dfs(graph, visited, 1);
于 2013-03-24T17:59:06.250 に答える