body, table{font-family: 微软雅黑; font-size: 13.5pt}
table{border-collapse: collapse; border: solid gray; border-width: 2px 0 2px 0;}
th{border: 1px solid gray; padding: 4px; background-color: #DDD;}
td{border: 1px solid gray; padding: 4px;}
tr:nth-child(2n){background-color: #f8f8f8;}
从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历(Traversing Graph)
****注：图的建立上一篇博客《图的邻接矩阵存储实现》已经放了源代码了，这里要运行只要按代码加上相应的文件就能执行****
完整实现代码链接：https://github.com/meihao1203/learning/tree/master/06272018/GraphTraversal
深度优先遍历（DFS,Depth_First_Search）:
从图中某个顶点V出发，访问此顶点，然后从V的未被访问的邻接点触犯深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到。相当于树的前序遍历。针对非连通图，只要对每个连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
|
右图是递归遍历的过程，其实每一层都是从A结点开始搜寻满足条件的点 |
|
|
/* DFS.h */
#ifndef __DFS_H__ #define __DFS_H__ #include"Graph.h" namespace meihao { void DFS(const meihao::Graph& g,int vi,bool*& visited); //参数->图和顶点数组中某个顶点的下标 void DFSTraversal(const meihao::Graph& g); }; #endif /* testMain.cpp */ #include"DFS.h" #include<iostream> int main() { meihao::Graph g("data.txt"); meihao::DFSTraversal(g); cout<<endl; system("pause"); } /* data.txt */ 9 A B C D E F G H I 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 0 0 0 |
/* DFS.cpp */
#include"DFS.h" namespace meihao { //算法都是基于邻接矩阵实现的 void DFS(const meihao::Graph& g,int vi,bool*& visited) { visited[vi] = true; //修改第vi个结点的访问标记为true cout<<g.getGraphVertexData(vi)<<" "; for(int idx=0;idx!=g.getGraphVertexNumber();++idx) { if(1==g.getGraphEdgeWeight(vi,idx)&& false==visited[idx]) //如果(vi,idx)之间存在边（==1），并且第idx个顶点还没有访问过 { DFS(g,idx,visited); //递归遍历第idx个顶点 } } } void DFSTraversal(const meihao::Graph& g) { bool* visited = new bool[g.getGraphVertexNumber()](); for(int idx=0;idx!=g.getGraphVertexNumber();++idx) { visited[idx] = false; //初始化访问标记，全部为false，表示未访问 } for(int idx=0;idx!=g.getGraphVertexNumber();++idx) { if(false==visited[idx]) //随便选一个点，如果未访问过，就从它开始深度优先遍历 DFS(g,idx,visited); } } }; |
广度优先遍历（Breadth First Search）:
类似于图的层序遍历，
| /* BFS.h */
#ifndef __BFS_H__ #define __BFS_H__ #include"Graph.h" namespace meihao { void BFSTraversal(const meihao::Graph& g); }; #endif /* test.cpp */ #include"BFS.h" #include<iostream> int main() { meihao::Graph g("data.txt"); meihao::BFSTraversal(g); cout<<endl; system("pause"); } /* data.txt */ 9 A B C D E F G H I 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 0 0 0 |
/* BFS.cpp */
#include"BFS.h" #include<queue> namespace meihao { void BFSTraversal(const meihao::Graph& g) { //广度优先遍历相当于层序遍历 queue<int> rootNode; //存放图的顶点 bool* visited = new bool[g.getGraphVertexNumber()]; for(int idx=0;idx!=g.getGraphVertexNumber();++idx) { visited[idx] = false; } for(int idx=0;idx!=g.getGraphVertexNumber();++idx) { //if语句可以确保如果图中有多个连通分量，也能每个点都访问到 if(false==visited[idx]) //如果该结点没有访问到 { //访问 cout<<g.getGraphVertexData(idx)<<" "; visited[idx] = true; rootNode.push(idx); while(!rootNode.empty()) //把刚刚访问到的结点的下一层结点访问并入队列 { for(int iidx=0;iidx!=g.getGraphVertexNumber();++iidx) { if(1==g.getGraphEdgeWeight(rootNode.front(),iidx)&& false==visited[iidx]) { cout<<g.getGraphVertexData(iidx)<<" "; visited[iidx] = true; rootNode.push(iidx); } } rootNode.pop(); //最先访问的一个结点出队列 } } } } }; |
两种遍历算法在时间复杂度上是一样的
深度优先遍历算法适合图和边都非常多，要找到合适的顶点
广度优先遍历算法适合不断扩大遍历范围时找到相对最优解
