在 C# 中通过 RMQ 约简解决 LCA

• 下载源代码 - 3.68 KB

引言

昨天我花了一些时间寻找一种算法来找到给定树中的最近公共祖先。 LCA 是两个子节点共享的第一个节点。

在上图中，3 和 6 的最近公共祖先是 1。节点 0 也是一个公共祖先，但不是最近的公共祖先。

最近公共祖先在社交网络、计算机网络、编译器中的公共子表达式消除等方面有很多应用。我的需求是在表达式树中找到公共祖先。 我在互联网上找不到任何 C# 的相关内容。 我决定根据 Robert Tarjan、Omer Berkman 和 Uzi Vishkin 的工作编写一个。

我的图中的一个节点有一个值和一组子节点。 我们没有对父节点的引用。 在此图中“识别”节点的唯一方法是通过引用。

/// <summary>
/// A tree node.
/// </summary>
/// <typeparam name="T">The type of the value associated with this node.</typeparam>
public interface ITreeNode<T>
{
    /// <summary>
    /// Gets or sets the value.
    /// </summary>
    /// <value>The value.</value>
    T Value { get; set; }

    /// <summary>
    /// Gets the children.
    /// </summary>
    /// <value>The children.</value>
    IEnumerable<ITreeNode<T>> Children { get; }
}

Using the Code

我们将创建一个具有单个方法的辅助类。 此方法接受两个节点并返回它们最常见的父节点。

IGraphNode<T> FindCommonParent(ITreeNode<T> x, ITreeNode<T> y) 

Berkman 和 Vishkin 的算法非常简单。 我们首先做一些预处理。 我们使用欧拉路径访问每个节点并将此存储在数组中。 可以使用深度优先遍历找到欧拉路径。 我们从根开始，记录从根到第一个子节点的路径。 如果该子节点也有一个子节点，那么我们将记录到该子节点的路径，一直到图的底部。 一旦我们到达底部，我们将从子节点返回父节点记录路径。 如果父节点有另一个子节点，我们将执行相同的过程，直到我们访问了图中的每个节点并返回到根节点。

private void PreProcess()
{
    // Eulerian path visit of graph 
    Stack<ProcessingState> lastNodeStack = new Stack<ProcessingState>();
    ProcessingState current = new ProcessingState(_rootNode);
    ITreeNode<T> next;
    lastNodeStack.Push(current);

    NodeIndex nodeIndex;
    int valueIndex;
    while (lastNodeStack.Count != 0)
    {
        current = lastNodeStack.Pop();
        if (!_indexLookup.TryGetValue(current.Value, out nodeIndex))
        {
            valueIndex = _nodes.Count;
            _nodes.Add(current.Value);
            _indexLookup[current.Value] = new NodeIndex(_values.Count, valueIndex);
        }
        else
        {
            valueIndex = nodeIndex.LookupIndex;
        }
        _values.Add(valueIndex);

        // If there is a next then push the current value on to the stack along with 
        // the current value.
        if (current.Next(out next))
        {
            lastNodeStack.Push(current);
            lastNodeStack.Push(new ProcessingState(next));
        }
    }
    _nodes.TrimExcess();
    _values.TrimExcess();
}

预处理完成后，我们可以开始使用范围最小值查询来计算 LCA。 范围最小值查询的工作方式与听起来完全一样。 对于数组中给定的范围，我们需要找到最小值。 我们的范围由节点第一次被访问的时间定义。 我们进行哈希表查找以获取给定节点的信息，然后使用简单的 FOR 循环来查找给定范围内的最小值。 不包括哈希表查找，我们可以说最坏情况下的时间复杂度是 O(n)，其中 n 是图中的节点数。

public ITreeNode<T> FindCommonParent(ITreeNode<T> x, ITreeNode<T> y)
        {
            // Find the first time the nodes were visited during preprocessing.
            NodeIndex nodeIndex;
            int indexX, indexY;
            if (!_indexLookup.TryGetValue(x, out nodeIndex))
            {
                throw new ArgumentException("The x node was not found in the graph.");
            }
            indexX = nodeIndex.FirstVisit;
            if (!_indexLookup.TryGetValue(y, out nodeIndex))
            {
                throw new ArgumentException("The y node was not found in the graph.");
            }
            indexY = nodeIndex.FirstVisit;

            // Adjust so X is less than Y
            int temp;
            if (indexY < indexX)
            {
                temp = indexX;
                indexX = indexY;
                indexY = temp;
            }

            // Find the lowest value.
            temp = int.MaxValue;
            for (int i = indexX; i < indexY; i++)
            {
                if (_values[i] < temp)
                {
                    temp = _values[i];
                }
            }
            return _nodes[temp];
        } 

关注点

此解决方案存在一个小问题。 如果我们正在计算节点 X、Y 的 LCA，并且 Y 是 X 的后代，那么此解决方案将返回 X。 对于我的要求，这不是问题，但在某些情况下可能想要返回 X 的直接父级。

这是我第一次尝试，我不是算法专家。 这个问题有很多更优化的解决方案。 这个解决方案的代码很少，而且非常容易理解。 如果您有任何反馈，请告诉我。