1. 概要

このチュートリアルでは、有向非巡回グラフで最も低い共通の祖先を見つけるアルゴリズムの1つを紹介します。 また、その時間計算量についても説明します。

さらに、無向ツリーと有向非巡回グラフで最も低い共通の祖先を見つけるアルゴリズムに違いが見られます。 グラフおよびBig-O表記の基本的な知識があることを前提としています。

2. 有向非巡回グラフ

有向非巡回グラフ( DAG )の主な定義を簡単に思い出してみましょう。 頂点のペアはエッジです。 さらに、このエッジにはからへの方向があります。 したがって、から到達可能であることを意味します。 ただし、から到達することはできません:

DAGは、有向非巡回を含まないグラフです。つまり、頂点がないため、この頂点からのパスを見つけて、この頂点に再び到達できます。

興味深いのは、 DAGを作成できることですが、対応する無向グラフにはサイクルが含まれる場合と含まれない場合があります。

左のグラフはDAGです。 有向サイクルは含まれていません。 それを証明するために、各輪郭を見て、これがサイクルではないことを確認することができます。 たとえば、このグラフにはエッジが存在しないため、等高線はサイクルではありません。 エッジしかありません。 同様に、他の輪郭がサイクルではないことを証明できます。

ただし、頂点の方向を削除すると、無向グラフが右側に表示されます。 このグラフには、、、およびの3つのサイクルが含まれています。 これは、エッジが無向であるために発生します。 そして、接続された頂点のペアごとに、両方のエッジが存在すると想定する場合があります。

ただし、対応する無向グラフが非巡回になるように、DAGを作成することもできます。

写真の両方のグラフは非周期的です。 頂点の無向グラフが非巡回であるための条件は、多くのエッジを持つことです。 頂点のDAGまたはそれ以下のエッジがあると仮定します。 したがって、その方向を削除すると、非周期的なグラフも作成されると確信できます。

ただし、有向非巡回グラフには最大のエッジがある場合があります。

3. 最も低い共通の祖先

最も低い共通祖先(LCA)を見つけることは、典型的なグラフの問題です。 ルートツリーでLCAを検索することは意味があります。 ただし、グラフの種類によって、アルゴリズムは少し異なります。 問題の定義を簡単に思い出してみましょう。

2つのノード間およびグラフ内のLCAは、との両方の祖先であるような最も深いノードです。 DAGがグラフの特殊なケースである場合、は0、1、またはそれ以上になる可能性があります。任意の2つのノード間のLCA。 ただし、無向ツリーでは、LCA候補は1つだけになります。

注意することが重要です、任意のノードと、について。

3.1. 頂点の次数

グラフの各ノードには、次数と次数があります。 in-degreeは、入力エッジの数です。 アウトディグリーは、このノード(アウトカム)から始まるエッジの数です。 ノードの度数が0の場合、そのノードはソースと呼ばれます。 アウトディグリーが0の場合、ノードはリーフと呼ばれます。 例を見てみましょう:

写真のグラフの各頂点には3つの数字があります。 これらは頂点の値であり、各値の左と右にそれぞれ次数と次数があります。 このようなグラフには、0と2の2つのソースがあります。 それらは両方ともゼロ度を持っています。 また、3つの葉があります:3、5、および6。 彼らはゼロのアウトディグリーを持っています。

注意することが重要です、写真のグラフは順序付けられているように見えます。 実際、すべての有向非巡回グラフにはトポロジカル秩序があります。 このような頂点の順序は、アルゴリズムをよりよく理解するのに役立つ可能性があります。

3.2. DAGのノードの場合の深さ

有向非巡回グラフのノードの深さ、は、ソースノードから。までの最長パスの長さです。 また、複数のソースノードが存在する場合もあります。 各ノードの深さを計算するために、幅優先探索(BFS)を実行できます。 同様のDAGで深度がどのように異なるかを示す例を次に示します。

