2

我正在尝试使用 jGraphT 在 Java 中实现最长路径算法，但是在编译时出现 java.lang.StackOverflowError。错误消息指向我复制图形的行以及该方法在算法内部调用自身的行。我使用的算法描述是Liao Wong 最长路径，第 11 页。

我在哪里做错了什么？

import org.jgrapht.*;
import org.jgrapht.graph.*;
import java.util.*;

public class LongestPath {
    private DirectedWeightedMultigraph<Vertice, DefaultWeightedEdge> graph;
    private double product;
    private ArrayList<DefaultWeightedEdge> edges;

    public LongestPath(DirectedWeightedMultigraph<Vertice, DefaultWeightedEdge> theGraph) {
        this.graph = theGraph;
        this.product = 1.0;
        this.edges = new ArrayList<DefaultWeightedEdge>();
    }

    public ArrayList<DefaultWeightedEdge> liaoWongLongestPath(Vertice source) {
        DirectedWeightedMultigraph<Vertice, DefaultWeightedEdge> copyGraph =     (DirectedWeightedMultigraph<Vertice, DefaultWeightedEdge>) graph.clone();
        boolean flag;

        for (int j = 1;j <= (copyGraph.edgeSet().size() + 1);j++) {

            edges = this.liaoWongLongestPath(source);

            flag = true;

            for (DefaultWeightedEdge dwe : edges) {

                if (copyGraph.getEdgeWeight(copyGraph.getEdge(source, copyGraph.getEdgeTarget(dwe))) < (copyGraph.getEdgeWeight(copyGraph.getEdge(source, copyGraph.getEdgeSource(dwe))) + copyGraph.getEdge(copyGraph.getEdgeSource(dwe), copyGraph.getEdgeTarget(dwe)).getWeight())) { 
                    //product = (copyGraph.getEdgeWeight(copyGraph.getEdge(source, copyGraph.getEdgeSource(dwe))) * copyGraph.getEdge(copyGraph.getEdgeSource(dwe), copyGraph.getEdgeTarget(dwe)).getWeight());
                    flag = false;
                    boolean status = edges.add(copyGraph.getEdge(source, copyGraph.getEdgeTarget(dwe)));
                }
            }
            if (flag) {
                System.out.println("Product: " + product + ".");
                return edges;
            }
        }

        return edges;
    }
}
4

1 回答 1

0

您在代码中进行递归调用，并在每次迭代中复制整个图。这是非常昂贵的，通常这会导致堆栈溢出异常。尝试消除该程序的递归复杂性和/或重用图形（您可能想要使用 MaskSubgraph 类）。

也请看看这个：什么是 StackOverflowError？

于 2013-08-05T07:25:39.570 回答