2

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

我用 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'没有存储'Route'，即它映射到'null'。

对于顶点'3'，'hashMap'没有存储'Route'，即它映射到'null'。

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

对于顶点'5'，'hashMap'没有存储'Route'，即它映射到'null'。

显然，“hashMap”存储了错误的“路线”。

编辑2：

好的，所以在进行了头脑风暴建议的修改之后，该程序适用于无环图。我希望它也适用于循环图。我尝试了几个输入，有趣的是，我注意到通过 Brainstorm 建议的修改，如果循环边属于ArrayList 'allEdges'. 换句话说，边缘出现在输入中的顺序会有所不同，这并不理想。

现在，我意识到我忘记在递归中标记当前“正在进行”的节点，因此代码陷入了无限递归调用序列。所以我所做的是创建一个全局堆栈inProcess，它将包含在source递归调用之一中起作用的节点，以便在处理这些递归调用期间不会再次遍历相同的节点。但我仍然没有得到正确的输出。这是我所做的修改：

初始代码块：

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

现在将上面的块修改为以下内容：

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
      }


}

我觉得这个修改在某种程度上是不够的。谁能告诉我有什么问题并纠正我？

4

2 回答 2

0

我想我已经修好了！我发现了两个问题。第一：就在递归调用之前（在 if-else 之前），我们有代码：

int nextNode = allEdges.get(i).getEndNode();
ArrayList<Route> temp = hashMap.get(nextNode);

然后 if tempisnull它跳转到递归调用，但在递归调用之后 hashMap.get(nextNode) 可能返回非空值。这样您就想在 if 语句之后执行部分。我这样修复它：

      int nextNode = currentEdge.getEndNode();
      ArrayList<Route> temp = hashMap.get(nextNode);
      if(temp==null) {
           findPaths(nextNode, dest);
           temp = hashMap.get(nextNode);
      }

      if(temp!=null) {
 for1:     for(j=0;j<temp.size();j++) {
       //...

我发现的第二个问题在这里：

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);

请注意，堆栈是在将路由插入 hashmap 之前添加的，然后从之后删除。if-else 语句中创建的路由对象引用了相同的堆栈，以便更改保存在那里的内容。你想要的是制作这样的副本：

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

下面列出了整个函数。很抱歉弄乱了格式。

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

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

            } else {
                int nextNode = currentEdge.getEndNode();
                ArrayList<Route> temp = hashMap.get(nextNode);
                if (temp == null) {
                    findPaths(nextNode, dest);
                    temp = hashMap.get(nextNode);
                }

                if (temp != null) {
                    for1: for (j = 0; j < temp.size(); j++) {
                        ArrayList<Integer> 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<Integer> copy = new ArrayList<Integer>(stack);
                        ArrayList<Route> list3 = hashMap.get(source);
                        if (list3 != null) {
                            list3.add(new Route(source, dest,copy));
                        } else {
                            ArrayList<Route> list4 = new ArrayList<Route>();
                            list4.add(new Route(source, dest, copy));
                            hashMap.put(source, list4);
                        }
                        stack.removeAll(path);
                    }
                }
            }
        }
    }
}
于 2013-07-08T19:09:03.097 回答
0

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

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

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

于 2013-07-08T17:18:34.737 回答