- 【用途】用來遍歷樹(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";
}
}
- 【更多練習】ZeroJudge c812: 1. 觀光景點 【題解】
- 【更多練習】ZeroJudge c877: 107北二4.環保愛地球 【題解】
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)