2

輸送ネットワークをシミュレートするために、有向グラフ (私は知っていますが、実装したことはありません) を使用してプログラムを作成しようとしています。

ユーザーは惑星名を入力し、その後にグラフ内の合計ノード数を表す整数を入力します。次に、ユーザーは各ノードを 1 つずつ調べます。ノードが持つネイバーの数と特定の名前を指定して名前を付けます。入力は次のようになります。

some_planet 4
node1 2 node2 node3
node2 1 node4
node3 1 node4
node4 1 node1

次に、node1 が到達できないノードを出力します。ただし、これを実装するにはいくつかの質問があります。

1) 大きい方がこれを収納しています。簡単な方法とは？私は LinkedList について考え、場所をリンクしようと考えました。次に、入力が何であれ、それらに対応するポインターをポップできます。ただし、最後の部分を行う方法がわかりません。

2) 次の大きな問題は、グラフの検索です。再帰的な depth-first-search を計画していました。このアルゴリズムに問題はありますか? ただし、この方法ですべてのノードを個別に検索する必要があるため、これをインクリメントする必要があります。すべてを for ループに入れることはできますか?

recursive-d-first-search(graph G, node start, node find)
  if(start == find)
    return true;

  else
    for every neighbor n of start
      success = recursive-d-first-search(graph G, node n, node find);
      if(success)
        return true;

  return false;
4

2 に答える 2

2

  1. グラフ全体の接続関係を格納するには、隣接行列を使用する必要があると思います。あなたの場合、それは次のようになります：

        1    2    3    4

1   0    1    1    0

2   0    0    0    1

3   0    0    0    1

4   1    0    0    0

  2. breadth-first search隣接行列を使用する場合は、理解と実装が簡単なので、が良い選択かもしれないと思います。一方、チェックする次のノードを格納するための1つのキューと、すでにチェックされているノードを格納するための1つのリストが必要です。

    たとえば、node1到達できないノードを確認したい場合は、行1を確認して、行1にとがあることを確認し2、キュー3に入れ2て3キューに入れます。次に、行をチェックして、行があり、リストに入れられ、キューに入れられ2ていることを確認します。次に、forループを使用して同じ操作を実行します。424

    最後に、リストにないノードを確認する必要があります。

于 2012-12-07T03:44:02.387 に答える
1

車輪を再発明したくない場合は、Boost::Graphを使用することもできます...

于 2013-01-09T00:06:03.407 に答える