1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #include <stdio.h>
#include <vector>
#include <iostream>
#include <stack>
#include <queue>
/**
* 路径的权值为1，就是两个结点相连，为0，则为两个结点不相连
**/
class Graphic {
private:
std::vector<std::vector<int>> g;
public:
Graphic(std::vector<std::vector<int>> &g):g(g){
}
/**
*深度优先遍历（递归）
**/
void DFS_Recursive(int node_id){
//储存结点是否被访问
std::vector<bool> Visited(g.size());
visit(Visited,node_id);
}
/**
*深度优先遍历（非递归）
**/
void DFS(int node_id){
std::vector<bool> visited(g.size());
std::stack<int> stack;
stack.push(node_id);
while (stack.size()>0) {
int visitedNode = stack.top();
stack.pop();
//判断是否访问过
if (!visited[visitedNode]) {
std::cout<<"dfs visit is "<<visitedNode<<std::endl;
visited[visitedNode] = true;
for (int i=0; i<g.size(); i++) {
if (visited[i]==false&&g[visitedNode][i]==1) {
stack.push(i);
}
}
}
}
}
/**
*广度优先遍历（非递归）
**/
void BFS(int node_id){
std::vector<bool> visited(g.size());
std::queue<int> queue;
queue.push(node_id);
while (queue.size()>0) {
int visitedNode = queue.front();
queue.pop();
if (!visited[visitedNode]) {
std::cout<<"bfs visit is "<<visitedNode<<std::endl;
visited[visitedNode] = true;
for (int i=0; i<g.size(); i++) {
if (visited[i]==false&&g[visitedNode][i]==1) {
queue.push(i);
}
}
}
}
}
private:
void visit(std::vector<bool> &visited,int node_id){
visited[node_id] = true;
std::cout<<"dfs_recursive visit is "<<node_id<<std::endl;
for (int i=0; i<visited.size(); i++) {
if (g[node_id][i]==1&&!visited[i]) {
visit(visited, i);
}
}
}
};
|