9

グラフを操作してコードを書き込もうとしたときに問題が発生しましたが、うまくいきませんでした:/ !!

グラフのデータを取得して、それが次のようになっているかどうかを確認するものを作成したかったのです。

たとえば、上記のテストを実行する.txtファイルからグラフデータを読み取るためにこれを書き込むことができるかどうか疑問に思っていました??

シンプルなエッジリスト形式を使用するのが正しいアプローチですか?

このタスクの実行方法やコードのキック スタートについて読むためのリンクを教えていただければ助かります。

ありがとう

4

1 に答える 1

25

それが次のとおりかどうかを確認します。

  1. 接続済み

この例では、1 つのポイントからグラフ全体をトラバースして、成功するかどうかを確認します。ここでは、深さ優先トラバーサルと幅優先トラバーサルの両方が受け入れられます。このアルゴリズムは、ノードをコンポーネントに分割します。

  • すべてのノードを未訪問としてマークする
  • cこのノードが未訪問の場合、 すべてのノードに対して
    • ノードの新しい空のセット、現在のコンポーネントを作成します
    • トラバーサルのためにこのノードをキューに入れる
    • tエンキュー されたノードがある間
      • このノードをキューから削除します
      • 訪問されていないすべてのネイバーをオープンとしてマークし、トラバーサルのためにキューに入れます
      • このノードを通過済みとしてマークする
      • このノードを現在のコンポーネントに追加します
    • 現在のコンポーネントを閉じて、コンポーネントのセットに追加します

コンポーネントが 1 つしかない場合、グラフは連結されます。

キューを使用する場合、アルゴリズムは幅優先検索になります。スタックを使用する場合、アルゴリズムは深さ優先検索になります。push および pop-any 操作を使用するその他のコレクションでもかまいません。特に興味深いのは呼び出しスタックです。「トラバーサルのキューに入れる」を「再帰的にトラバースする」に置き換えます。

有向グラフには、関連する 2 つの概念があります。有向グラフは、すべてのエッジ方向を無視して接続されている場合、弱く接続されています。有向グラフは、すべてのノードからすべてのノードに到達できる場合、強く接続されています。強い接続性をテストするには、前方エッジのみを使用して最初のノードからすべてのノードに到達可能であり、後方エッジのみを使用して最初のノードからすべてのノードに到達可能であることを確認するだけで十分です (最初のノードはすべてのノードから到達可能です)。

  1. 二部

グラフが 2 色可能である場合、そのグラフは 2 部グラフです。2 色を割り当ててみてください。失敗した場合、グラフは 2 部構成ではありません。これは、以前のアルゴリズムに組み込むことができます。ノードをオープンとしてマークするときはいつでも、隣接ノードに割り当てられた色と反対の色をノードに割り当てますt。の隣tがすでに開いている場合は、その色を確認します。その色が の色と同じ場合、tバイカラーリングはありません。

  1. 周期がある

これは簡単です。すでに開いているノードを観察すると、サイクルがあります。サイクルを持たないすべてのグラフは二部グラフであることに注意してください。

有向グラフでは、無向循環の存在を検出します。有向サイクルの存在を検出するには、次の (トポロジカル ソート) アルゴリズムを使用します。

  • ゼロの次数を持つノードがある間
    • ノードをトポロジーソートに追加します（サイクルの検出には関係ありません）
    • グラフからノードを削除します
  • グラフにまだノードがある場合
    • グラフには有向循環が含まれています。そのグラフにはトポロジカル ソートが存在しません
  • そうしないと
    • グラフに有向循環が含まれていない (非循環)。生成されたトポロジー ソートは有効です。
  1. 木

無向グラフは、接続されていて循環を含まない場合はツリーです。

有向グラフは、無向循環がなく、次数が 0 の頂点が 1 つしかない (ルートが 1 つだけ) 場合、ルート付きツリーです。また、有向グラフは、接続されていて、無向循環がなく、出次数が 0 のすべてのノードの入次数が最大で 1 である場合 (すべてのシンクが葉)、ルート付きツリーです。

于 2013-03-13T19:49:10.227 に答える