0

我需要寻求您的帮助，因为我已经为我的问题苦苦挣扎了很多天，但没有找到任何合适的解决方案。我想找到包含节点（将成为我的方法的参数）的 subgrah 的权重，并将以中心节点 0 结束。我知道这听起来很愚蠢，但图像在这里会有很大的帮助（http://img542.imageshack。我们/img542/5400/zrzutekranu20130418o205.png）。例如 getWeight(8) 将返回 21，如果我们运行 getWeight(7) (9,10) 则相同。getWeight(2) = 7。我写了这样的方法，但有时我得到堆栈溢出异常:(

    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 lib。

请帮忙，你是我最后的希望！

@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 ;(

4

2 回答 2

2

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

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

于 2013-04-18T19:20:51.350 回答
1

我对jung一无所知，但是这个伪 java 概述了一种方法来计算您正在寻找的权重，它保留了一个地图来追踪访问过的节点和访问过的边（以避免重新计算任何时候），您必须使用 api 等效方法填补空白并进行调整：

private int calculateWeight(Object startNode, HashMap<Node, Boolean> visitedNodes, HashMap<Edge, Boolean> visitedEdges) {
    int w = 0;
    if (!visitedNodes.get(startNode)) {
        // Don't know if this method (getEdeges) exists, but if you could implement 
        // a way to get all the edges that go out from a node, then paste the code  here 
        //
        // Get the edges from the node
        Collection edges = startNode.getEdges();

        for (Object edge : edges) { 
            // If the edge haven't been visited, then add its weight to w
            if (!visitedEdges.get(edge)) {
                w += edge.getW();
                // Mark the edge as visited 
                visitedEdges.put(edge, true);
            }
        }
        // We are done with this node, mark it as visited
        visitedNodes.put(startNode, true);

        // Check the neighbors of this node recursively 
        Collection neighborNodes = getGraph().getNeighbors(startNode);
        for (Object node : neighborNodes) {
            // Go recursively with this node, passing in the visited nodes and edges maps to avoid recounting
            w += calculateWeight(node, visitedNodes, visitedEdges);                
        }
    }
    return w;
}

// Then, use the above method like this 
public static void main(String... args) { 
    HashMap<Node, Boolean> visitedNodes = new HashMap<Node, Boolean>();
    HashMap<Edge, Boolean> visitedEdges = new HashMap<Edge, Boolean>();

    // Search the startNode and nodeZero from the graph...

    // Add the Node 0 to the visitedNodes map, so the zero node won't be processed 
    visitedNodes.put(nodeZero, true);

    int w = calculateWeight(startNode, visitedNodes, visitedEdges);
}

警告：这只是一个伪java，我没有测试过

希望这有助于或至少给你一个提示来解决问题

于 2013-04-18T21:34:31.793 回答