我需要寻求你的帮助，因为我已经为我的问题苦苦挣扎了很多天，但没有找到任何合适的解决方案。我想找到包含节点(将成为我的方法的参数)并将以中心节点 0 结尾的子图形的权重。我知道这听起来很愚蠢，但图像在这里会有很大帮助(http://img542.imageshack.us/img542/5400/zrzutekranu20130418o205.png)。 例如 getWeight(8) 将返回 21，如果我们运行 getWeight(7) (9,10) 也是如此。 getWeight(2) = 7。我写了这样的方法，但有时我会遇到 Stack Overflow Exception :(
private void getWeight(Object node, Object source) {
Collection nodeCollection = graph.getNeighbors(node);
for (Object n : nodeCollection) {
if ((Integer) n == 0) {
weight += ((MyEdge) (graph.findEdge(startNode, node))).getW();
} else {
if (n != source) {
weight += ((MyEdge) (graph.findEdge(node, n))).getW();
getWeight(n, node);
} else {
}
}
}
return weight;
}
我正在使用 jung2 库。
请帮忙，你是我最后的希望!
@Zim-Zam O'Pootertoot:像这样？
ArrayList<Boolean> visited = new ArrayList<Boolean>();
public void getWeight2(Object i) {
visited.set((Integer) i, true);
for (Object v : getGraph().getNeighbors(i)) {
if (!visited.get((Integer) v)) {
if (getGraph().getNeighborCount(v) > 1 & !v.equals(startNode)) {
weight += ((MyEdge) getGraph().findEdge(i, v)).getW();
getWeight2(v);
} else {
weight += ((MyEdge) getGraph().findEdge(i, v)).getW();
}
}
}
}
还是SOExp ;(
最佳答案
看起来你在重复计算节点。您可以创建一个 HashSet 并将其传递给包含您已经访问过的节点的 getWeight； for 循环将跳过集合中的节点，并将 nodeCollection 与哈希集合并。
另一种选择是在您的节点中放置一个已访问标志 - 将它们初始化为假，并在您访问该节点时将它们设置为真。棘手的部分是在你完成后将所有标志重置为 false - 为此，我建议你保留所有节点的单独列表，以便你可以遍历它以重置标志而无需再次遍历你的图表.
关于java - 计算子图的权重，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16091260/