15

BFS を理解し、簡単に実装できます。

私の質問は、この BFS を特定の深さに制限するにはどうすればよいでしょうか? 10レベルの深さに行く必要があるとします。

4

6 に答える 6

27

これは、一定のスペースオーバーヘッドで実行できます。

depthBFSには、キュー内の未訪問のノードすべての深度が減少せず、最大で1増加するという特性があります。したがって、BFSキューからノードを読み取るときに、最初は単一の変数で現在の深度を追跡できます。0。

あなたがする必要があるのは、キュー内のどのノードが次の深さの増加に対応するかを記録することです。これを行うには、変数を使用して、timeToDepthIncreaseこのノードを挿入したときにすでにキューにある要素の数を記録し、キューからノードをポップするたびにこのカウンターをデクリメントします。

ゼロに達すると、キューからポップする次のノードは、新しい、より深い（1だけ）深さになります。したがって、次のようになります。

  • インクリメントdepth
  • pendingDepthIncreasetrueに設定

キューの子ノードをプッシュするときは常に、最初にpendingDepthIncreasetrueかどうかを確認してください。そうである場合、このノードはより深い深さになるためtimeToDepthIncrease、プッシュする前にキュー内のノードの数に設定し、pendingDepthIncreasefalseにリセットします。

最後にdepth、希望の深さを超えたら停止します！後で表示される可能性のあるすべての未訪問ノードは、この深さ以上である必要があります。

[編集：コメンターキーザーに感謝します。]

于 2012-10-31T02:25:56.750 に答える
2

クラス ノードを持たない (そしてノードに変数の深さを追加する) 場合は、距離と VisitedNodes の 2 つのマップ、または各行がノードで、column1:depth、column2: Visited の 2d 配列を持つことができます。もちろん、両方を 1 つで追跡できますmap<Node,Depth>(ここで、Node はクラスまたは int、String などのインスタンスであり、Depth はルート ノードからの Node の深さを表す int です)。マップにノード (O(1) コスト) が含まれている場合は訪問され、そうでない場合は続行され、現在のノードの深さ +1 でマップに追加されます。

public static void BfsToDepth(graph graphDb, Node rootNode, int depth) {
    if(depth<1)
       return;
    Queue<Node> queue = new LinkedList<>();
    ResourceIterator<Node> nodesIterator = graphDb.getAllNodes().iterator();
    LinkedHashMap<Node, Boolean> visited = new LinkedHashMap<>();
    LinkedHashMap<Node, Integer> distance = new LinkedHashMap<>();
    // Start: Bfs Init Step
    if (nodesIterator.hasNext() == true) {
        while (nodesIterator.hasNext()) {
            Node currentNode = nodesIterator.next();
            visited.put(currentNode, false);
            distance.put(currentNode, Integer.MAX_VALUE);
        }
    } else {
        System.out.println("No nodes found");
    }
    // End: Bfs Init Step 

    distance.put(rootNode, 0);
    visited.put(rootNode, true);
    queue.add(rootNode);
    Node current = null;

    while (queue.isEmpty() == false) {
        current = queue.poll();
        if (distance.get(current) <= depth) {
            Iterator<Relationship> relationships = current.getRelationships().iterator();
            if (relationships.hasNext() == true) {
                while (relationships.hasNext()) {
                    Relationship relationship = relationships.next();
                    Node adjacent = relationship.getOtherNode(current);

                    if (visited.get(adjacent) == false) {
                        /*if you want to print the distance of each node from root then 
                        System.out.println("len: "+ (distance.get(current) + 1)+" to: "+ adjacent);*/
                        distance.put(adjacent, (distance.get(current) + 1));
                        visited.put(adjacent, true);
                        queue.add(adjacent);
                    }
                }
            }
        }
    }
}
于 2016-11-03T18:18:41.513 に答える
0

これは機能します。訪問済みフラグが Node.js に存在しないと仮定します。isVisited が利用可能な場合、Map を追跡する必要はありません。

// k is depth, result should not contain initialNode.
public static Collection<Node> bfsWithK_Depth(Node initialNode, int k) {

    if (initialNode == null || k <= 0) {
        return new ArrayList<>();
    }

    Queue<Node> q = new LinkedList<>();
    q.add(initialNode);
    Map<Node, Node> tracker = new HashMap(); // no need if there is visited flag.
    Collection<Node> result = new ArrayList<>();

    while (!q.isEmpty()) { // Q will be filled only with eligible nodes
        --k ;
        Node node = q.remove();
        List<Node> neighbor = node.getNeighbor();
        for (Node n : neighbor) {
            if (tracker.get(n) == null && k > 0) {
                q.add(n);
            }
            if (tracker.get(n) == null) { 
                tracker.put(n, n); 
                result.add(n); // visit this node
            }
        }

    }
    return result;
}
于 2016-08-06T05:04:23.863 に答える