1

ユーザーが jung を使用して描画したグラフの深さ優先トラバーサルを実装しています。

現時点では次のコードがあります。

 public <V,E> void dftdraw(Graph<V,E> g) {
    V start = null;      
    for (V v:g.getVertices()){
        if(v.toString().equals("0"))
           start = v; 
    }

    Set visited = new HashSet();
    LinkedList stack = new LinkedList();
    stack.add(start);
    System.out.println(start.toString());
    // traverse through graph in depth-first order
    while (!stack.isEmpty())
    {
        V v = (V)stack.removeFirst();
        visited.add(v);
        Set neighbors = (Set) g.getNeighbors(v);

        for (Iterator n_it = neighbors.iterator(); n_it.hasNext(); )
        {
            V w = (V)n_it.next();

            if (!visited.contains(w)){
                System.out.println(w.toString());
                stack.addFirst(w);
            }
        }
    }
}

しかし、これは深さを最初に行うのではなく、最初に接続された頂点に接続された頂点を最初に出力し、最初に接続された頂点をトラバースしてから、接続された頂点をトラバースします。

4

2 に答える 2

0

これは、頂点を印刷するのが早すぎるためです。訪問順に印刷したい場合は、訪問時に印刷する必要があります (スタックから頂点を削除した後)。それ以外の場合、アルゴリズムは問題ないようです。

于 2013-04-14T20:32:56.433 に答える