两种遍历
图的遍历分为深度优先搜索(Depth First Search)和广度优先搜索
深度优先搜索(DFS)
顺着起始节点的一条边一直找下去，知道这条边上的节点全部被找完，然后再开始顺着另一条边寻找。
广度优先搜索(BFS)
选起始节点连接的所有边，然后将这些边的尾节点中没有访问的加入待寻找节点结合T，起始点置为已访问，接着寻找T中每一个点连接的边，并将尾节点加入T，直到T中包含所有的节点并且都已访问。
例子说明
深度和广度优先搜索.jpg
深度优先搜索结果为：A B C E F D G H
广度优先搜索结果为：A B D C F G H E
可以看出深度优先搜索就是先一条路走到底，再去走另外的路
广度优先搜索就是一层一层的访问
上代码
深度优先搜索(DFS)
void MyGraph::depthFirstTraverse(int node_index) {
cout << this->node_array[node_index].data << " ";
this->node_array[node_index].is_visited = true;
for (int i = 0; i < this->num; i++) {
if (this->array[node_index * this->num + i] != 65535) {
if (!this->node_array[i].is_visited) {
depthFirstTraverse(i);
}
}
}
}
广度优先搜索(BFS)
需要使用两个结合来存储上层访问的节点和下一层待访问的节点，然后递归调用 breadthFirstTraverseIndex()
void MyGraph::breadthFirstTraverse(int node_index) {
cout << this->node_array[node_index].data << " ";
//已经访问过的节点就不再访问
this->node_array[node_index].is_visited = true;
vector<int> cur;
cur.push_back(node_index);
this->breadthFirstTraverseIndex(cur);
}
void MyGraph::breadthFirstTraverseIndex(vector<int> previous) {
if (previous.size() <= 0) {
return;
}
vector<int> last;
for (int i = 0; i < previous.size(); i++) {
for (int j = 0; j < this->num; j++) {
if (this->array[previous[i] * this->num + j] != 65535) {
if (!this->node_array[j].is_visited) {
cout << this->node_array[j].data << " ";
//已经访问过的节点就不再访问
this->node_array[j].is_visited = true;
last.push_back(j);
}
}
}
}
this->breadthFirstTraverseIndex(last);
}
