開始ノードから到達可能なすべてのノードを検出しようとしています。
ベースケースに到達していないようですが、理由はわかりません。
私のコード:
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) };