BFS主要功能
計算unweighted graph上的single source shortest path
時間複雜度
(1) 用adjacency-matrix : O(n^2)
(2) 用adjacency-list : O(n+m)
簡單範例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int color[N], d[N], pi[N], adj[N][N];void BFS(int s){ memset(color, 0, sizeof(color)); color[s] = 1, d[s] = 0, pi[s] = -1; deque<int> q; q.push_back(s); while (!q.empty()) { int u = q.front(); q.pop_front(); for (int v=1; v<=N; v++){ if (!color[v] && adj[u][v]){ color[v] = 1, d[v] = d[u]+1, pi[v] = u; q.push_back(u); } } }} |
