Depth-First Search

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

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

背景知識

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

理解問題

深度走訪圖

思路視覺化

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

非遞迴
1. 陣列中取出某節點，看過跳下一個
2. 節點加入集合
3. 移動節點至連接節點

遞迴
1. 陣列中取出某節點，並加入看過集合
2. 有無看過，沒看過加入看過集合
3. 移動節點至連接節點

Java

List: O(V+E)
Matrix: O(V^2)

import java.util.*;
class DFS {
    private static void recDfs(Map<Character, Character []> graph, Character node, Set visited){
        if(!visited.contains(node)){
            System.out.println(node);
            visited.add(node);
        }
        for(Character next:graph.get(node)){
            recDfs(graph, next, visited);
        }
    }
    private static void dfs(Map<Character, Character []> graph, Character node, Set visited){
        Stack<Character> stack = new Stack<Character>();
        stack.push(node);
        
        while(!stack.empty()){
            node = stack.pop();
            if(!visited.contains(node)){
                System.out.println(node);
                visited.add(node);
            }
            for(Character next:graph.get(node)){
                dfs(graph, next, visited);
            }
        }
    }
    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("Recursive DFS: ");
        Set visited=new HashSet(); 
        recDfs(graph, 'A', visited);

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

Python

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

# 遞迴

visited = set()
def dfs(graph, node):
    if node not in visited: # set "in"nex is O(1)
        print(node)
        visited.add(node)
      
        for next in graph[node]: 
        	dfs(graph, next) # recursive


dfs(graph, 'A')

>
A
B
D
E
F
C


# 非遞迴

visited = set()
def dfs(graph, node):
    stack = [node] # 層
    
    while stack:
        node = stack.pop() # pop last(connected node)
        
        if node not in visited:  # set "in" is O(1)
        	print(node)
        	visited.add(node)
        
        for next in reversed(graph[node]): # FILO, 各層左右，右邊開始要reversed
        	stack.append(next)

dfs(graph, 'A')

> 
A
B
D
E
F
C

問題

1. BFS

---

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