java - 使用记忆化的源和目标之间有向图中的所有非循环路径

Question

我正在研究一个研究问题，该问题涉及在一般有向图中存储从源顶点到目标顶点的所有非循环路径(可能是循环的，也可能不是循环的)。输入由有向图、源顶点和目标顶点组成。

我已经用 Java 编写了一个方法来执行此操作。我使用了记忆化的概念，通过存储从源顶点到目的地的所有非循环路径，这样如果我在我的方法的递归调用期间到达相同的顶点，我可以只使用存储的“路由”，并且节省大量计算。

我在算法的递归步骤中某处出错了(我认为)，我花了一些时间思考可能是什么错误，但我无法找出来。在这方面，我将不胜感激。提前致谢!

哦，如果有人想澄清任何代码块的用途，请发表评论!

我在解决问题的方法中基本上使用了 DFS。我的代码如下:

//'allEdges' is an ArrayList of all edges of the input graph

/*'Route' is a class that stores the 'src', 'dest' and 'edgeIndices' of 'allEdges'
that comprise the route from 'src' to 'dest'*/

/*'hashMap' is a HashMap<Integer, ArrayList<Route>>. It maps an integer source vertex
 to a list of all routes from that vertex to the actual destination vertex to which
the method is initialized from main()*/


static void findPaths(int source, int dest)
{
    int i,j,k;
    for(i=0;i<allEdges.size();i++)
    {
        if(allEdges.get(i).getStartNode()==source)
        {
            ArrayList stack = new ArrayList();
            stack.add(i);   //pushing edge index to stack
            if(allEdges.get(i).getEndNode()==dest)
            {
                ArrayList<Route> list1 = hashMap.get(source);   

                if(list1!=null)
                {
                    list1.add(new Route(source,dest,stack));
                    hashMap.put(source, list1);
                }
                else
                {
                    ArrayList<Route> list2 = new ArrayList();
                    list2.add(new Route(source,dest,stack));
                    hashMap.put(source, list2);
                }

            }
            else
            {
                int nextNode = allEdges.get(i).getEndNode();
                ArrayList<Route> temp = hashMap.get(nextNode);
                if(temp!=null)
                {
    for1:           for(j=0;j<temp.size();j++)
                    {
                        ArrayList path = temp.get(j).getEdgeIndices();

                        for(k=0;k<path.size();k++)
                        {
                            int edgeIndex = (int)path.get(k);
                            Edge ed = allEdges.get(edgeIndex);
                            if(ed.getStartNode()==source)
                            {
                                continue for1;
                            }
                        }

                        stack.addAll(path);

                        ArrayList<Route> list3 = hashMap.get(source);
                        if(list3!=null)
                        {
                            list3.add(new Route(source,dest,stack));
                            hashMap.put(source,list3);
                        }
                        else
                        {
                            ArrayList<Route> list4 = new ArrayList();
                            list4.add(new Route(source,dest,stack));
                            hashMap.put(source,list4);
                        }


                        stack.removeAll(path);
                    }
                }
                else
                {
                    findPaths(nextNode, dest);
                }
            }    
        } 
    }

}

编辑 1:

对于以下输入图:

顶点数 = 5

源顶点 = 1

目标顶点 = 5

有向边:1 -> 2, 1 -> 3, 1 -> 4, 2 -> 4, 4 -> 5

从1到5的所有路径都是:

1 -> 2 -> 4 -> 5

1 -> 4 -> 5

调用 findPaths(1, 5) 时的输出 'hashMap' 如下:

对于顶点 '1'，'hashMap' 只存储了一个 'Route'，并且该路由只有一个 'Edge':1 -> 4

对于顶点“2”，“hashMap”没有存储“路由”，即它映射到“null”。

对于顶点“3”，“hashMap”没有存储“路由”，即它映射到“null”。

对于顶点 '4'，'hashMap' 只存储了一个 'Route'，并且该路由只有一个 'Edge':4 -> 5

对于顶点“5”，“hashMap”没有存储“路由”，即它映射到“null”。

很明显，'hashMap' 存储了错误的'Route's。

编辑 2:

好的，所以在按照 Brainstorm 的建议进行修改后，该程序适用于非循环图。我希望它也适用于循环图。我试了几个有趣的是，我注意到根据 Brainstorm 建议的修改，如果循环边属于 ArrayList 'allEdges' 的末尾，则该程序适用于某些循环图。换句话说，边在输入中出现的顺序会产生影响，这并不理想。

现在，我意识到我忘记标记递归中当前“正在处理”的节点，因此代码陷入无限递归调用序列。所以我所做的是创建一个全局堆栈 inProcess，它将包含在其中一个递归调用中充当 source 的节点，这样同一个节点就不会在那些递归调用的处理过程中再次遍历。但我仍然没有得到正确的输出。这是我所做的修改:

初始代码块:

if(temp==null)
{
   findPaths(nextNode,dest);
   temp = hashMap.get(nextNode);
}

现在将上述 block 修改为以下内容:

if(temp==null)
{

      if(!inProcess.contains(nextNode))
      {
           inProcess.add(nextNode);
           findPaths(nextNode,dest);
           inProcess.remove(inProcess.indexOf(nextNode));
           temp = hashMap.get(nextNode);
      }
      else
      {
           continue main_for1;  //main_for1 labels the very first for() loop of this method
      }


}

我觉得这个修改在某些方面是不够的。谁能告诉我哪里出了问题并纠正我？

Answer 1

我认为您的问题可能是主要 else 语句的第一行:

int nextNode = allEdges.get(i).getEndNode();

这到底是做什么的？在我看来，当您第一次通过路径时，当您还没有弄清楚 i 的结束节点时，它会返回 null。