-1

我正在尝试发现从起始节点可到达的所有节点。

似乎从未达到基本情况，我不知道为什么。

我的代码：

class Vertex {
    public final String name;
    public int found;
    public Edge[] adjacencies;
    public Vertex(String argName) { name = argName; found = 0;}
}

class Edge {
    public final Vertex target;
    public Edge(Vertex argTarget, double argWeight) { target = argTarget; weight = argWeight; }
}

ArrayList<Vertex> merge(ArrayList<Vertex> a, ArrayList<Vertex> b) {
    if(a == null) return b;
    if(b == null) return a;
    for(int x = 0; x < a.size(); x++)
        b.add(a.get(x));
        return b;
}

ArrayList<Vertex> span(Vertex b) {
    System.out.println("hello");
    if(b.found == 1) {
        return null;
    }
    ArrayList<Vertex> t = new ArrayList<Vertex>();
    t.add(b);
    b.found = 0;
    if(b.adjacencies == null) return t;
    for(int x = 0; x < b.adjacencies.length; x++) {
        ArrayList<Vertex> result = span(b.adjacencies[x].target);
        t = merge(t, result);
    }
    return t;
}

我收到一个堆栈溢出错误，似乎它陷入了递归，但我不知道为什么。

注意：这是我运行它的图表。

Vertex v0 = new Vertex("Redvile");
Vertex v1 = new Vertex("Blueville");
Vertex v2 = new Vertex("Greenville");
Vertex v3 = new Vertex("Orangeville");
Vertex v4 = new Vertex("Purpleville");

v0.adjacencies = new Edge[]{ new Edge(v1, 5), new Edge(v2, 10), new Edge(v3, 8) };
v1.adjacencies = new Edge[]{ new Edge(v0, 5), new Edge(v2, 3), new Edge(v4, 7) };
v2.adjacencies = new Edge[]{ new Edge(v0, 10), new Edge(v1, 3) };
v3.adjacencies = new Edge[]{ new Edge(v0, 8), new Edge(v4, 2) };
v4.adjacencies = new Edge[]{ new Edge(v1, 7), new Edge(v3, 2) };
4

2 回答 2

1

您从未将 found 设置为 1，您仅将其设置为 0，而您可能的意思是 1。此外，对 found 使用布尔值。此外，对 ArrayLists 使用 addAll，并返回 Collections.emptyList，而不是 null。

于 2012-11-30T21:40:26.003 回答
1

鉴于这个简单的图表：

顶点A <----------------> 顶点B

顶点 A 进入跨度。found==0 所以继续，把它加到 t，设置 found=0，它有一个邻接——然后调用 span(vertex b)

顶点 B 进入跨度。found==0 所以继续，把它加到 t，设置 found=0，它有一个邻接——然后调用 span(vertex a)

顶点 A 进入跨度。found==0 所以继续，把它加到 t，设置 found=0，它有一个邻接——然后调用 span(vertex b)

等等

我认为，问题在于您应该将 found 设置为 1，而不是 0。

（将 VertexA 替换为“Redville”，将 VertexB 替换为“Blueville”以适合您的示例）

于 2012-11-30T21:43:01.347 回答