java - 计算子图的权重

Question

我需要寻求你的帮助，因为我已经为我的问题苦苦挣扎了很多天，但没有找到任何合适的解决方案。我想找到包含节点(将成为我的方法的参数)并将以中心节点 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 ;(

Answer 1

看起来你在重复计算节点。您可以创建一个 HashSet 并将其传递给包含您已经访问过的节点的 getWeight； for 循环将跳过集合中的节点，并将 nodeCollection 与哈希集合并。

另一种选择是在您的节点中放置一个已访问标志 - 将它们初始化为假，并在您访问该节点时将它们设置为真。棘手的部分是在你完成后将所有标志重置为 false - 为此，我建议你保留所有节点的单独列表，以便你可以遍历它以重置标志而无需再次遍历你的图表.