兩種遍歷
圖的遍歷分為深度優(yōu)先搜索(Depth First Search)和廣度優(yōu)先搜索
深度優(yōu)先搜索(DFS)
順著起始節(jié)點(diǎn)的一條邊一直找下去，知道這條邊上的節(jié)點(diǎn)全部被找完汉额，然后再開始順著另一條邊尋找分瘦。
廣度優(yōu)先搜索(BFS)
選起始節(jié)點(diǎn)連接的所有邊稍计，然后將這些邊的尾節(jié)點(diǎn)中沒有訪問的加入待尋找節(jié)點(diǎn)結(jié)合T燎斩，起始點(diǎn)置為已訪問辖佣，接著尋找T中每一個(gè)點(diǎn)連接的邊缨恒，并將尾節(jié)點(diǎn)加入T谴咸，直到T中包含所有的節(jié)點(diǎn)并且都已訪問。
例子說明
深度和廣度優(yōu)先搜索.jpg
深度優(yōu)先搜索結(jié)果為：A B C E F D G H
廣度優(yōu)先搜索結(jié)果為：A B D C F G H E
可以看出深度優(yōu)先搜索就是先一條路走到底骗露，再去走另外的路
廣度優(yōu)先搜索就是一層一層的訪問
上代碼
深度優(yōu)先搜索(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);
}
}
}
}
廣度優(yōu)先搜索(BFS)
需要使用兩個(gè)結(jié)合來存儲(chǔ)上層訪問的節(jié)點(diǎn)和下一層待訪問的節(jié)點(diǎn)岭佳，然后遞歸調(diào)用 breadthFirstTraverseIndex()
void MyGraph::breadthFirstTraverse(int node_index) {
cout << this->node_array[node_index].data << " ";
//已經(jīng)訪問過的節(jié)點(diǎn)就不再訪問
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 << " ";
//已經(jīng)訪問過的節(jié)點(diǎn)就不再訪問
this->node_array[j].is_visited = true;
last.push_back(j);
}
}
}
}
this->breadthFirstTraverseIndex(last);
}
