Breadth-First Search

深度堆疊[]，廣度佇列deque()。

先進先出的取法，常見於樹，圖問題。

背景知識

• 前序 (preorder): 中 -> 左 -> 右：BFS, DFS。
• 中序 (inorder): 左 -> 中 -> 右：二元搜尋樹中正好小到大。
• 後序 (postorder): 左 -> 右 -> 中

理解問題

廣度走訪圖

思路視覺化

      A
    /   \
   B     C
  / \   /
 D   E-F
 
可以利用函式前序遞迴DFS：ABCDEF

1. 從佇列取出某節點
2. 找相鄰判斷是否看過

Java

TC, SC:
List: O(V+E)
Matrix: O(V^2)

import java.util.*;
class BFS {
    private static void bfs(Map<Character, Character []> graph, Character node, Set visited){
        //https://www.runoob.com/java/data-queue.html
        Queue<Character> queue = new LinkedList<Character>();
        queue.offer(node);
        visited.add(node);
        
        while(!queue.isEmpty()){
            node = queue.poll();
            System.out.println(node);
            for(Character neighbor:graph.get(node)){
                if(!visited.contains(neighbor)){
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }
    private static void stackBfs(Map<Character, Character []> graph, Character node, Set visited){
        Deque<Character> stack = new LinkedList<>();
        stack.push(node);
        visited.add(node);
        
        while(!stack.isEmpty()){
            node = stack.pollLast();
            System.out.println(node);
            
            for(Character neighbor:graph.get(node)){
                if(!visited.contains(neighbor)){
                    stack.push(neighbor);
                    visited.add(neighbor);
                }
            }            
        }        
    }
    private static void printMap(Map<Character, Character []> graph){
        for (Map.Entry<Character, Character []> entry : graph.entrySet()){
                System.out.println(entry.getKey() + ":" + Arrays.toString(entry.getValue()));
        }
    }
    public static void main(String[] args) {
        /*
            graph = {
                'A' : ['B','C'],
                'B' : ['D', 'E'],
                'C' : ['F'],
                'D' : [],
                'E' : ['F'],
                'F' : []
            }
        */
       Map<Character, Character []> graph = new HashMap<Character, Character []>();
  
        graph.put('A', new Character [] {'B','C'});
        graph.put('B', new Character [] {'D', 'E'});
        graph.put('C', new Character [] {'F'});
        graph.put('D', new Character [] {});
        graph.put('E', new Character [] {'F'});
        graph.put('F', new Character [] {});
        
        printMap(graph);
        
        System.out.println("Queue BFS: ");
        Set visited=new HashSet(); 
        bfs(graph, 'A', visited);

        System.out.println("Stack BFS: ");      
        visited=new HashSet(); 
        stackBfs(graph, 'A', visited);
    }
}
>
java -cp /tmp/fqlpjpJwBO BFS
A:[B, C]
B:[D, E]
C:[F]
D:[]
E:[F]
F:[]
Queue BFS: 
A
B
C
D
E
F
Stack BFS: 
A
B
C
D
E
F

Python

from collections import deque

graph = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

visited = set()
def bfs(graph, node):
  queue.append(node) # 層
  visited.add(node)
  
  while queue:
    node = queue.popleft() # FIFO, 各層左
    print(node) 

    for neighbor in graph[node]:
      if neighbor not in visited:
        queue.append(neighbor)
        visited.add(neighbor)

queue = deque() # deque(stack)
bfs(graph, 'A')

>
A
B
C
D
E
F

# 用stack

visited = set()
def bfs(graph, node):
  queue.append(node) # 層
  visited.add(node)
  
  while queue:
    node = queue.pop(0) # FIFO, 各層左右
    print(node) 

    for neighbor in graph[node]:
      if neighbor not in visited:
        queue.append(neighbor)
        visited.add(neighbor)

queue = [] # stack
bfs(graph, 'A')

>
A
B
C
D
E
F

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)