0

何日も問題に苦しんでいて、適切な解決策が見つからなかったため、あなたの助けを求める必要があります. ノード (私のメソッドのパラメーターになる) を含み、中央ノード 0 で終わる subgrah の重みを見つけたいと思います。ばかげているように聞こえますが、ここでは画像が非常に役立ちます ( http://img542.imageshack. us/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

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 に答える