获取数组中两个项目之间的路径

Question

我正在尝试编写一个函数来获取数组中两个项目之间的路径这个数组代表项目之间的连接就像一棵没有循环的树，例如：

 A=[1, 3, 0, 3, 2] 
 A[0]=1 // node 0 is connected to node 1
 A[1]=3 // node 1 is connected to node 3
 A[2]=0 //node 2 is connected to node 0

等等，所以现在这个数组生成一个像这样的图 <4---2---0----1---3> 这个函数应该得到数组中两个给定索引之间的路径如果给定 4 & 1 输出应该是 [2,0]

的列表

所以我想帮助如何开始构建这个函数的算法？

我试过这个代码

    private List<int> getDirectlyConnectedNodes(int ind, int[] A)
        {

            List<int> directNeighbours = new List<int>();
            for (int i = 0; i < A.Length; i++)
            {
                if ((A[i] == ind || A[ind] == i) && ind != i)
                {
                    directNeighbours.Add(i);
                }
            }
            return directNeighbours;
        }
        private List<int> getPath(int ind1, int ind2, int[] A, List<int> path)
        {

            List<int> directNeighbours= getDirectlyConnectedNodes(ind1, A);


            foreach (int i in directNeighbours)
            { 
                path.Add(i);
                if (A[i] == ind2 || A[ind2] == i)
                {

                    return path; 
                }
                else
                {
                    getPath(i, ind2, A, path);  
                }

            }

            return path; 
        }

Answer 1

您可以找到从两个节点到根的路径，删除公共部分并加入路径。

public static List<int> GetPath(int a,int b,int[] array) {
    Stack<int> stacka=GetPathToRoot(a,array);
    Stack<int> stackb=GetPathToRoot(b,array);
    int lastCommonNode=-1;
    while(stacka.Count>0&&stackb.Count>0&&stacka.Peek()==stackb.Peek()) {
        lastCommonNode=stacka.Pop();
        stackb.Pop();
    }
    List<int> list=new List<int>();
    while(stacka.Count>1) {
        list.Add(stacka.Pop());
    }
    list.Reverse();
    if(stacka.Count>0&&stackb.Count>0) {
        list.Add(lastCommonNode);
    }
    while(stackb.Count>1) {
        list.Add(stackb.Pop());
    }
    return list;
}
private static Stack<int> GetPathToRoot(int a,int[] array) {
    Stack<int> stack=new Stack<int>();
    for(;;) {
        stack.Push(a);
        if(array[a]==a) {
            break;
        }
        a=array[a];
    }
    return stack;
}

Answer 2

您不能只从第一个索引开始并继续前进直到达到第二个索引吗？您的数据结构中似乎没有任何分支，只是从一个节点到下一个节点的固定路径。

private IEnumerable<int> getPath(int ind1, int ind2, int[] A)
{    
    for (int ind = ind1; A[ind] != ind && A[ind] != ind2; ind = A[ind])
    {
        yield return A[ind];
    }
}

如果指定节点之间没有路径，您可能需要调整它以覆盖误报，但如果有路径，它应该会找到它。

获取数组中两个项目之间的路径

Get the path between two items in array

c#

arrays

algorithm

tree