以下是基于图的链表表示的:
dfs和bfs的演示:
http://sjjg.js.zwu.edu.cn/SFXX/sf1/gdyxbl.html (深搜)
http://sjjg.js.zwu.edu.cn/SFXX/sf1/sdyxbl.html (广搜)
bfs通过检测边发现点,被发现点(但未探索)入队。(被探索是指是否检测过与该点相关联的临近顶点)一个顶点被完全探索当且仅当他的所有边被检测。一个顶点探索完选另一个顶点,被选点应位于被发现但未被探索点队列的队首。待探索点集为空时算法结束。(bfs探索顺序与发现顺序一致,dfs发现后马上探索)
1 #include <iostream>
2 #include <cstdio>
3 #include <list>
4 #include <vector>
5 #include <queue>
6 using namespace std;
7 int n;
8 vector< list<int> > graph;
9 bool visited[100] = {0};
10 void dfs(int v)
11 {
12 list<int>::iterator it;
13 visited[v] = true;
14 printf("%5d", v);
15 for (it = graph[v].begin(); it != graph[v].end(); ++it)
16 if (!visited[*it])
17 dfs(*it);
18 }
19 void bfs(int v)
20 {
21 list<int>::iterator it;
22 printf("%5d", v);
23 visited[v] = true;
24 queue<int> t;
25 t.push(v);
26 while (!t.empty())
27 {
28 v = t.front();
29 t.pop();
30 for (it = graph[v].begin(); it != graph[v].end(); ++it)
31 if (!visited[*it])
32 {
33 printf("%5d", *it);
34 t.push(*it);
35 visited[*it] = true;
36 }
37 }
38 cout << endl;
39 }
40 int main()
41 {
42 //freopen("in.txt", "r", stdin);
43 cout << "input the vertex num:"<< endl;
44 cin >> n;
45 vector< list<int> >::iterator it;
46 for (int i = 0; i < n; ++i)
47 {
48 list<int> il;
49 int t;
50 while (cin >> t && t != n)
51 il.push_back(t);
52 graph.push_back(il);
53 }
54 cout << "result for bfs:" << endl;
55 bfs(0);
56 memset(visited, 0, sizeof(visited)); //重新初始化标志数组
57 cout << "result for dfs:" << endl;
58 dfs(0);
59 system("pause");
60 return 0;
61 }
按照链表表示输入以下数据:
8
0 1 2 8
1 0 3 4 8
2 0 5 6 8
3 1 7 8
4 1 7 8
5 2 7 8
6 2 7 8
7 3 4 5 6 8
最后一个8用来标识这个节点输入结束。可以得到深搜和广搜的结果。
原文链接: https://www.cnblogs.com/PegasusWang/archive/2013/04/06/3002511.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/83427
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!