0

無向グラフとノードが与えられた場合、任意のパスが特定のノードにつながるように、グラフを有向グラフに変更するにはどうすればよいでしょうか。この質問は、SE のインタビューで人気のあるアルゴリズムの質問として取り上げられています。

4

1 に答える 1

1

これは単純に、指定されたノードをルートとする (および指定された) ツリーを作成し、それを DAG に完成させるだけです。任意の検索アルゴリズム (BFS や DFS など) で解決策を得ることができます。検索アルゴリズムを使用して、指定されたノードから開始します。ノードに遭遇するたびに、それをすでに接続されているノード (通常はそのノードに到達したノード) に接続します。次に、ノードに遭遇した順序に従って残りのエッジの方向を設定できます (後者から早い方）

于 2013-02-03T19:25:14.303 に答える