各頂点の左上隅の数字は、このノードの深さです。 ソースの深さは常に0です。 写真左のグラフを見てみましょう。 ノード5の深さは2です。 ソースノード2および0からの2つの異なるパスがあります。 ただし、深さは任意のソースノードからの最長パスであるため、深さ5は2です。 ただし、グラフ(図の右側のグラフ)から頂点0を削除すると、ソース1と2からのパスが2つあるため、ノード5の深さは1になります。 両方のパスの長さは1です。

3.3. DAGのLCAの例

前述したように、2つのノード間に複数の最も低い共通の祖先が存在する可能性があります。 有向非巡回グラフのLCAの数は、0からの間である可能性があります。ここで、は頂点の数です。

7つの頂点のグラフでは、1と2の両方の深さが等しいため、または。 と。

頂点とその祖先の間のLCAを見つけたい場合は、LCAが祖先になります。 したがって、たとえば、。

他のグラフでは、頂点3と5の間にLCAは存在しません。 彼らには共通の親がいません。

4. DAGでLCAを見つけるアプローチ

グラフの2つの指定されたノード間で最も低い共通の祖先をすべて見つけることができる単純なアルゴリズムを紹介します。

4.1. アルゴリズム

グラフでを見つけたいとします。 最初は、すべての頂点が白に着色されています。

まず、ターゲットノードの1つで深さ優先探索(DFS)を実行します。 それをノードとします。 また、親の配列(開始頂点からの現在のパス)を追跡します。 DFSの間、到達するたびに、のすべての祖先を赤で色付けします。

次に、他のノードでDFSを開始する必要があります。 それに到達すると、すべての赤い祖先を黒に再着色します。

最後に、黒いノードによって誘導というサブグラフを作成しました。 アウトディグリーがゼロの新しいグラフのノードが答えです。

アルゴリズムのステップを視覚化してみましょう。

これが最初のグラフです。 LCA(4、7)を見つけたいとします。 DFSを開始し、4または7のすべての親を赤で色付けします。 たとえば、頂点7を選択しましょう。

ご覧のとおり、ノード7には5つの親があります。 次に、別のノード(4)のすべての親を黒で色付けする必要があります。 理解を深めるために、最初に4のすべての祖先を見つけます。

Vertex4には3つの親があります。 しかし、私たちの目的は、赤と黄色のノードの交点を黒で着色することです。 との共通部分はです。 したがって、3つの黒いノードがあります。

最後のステップは、黒いノード0、1、および2にサブグラフを誘導することです。 これは、3つの頂点と、0、1、および2のすべての共通エッジを持つサブグラフになります。

ここで、2つのノード1と2のアウトディグリーがゼロであることがわかります。 したがって、それらは私たちの問題に対する答えです。 または。

4.2. 時間計算量

グラフにソースノードが1つしかないことを前提としています。

このようなアルゴリズムの時間計算量はです。ここで、は頂点の数であり、はDAGのエッジの数です。 ただし、DAGでは。 アルゴリズムの間、DFSを2回順番に実行します。 その後、黒いノードによって誘導されたサブグラフを作成しました。 それらの量は最大で、である可能性があります。 新しいサブグラフのエッジの数も。になる可能性があります。 したがって、誘導部分グラフの作成にも時間がかかります。 アウトディグリーがゼロのノードを見つけるには、O(V)時間がかかります。

したがって、アルゴリズムの合計時間計算量はです。

ただし、複数のソースノードがある場合、時間計算量は最大で増加します。追加の乗数は、すべてのソース頂点からDFSを開始する必要があることを表します。 それらの量は最大である可能性があります。 次に、ノードのすべての親を見つけるために、すべての検索からすべての祖先の共通部分を見つける必要があります。

6. 結論

この記事では、有向非巡回グラフの2つの頂点間のLCAを見つけるためのアルゴリズムの1つを紹介しました。 さらに、無向ツリーとDAGのLCA問題の用語と問題定義の違いに気づきました。 さらに、アルゴリズムの時間計算量についても説明しました。 もちろん、事前計算手法を使用したより効率的なアルゴリズムが存在します。 ただし、提案されているブルートフォースソリューションよりもはるかに高速ではありません。