java - 计算子图的权重

标签 java algorithm graph-algorithm jung

我需要寻求你的帮助,因为我已经为我的问题苦苦挣扎了很多天,但没有找到任何合适的解决方案。我想找到包含节点(将成为我的方法的参数)并将以中心节点 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 并将其传递给包含您已经访问过的节点的 getWeightfor 循环将跳过集合中的节点,并将 nodeCollection 与哈希集合并。

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

关于java - 计算子图的权重,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16091260/

相关文章:

algorithm - 颜色渐变算法

algorithm - 具有单一来源、单一目标点的修改后的 Dijkstra 和统一成本搜索之间有什么区别?

database - 存储路线数据

algorithm - 如何跟踪广度优先搜索的深度?

java - Testcontainer 的 Redis 容器连接到与测试中定义的容器不同的容器

java - RCP 3 - 锁定工具栏菜单贡献

c++ - 我应该使用什么算法在流量有下限但没有上限的有向图中找到最小流量?

algorithm - 解决迷宫的最佳算法?

java - 如何使用netbeans ide对jtable记录进行过滤

java - 线程会降低 PC 速度并导致 java.lang.OutOfMemoryError