1

最近のインタビューで、以下の質問をされました。

ノードとエッジのセットが与えられ、開始ノードが最終終了ノードを指します。下の図では、1 で開始し、15 で終了します。彼らの質問には、ノード 2 (または任意のノード) が開始点として与えられ、入力エッジがすべてノード 2 から到達可能ではないパス内の次のノードをどのように見つけることができますか (つまり、どうすれば 14 に到達できますか)。

どうすればこれを行うことができますか、疑似コードは問題ないはずです。

ここに画像の説明を入力

4

4 に答える 4

3
  1. 開始ノードから到達可能なすべてのエッジをマークします。
  2. マークされていない入力エッジを持つ開始ノードから到達可能な最初のノードを見つけます。
于 2012-03-25T16:11:20.090 に答える
1

グラフ全体を少なくとも 1 回トラバースすることを回避する方法がわかりません (ノードに親へのリンクがない場合)。それが問題ない場合、ノードから直接の親のセットへのマップ (以下の「親マップ」) に基づく簡単な解決策は次のとおりです。

  • 開始ノードの下にあるすべてのノードの親マップを拡張するルーチンを作成します (dfs を使用)。ルーチンは、マップ内で既にキーになっているノードを探索する必要はありません。

  • グラフ内のすべてのノードに対して上記のルーチンを呼び出します。これにより、ノードから親への完全なマップが得られます (事実上、グラフの転置)。

  • 新しいマップを使用して、質問で指定されたノード (例: 2) から上記のルーチンを呼び出します。これにより、ノードから 2 から到達可能な親へのマップが得られます。

  • 指定されたノードからの bfs を使用して、2 つのマップ内の親が異なる最初のノードを見つけます。

実際の親ノードをマップに保存する必要はありません (そのように説明するのが最も簡単です)。訪問したノードをマークし、親の数を保存することで、同様のことを行うことができます。

さらに別の言い方をすると、グラフの転置と、指定されたノードから到達可能なノードのセットを見つけます。次に、指定されたノードから bfs を実行して、転置が到達可能なセット外の親につながる最初のノードを見つけます。（これは本当に単なる質問です...）

于 2012-03-25T15:15:11.827 に答える
1

私はこう言います：

  1. ノード 2 から到達できないノードを検索します。BFS または任意の完全なアルゴリズムを実行して、 set all reachable を検索しますR。を使用して到達不能を検索U = V - R

  2. 到達不能なノードから到達できるすべてのノードを検索し、ノードを見つけるたびに、それがノード 2 の到達可能リストにあるかどうかを確認します。そうである場合は、使用したばかりのエッジを保存します。

2 番目のステップでは、ノードを連続して選択Uし、BFS を実行します。ノードの扱いは異なります。

  • すでに選択されているノードXに属するノードを見つけるたびに、停止しますU
  • Y属しているが選択されていないノードを見つけるたびにU、このノードをから削除します。U
  • でノードを見つけたら R、エッジを覚えて、このノードを「これまでにアクセスしない」とマークします。
于 2012-03-25T14:52:06.500 に答える
0
  • このアルゴリズムが 1 回のルックアップを実行する必要がある場合は、StartNode を検討してください。
    • 開始ノードから到達可能なすべてのノードを見つけます。(BFS グラフ走査アルゴリズムを実行することにより)
    • 効率的なルックアップのために、ハッシュ テーブルに StartNode から到達可能なノードのリストを保持します。
    • 現在のノードから到達可能な各ノードについて (順番に):
      • 着信ノードを確認します (着信エッジの開始頂点)
      • すべての着信ノードがハッシュ テーブルで使用可能な場合は、次に到達可能なノードに移動します。そうでない場合は、このノードを返します。
于 2012-03-26T04:50:17.887 に答える