Leaky Cauldron
0%

广度优先遍历

Posted on Edited on

树和图的广度优先遍历可借助一个队列和一个集合实现. 先将当前节点分别放入队列和集合中, 再依次出队, 出队元素将其下一个节点进队, 迭代即可实现广度优先遍历.

以上图为例, 图的节点定义及整体结构见上一篇博客

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class BFS {
    public static void bfs(GraphNode node) {
        if (node == null) return;

        Queue<GraphNode> queue = new LinkedList<>();
        HashSet<GraphNode> set = new HashSet<>();
        queue.add(node);
        set.add(node);
        while (!queue.isEmpty()) {
            GraphNode curNode = queue.poll();
            System.out.print(curNode.value + " ");
            for (GraphNode next : curNode.nexts) {
                if (!set.contains(next)) {
                    set.add(next);
                    queue.add(next);
                }
            }
        }
    }

    public static void main(String[] args) {
        // 无权重, 假定都为 1
        Integer[][] nodes = {
                {1, 1, 2},
                {1, 1, 3},
                {1, 1, 4},
                {1, 2, 3},
                {1, 2, 7},
                {1, 3, 5},
                {1, 4, 6},
                {1, 7, 3}
        };
        Graph graph = GraphBuilder.createGraph(nodes);
        bfs(graph.nodes.get(1));
    }
}
1
1 2 3 4 7 5 6
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from queue import Queue

def bfs(node):
    if not node: return

    ele_queue = Queue()
    ele_set = set()

    ele_queue.put(node)
    ele_set.add(node)

    while ele_queue.qsize() != 0:
        current_node = ele_queue.get()
        print(current_node.value, end=' ')
        for next_node in current_node.nexts:
            if next_node not in ele_set:
                ele_set.add(next_node)
                ele_queue.put(next_node)