33

私はネットを検索しましたが、グラフのすべての関節頂点を見つけるための DFS アルゴリズムの説明を見つけることができませんでした。wikiページすらありません。

ここまで読んで、基本的な事実を知ることができました。PDF

各ノードには変数があり、実際にはバック エッジを見て、ルート ノードに最も近いノードと最上部のノードを見つけます。すべてのエッジを処理した後、それが見つかります。

しかし、DFS の実行中に各ノードでこの down & up 変数を見つける方法がわかりません。この変数は正確に何をしていますか?

アルゴリズムを説明してください。

ありがとう。

4

4 に答える 4

44

関節頂点の検索は、DFS のアプリケーションです。

手短に、

  1. グラフに DFS を適用します。DFS ツリーを取得します。
  2. 先にアクセスしたノードは、そのノードが到達して後でアクセスしたノードの「親」です。
  3. ノードのどの子にもその親の先祖へのパスがない場合、このノードを削除すると、この子がグラフから分離されることを意味します。
  4. 例外があります: ツリーのルートです。複数の子がある場合、それはアーティキュレーション ポイントであり、そうでない場合はそうではありません。

ポイント 3 は、本質的に、このノードが関節点であることを意味します。

子の場合、ノードの祖先へのこのパスは、ノードまたはその子のいずれかからのバックエッジを経由します。

このすべては、このPDFで美しく説明されています。

于 2013-04-24T23:32:35.313 に答える
15

このアルゴリズムがどのように機能するかを直感的に理解できるように努め、Bi-Components とブリッジを出力するコメント付きの疑似コードも示します。

実際、関節点のブルート フォース アルゴリズムを開発するのは簡単です。頂点を取り出して、グラフで BFS または DFS を実行するだけです。接続されたままの場合、頂点は関節点ではなく、それ以外の場合は関節点です。これはO(V(E+V)) = O(EV)時間内に実行されます。課題は、線形時間 (すなわちO(E+V)) でこれを行う方法です。

関節点は、2 つ (またはそれ以上) のサブグラフを接続します。これは、あるサブグラフから別のサブグラフへのエッジがないことを意味します。したがって、これらのサブグラフの 1 つにいて、そのノードにアクセスしていると想像してください。ノードにアクセスすると、フラグが付けられ、使用可能なエッジを使用して次のフラグが付けられていないノードに移動します。これを行っている間、まだ同じサブグラフ内にいることをどのように確認しますか? ここでの洞察は、同じサブグラフ内にいる場合、フラグの付いていないノードにアクセスしているときに、フラグの付いたノードがエッジを介して最終的に表示されるということです。これはバックエッジと呼ばれ、サイクルがあることを示します。バック エッジを見つけるとすぐに、そのフラグが設定されたノードから現在アクセスしているノードまでのすべてのノードがすべて同じサブグラフの一部であり、間に関節点がないことを確信できます。もしあなたがしなかったなら'

したがって、頂点を訪問し、バック エッジのターゲット間のすべてのポイントを、同じサブグラフ内の現在訪問中のノードとしてマークするアルゴリズムが必要です。明らかにサブグラフ内にサブグラフが存在する可能性があるため、これまでで最大のサブグラフを選択する必要があります。これらのサブグラフは Bi-Components と呼ばれます。このアルゴリズムを実装するには、これまでに訪れた頂点の数として初期化される ID を各バイ コンポーネントに割り当てます。後でバック エッジを見つけたら、bi-component ID をこれまでに見つけた最小値にリセットできます。

明らかに 2 つのパスが必要です。最初のパスでは、バック エッジがある場合は、各頂点からどの頂点が見えるかを調べます。2 番目のパスでは、頂点を反対方向に訪問し、最小のバイコンポーネント ID (つまり、すべての子孫からアクセス可能な最古の祖先) を収集します。DFS は当然ここに適合します。DFS では、最初にダウンしてから再びアップするため、上記の両方のパスを 1 回の DFS トラバーサルで実行できます。

これ以上苦労することなく、ここに疑似コードがあります：

time = 0
visited[i] = false for all i
GetArticulationPoints(u)
    visited[u] = true
    u.st = time++
    u.low = v.st    //keeps track of highest ancestor reachable from any descendants
    dfsChild = 0    //needed because if no child then removing this node doesn't decompose graph
    for each ni in adj[i]
        if not visited[ni]
            GetArticulationPoints(ni)
            ++dfsChild
            parents[ni] = u
            u.low = Min(u.low, ni.low)  //while coming back up, get the lowest reachable ancestor from descendants
        else if ni <> parent[u] //while going down, note down the back edges
            u.low = Min(u.low, ni.st)

    //For dfs root node, we can't mark it as articulation point because 
    //disconnecting it may not decompose graph. So we have extra check just for root node.
    if (u.low = u.st and dfsChild > 0 and parent[u] != null) or (parent[u] = null and dfsChild > 1)
        Output u as articulation point
        Output edges of u with v.low >= u.low as bridges
    output u.low as bicomponent ID
于 2014-12-30T02:01:26.940 に答える