在有向无环图中找到最低共同祖先的算法? [英] Algorithm to find lowest common ancestor in directed acyclic graph?

问题描述

想象一个有向无环图如下，其中:

• A"是根(总是只有一个根)
• 每个节点都知道它的父节点
• 节点名称是任意的 - 无法从中推断出任何内容
• 我们从另一个来源知道节点是按照 A 到 G 的顺序添加到树中的(例如，它们是在版本控制系统中提交的)

我可以使用什么算法来确定两个任意节点的最低共同祖先(LCA)，例如，以下的共同祖先:

• B 和 E 是 B
• D 和 F 是 B

注意:

• 从根到给定节点不一定只有一条路径(例如G"有两条路径)，所以你不能简单地

  LCA(4,5) 可能的解是 1 和 2.

  请注意，如果您想找到 3 个或更多节点的 LCA，它仍然有效，您只需为每个节点添加不同的颜色即可.

  Imagine a directed acyclic graph as follows, where:

  • "A" is the root (there is always exactly one root)
  • each node knows its parent(s)
  • the node names are arbitrary - nothing can be inferred from them
  • we know from another source that the nodes were added to the tree in the order A to G (e.g. they are commits in a version control system)

  What algorithm could I use to determine the lowest common ancestor (LCA) of two arbitrary nodes, for example, the common ancestor of:

  • B and E is B
  • D and F is B

  Note:

  • There is not necessarily a single path to a given node from the root (e.g. "G" has two paths), so you can't simply traverse paths from root to the two nodes and look for the last equal element
  • I've found LCA algorithms for trees, especially binary trees, but they do not apply here because a node can have multiple parents (i.e. this is not a tree)

  解决方案

  Den Roman's link (Archived version) seems promising, but it seemed a little bit complicated to me, so I tried another approach. Here is a simple algorithm I used:

  Let say you want to compute LCA(x,y) with x and y two nodes. Each node must have a value color and count, resp. initialized to white and 0.

  1. Color all ancestors of x as blue (can be done using BFS)
  2. Color all blue ancestors of y as red (BFS again)
  3. For each red node in the graph, increment its parents' count by one

  Each red node having a count value set to 0 is a solution.

  There can be more than one solution, depending on your graph. For instance, consider this graph:

  LCA(4,5) possible solutions are 1 and 2.

  Note it still work if you want find the LCA of 3 nodes or more, you just need to add a different color for each of them.

  这篇关于在有向无环图中找到最低共同祖先的算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！