Directed Acyclic Graph（DAG）をコンポーネントに分割し、それらのコンポーネントのルートと最後の子を見つける

Question

グラフをそのコンポーネントに分割したい（例DAGのように）。コンポーネント）。画像のコンポーネントを見つけたら、そのコンポーネントのルートと最後の子を探したいと思います。 青のコンポーネントを取ると、ルートはE、最後の子はHになります。 緑色：ルートB - 最後の子H。

例のグラフ：

あなたはEとの間の接続を見つけることができれば - コンポーネントにそれを分割せずにIからH、BからE、BからH、Aを。それが私の最終目標であることを私に教えてください。

コンポーネントのコンパイルについて。それが実際に私の最終目標です。私はちょうどあなたが私が達成しようとしているもののより良い理解を得るためにそれを含めるためにしたかった。これは一度これらの接続を見つけることはできません。

Iが役に立ったと評価していますが、私の質問答えていない質問：

• Algorithm to find lowest common ancestor in directed acyclic graph?

• Finding best common ancestor of two leaf nodes where nodes have zero, one, or two parents

（これらの答えは十分かもしれないが、私は実装する方法がわからないがそれ）

注：

• （あなたがサンプルコードを投稿するつもりなら）これは私の最初の質問であるC++やC＃で

• をすべてのサンプルコードを投稿してください。私が何か間違ったことがあったなら、私に知らせてください。

//ビッグ編集： は、私が何をしたい、それがより明確にする質問を作り直しました。もっと役に立つと思うかもしれないコンポーネントを紹介しました。

Answer 1

コメントには長すぎる

が、私はあなたがすべての共通の祖先を見つけているとは思わない：wikipediaから

：

グラフ理論と計算機科学、最低の共通祖先（LCA）でツリーまたは有向非循環グラフ（DAG）内の2つのノードvおよびwは、子孫としてvおよびwの両方を持つ最も低い（すなわち最も深い）ノードであり、各ノードはそれ自身の子孫であると定義します。したがってvに直接接続w、wは最も低い共通祖先です）。

あなたは両親のLCAを考慮した場合、4人のCある頂点Hの両親、D、FとG、あなたは両親のいずれかのペアの値であることがLCAを考慮することができますがあります。

は、

• LCA(C, D) = B
• LCA(C, F) = C
• LCA(C, G) = C
• LCA(D, F) = D
• LCA(D, G) = D
• LCA(F, G) = E

ので、Hの両親ののLCAはB、C、DとEです。そうA、B、C、DとE -

共通の祖先は、最も低い共通の祖先（S）とその祖先であろう。

なぜA,CおよびDが共通の祖先として除外されているのかを説明する必要があります。