【筆記】DFS (Depth First Search,深度優先搜尋)

  • 【用途】用來遍歷樹(tree)或圖(graph)的演算法。
  • 【觀念】由圖的某一點開始搜尋,先探尋鄰接邊(edge)上未搜尋的一點,並儘可能往深處搜索,直到最後,再回溯(backtracking)到前一個節點,持續拜訪未搜尋的節點,直到到達目標節點或已經遍歷所有節點。
  • 【實作】以遞迴(recursion)方式實現。
  • 【範例】ZeroJudge d908: 4. 最佳路徑題解
#include <iostream>
#include <map>
#include <vector>
using namespace std;
 
map <char, vector<pair<char, int> > > mp;
char start;
 
int func(int start, int total){
    if (!mp.count(start)) return total;
    int maxi = 0;
    for (pair<char, int> p: mp[start]){
        maxi = max(func(p.first, total+p.second), maxi);
    }
    return maxi;
}
 
int main() {
    int num;
    while (cin >> start >> num){
        mp.clear();
        char a, b;
        int n;
        for (int i = 0; i < num; i++){
            cin >> a >> b >> n;
            mp[a].push_back({b, n});
        }
        cout << func(start, 0) << "\n";
    }
}

Python code (credit: Amy Chou)
提醒:Python 預設的recursion depth很小,只有1000。如果遇到RecursionError: maximum recursion depth exceeded in comparison。放寬maximum recursion depth或可解決。

  • import sys
  • sys.setrecursionlimit(100000)
# Depth-First Search
def DFS(now, pre):
    print(now)
    for nxt in g[now]:
        if nxt == pre:
            continue
        DFS(nxt, now)

# main program
n = int(input())
g = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

print("DFS")
DFS(1, 0)
分享本文 Share with friends