5.2 图的遍历
5.2.1 广度优先搜索
概念
广度优先搜索（也称宽度优先搜索，缩写BFS）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。
基本步骤
1.给出一连通图，如图，初始化全是白色（未访问）；
2.搜索起点V1（灰色）；
3.已搜索V1（黑色），即将搜索V2，V3，V4（标灰）；
4.对V2，V3，V4重复以上操作；
5.直到终点V7被染灰，终止；
模板
/* 通过邻接矩阵实现BFS */ #include <iostream> #include <queue> using namespace std; #define MaxVertexNum 10 struct Graph { int vertexnum; int edgenum; bool visit[MaxVertexNum]; int edgeList[MaxVertexNum][MaxVertexNum]; }; void BuildGraph(Graph *G) { int start, end; cout << "Please enter the number of vertices and edges" << endl; cin >> G->vertexnum >> G->edgenum; // 图的权重初始化 for (int i = 0; i < G->vertexnum; i++) { G->visit[i] = false; for (int j = 0; j < G->vertexnum; j++) { G->edgeList[i][j] = 0; } } // 输入权重信息 for (int i = 0; i < G->edgenum; i++) { cout << "Please enter the Start number, end number, weight" << endl; cin >> start >> end; cin >> G->edgeList[start][end]; G->edgeList[end][start] = G->edgeList[start][end]; } cout << endl; } void BFS(Graph *G) { queue<int> q; G->visit[0] = true; q.push(0); while (!q.empty()) { int tmp = q.front(); q.pop(); for (int i = 0; i < G->vertexnum; i++) { if (G->edgeList[tmp][i] && !G->visit[i]) { G->visit[i] = true; q.push(i); cout << i << "Visited" << endl; } } } } int main() { Graph G; BuildGraph(&G); BFS(&G); cout << endl; system("pause"); return 0; } /* 7 9 0 2 1 0 1 1 0 3 1 1 2 1 2 3 1 2 4 1 3 6 1 1 5 1 5 6 1 */
总结
广度优先搜索就是访问根结点相邻的所有结点，同时相邻的结点被访问后进入队列，然后依次出队，访问所有未访问结点。类似与水波一圈一圈荡开的结构。
5.2.2 深度优先搜索
概念
深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
基本步骤
1.对于下面的树而言，DFS方法首先从根节点1开始
2.从stack中访问栈顶的点；
3.找出与此点邻接的且尚未遍历的点，进行标记，然后放入stack中，依次进行；
4.如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照（3）依次进行；
5.直到遍历完整个树，stack里的元素都将弹出，最后栈为空，DFS遍历完成。
模板
/* 通过邻接表实现DFS */ #include #include using namespace std; #define MaxVertexNum 10 struct EdgeNode { int adjvex; EdgeNode *next; }; struct VertexNode { EdgeNode *firstedge; }; struct Graph { int vertexnum; int edgenum; VertexNode vertexList[MaxVertexNum]; bool visit[MaxVertexNum]; }; void BuildGraph(Graph *G) { int start, end, weight; EdgeNode *newnode; cout << "Please enter the number of vertices and edges" << endl; cin >> G->vertexnum >> G->edgenum; // 图的顶点数据 for (int i = 0; i < G->vertexnum; i++) { G->vertexList[i].firstedge = NULL; G->visit[i] = false; } // 输入权重信息 for (int i = 0; i < G->edgenum; i++) { cout << "Please enter the Start number, end number" << endl; cin >> start >> end; //start-->end newnode = new EdgeNode; newnode->adjvex = end; newnode->next = G->vertexList[start].firstedge; G->vertexList[start].firstedge = newnode; // end-->start newnode = new EdgeNode; newnode->adjvex = start; newnode->next = G->vertexList[end].firstedge; G->vertexList[end].firstedge = newnode; } } void Print_Adjacency_Matrix(Graph G) { for (int i = 0; i < G.vertexnum; i++) { cout << i << '\t'; EdgeNode *p = G.vertexList[i].firstedge; while (p) { printf("adjvex:%d ", p->adjvex); p = p->next; } cout << endl; } } void DFS(Graph *G) { stack s; s.push(0); G->visit[0] = true; while (!s.empty()) { int tmp = s.top(); EdgeNode *p = G->vertexList[tmp].firstedge; while (p) { if (G->visit[p->adjvex]) { p = p->next; } else { cout << "-->" << p->adjvex; s.push(p->adjvex); G->visit[p->adjvex] = true; // 找到下一深度的点就不再周边广搜 break; } // 周围没有待访问的点，出栈 if (p == NULL) { s.pop(); } } } } int main() { Graph G; BuildGraph(&G); Print_Adjacency_Matrix(G); DFS(&G); cout << endl; system("pause"); return 0; } /* 9 10 0 1 0 7 1 2 1 4 7 5 7 8 2 3 4 3 5 3 5 6 */
总结
深度优先搜索就是一条道走到黑，然后到无路可走的时候回头。所以说最后会回溯所有的点。
