1

グラフをコンポーネントに分割したい (下の例の DAG のように。コンポーネントを表すため、各ノードの色付きの識別子に注意してください)。画像内のコンポーネントを見つけた後、そのコンポーネントのルートと最後の子を見つけたいと思います。たとえば、青のコンポーネントを例にとると、ルートはEで、最後の子はHです。緑: ルートB- 最後の子H。

グラフの例: グラフの例

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

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

役に立ったが質問の答えにはならなかった質問:

（これらの回答で十分かもしれませんが、実装方法がわかりません）

ノート：

  • すべてのサンプル コードを C++ または C# で投稿してください (サンプル コードを投稿する場合)

  • これは私の最初の質問です。私が何か間違ったことをした場合は、私に知らせてください。

// 大きな編集: 質問を作り直して、私が望むものをより明確にしました。より役立つと思われるコンポーネントを導入しました。

4

1 に答える 1

0

Too long for a comment but I don't think you are finding all the common ancestors:

From wikipedia:

In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).

If you consider the LCA of the parents then there are 4 parents of vertex H which are C, D, F and G then you can consider the LCA to be the values for any pair of parents:

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

so, the LCAs of the parents of H are B, C, D and E.

The common ancestors will be the lowest common ancestor(s) and their ancestors - so A, B, C, D and E.

You need to address why A, C and D are being excluded as common ancestors.

于 2016-04-28T10:43:22.300 に答える