coursera review—algorithms,Stanford—04—BFS & DFS

1 #include <map>
 2 #include <vector>
 3 #include <queue>
 4 #include <stack>
 5 
 6 using namespace std;
 7 
 8 typedef map<int, vector<int> > graphType;
 9 
10 void BFS(graphType graph, int starter, map<int, int> & visitTime) {
11     queue<int> Q;
12     Q.push(starter);
13     map<int, bool> visited;
14     for (auto i : graph) {
15         visited[i.first] = false;
16     }
17     int time = 0;
18     int node = 0;
19     while (!Q.empty()) {
20         node = Q.front();
21         Q.pop();
22         if (!visited[node]) {
23             visited[node] = true;
24             visitTime[node] = time++;
25             for (int i : graph[node]) {
26                 Q.push(i);
27             }
28         }
29     }
30 }
31 
32 void DFS(graphType graph, int starter, map<int, int> & visitTime) {
33     stack<int> S;
34     S.push(starter);
35     map<int, bool> visited;
36     for (auto i : graph) {
37         visited[i.first] = false;
38     }
39     int time = 0;
40     int node = 0;
41     while (!S.empty()) {
42         node = S.top();
43         S.pop();
44         if (!visited[node]) {
45             visited[node] = true;
46             visitTime[node] = time++;
47             for (auto i = graph[node].rbegin(); i != graph[node].rend(); ++i) {
48                 S.push(*i);
49             }
50         }
51     }
52 }

P.S.

this code uses C++11 features
原文链接: https://www.cnblogs.com/haoyancoder/p/3265695.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