1.广度优先搜索 BFS
基本思想： 1 随机选定一个起始点v 2 从v出发访问v的所有未被访问的邻接结点 3 从这些结点出发再依次访问其未被访问的邻接结点 4 重复上述过程直到图中所有结点都被访问过 5 如果到最后有结点访问不到，则另选一个起始点v重新进行搜索 可以看出，这个算法和dijkstra算法/prim算法都比较类似，但不属于递归算法，因为算法过程中没有回溯 之所以说广度优先算法和数的层序遍历类似，是因为这个算法是从起始点出发，由近及远依次访问和v有路径联通的结点 广度优先算法在实现过程中需要借助一个辅助队列存储下一层的待访问结点 伪代码： ``` bool visited[MAX_VERTEX_NUM];//标记当前节点是否被访问 void BFSTraverse(Graph G){ for(i=0;i<G.vexnum;++i) visited[i]=false;//初始化标记数组，初始时所有节点都未被访问 InitQueue(Q);//初始化辅助队列Q for(i=0;i<G.vexnum;++i) if(!visited[i]) BFS(G,i);//对于每一个未被访问的结点，从它开始进行广度优先遍历 } void BFS(Graph G,int v){ visit(v);//在标记数组中对v进行标记 visited[v]=true; Enqueue(Q,v);//先将当前这一层访问的结点入队，为了依次从他们出发访问后面的结点 while(!isEmpty(Q)){ Dequeue(Q,v); for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))//从头遍历所有与v邻接的顶点 if(!visited[w]){//如果当前节点w未被访问，则对其进行访问，并更新访问数组 visit(w); visited[w]=true; Enqueue(Q,w);//把访问过的w入队，从而在后面继续对w的邻接结点进行访问 }//if }//while } ``` 图的广度优先算法可以看成树的层序遍历算法的扩展和推广 用BFS算法求一些问题的最优解（单源路径最短问题）（初始中涉及比较少，先不看） **广度优先生成树**：在BFS算法执行的过程中产生的一棵遍历树，称为广度优先生成树。 注意，图的邻接矩阵表示是唯一的，而邻接表是不唯一的(顶点的边表中各边的顺序可以任意)，所以用邻接矩阵表示是，广度优先生成树唯一，而用邻接表表示时生成树不唯一 BFS算法的性能分析： 空间复杂度：O(|V|) 即辅助队列所需空间 时间复杂度：如果用邻接表，则为O(V+E)，用邻接矩阵，则为O(V^2)。2，深度优先搜索 DFS
DFS算法类似于树的先序遍历算法 算法基本思想： 1 访问图中某一起始顶点v 2 从v出发访问任意一个与它邻接但是没有被访问过的结点 3 重复上述的操作，每次只访问一个新节点 4 当不能再继续向下访问时，回退到上一个节点，从该点开始访问其他未被访问的结点 5 重复上述步骤直到图中所有顶点都被访问过为止 DFS算法中需要进行回溯，所以是一种递归算法 代码描述： ``` bool visited[MAX_VERTEX_NUM];//记录访问状态的数组 void DFSTraverse(Graph G){ for(v=0;v<G.vexnum;++v) visited[v]=false;//初始化访问状态数组 for(v=0;v<G.vexnum;++v) if(!visited[v]) DFS(G,v);//从每个顶点为起点，执行深度优先算法 } void DFS(Graph G,int v){ visit(v); visited[v]=true; for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v)) if(!visited[v]) DFS(G,w);//向深一层递归 //如果当前访问的结点的所有邻接结点都被访问过，则会退出循环，回退到上一层的DFS函数中去 //这时会继续向这个节点的下一个未被访问的邻接结点进行访问 //其算法思想可以概括为 先遍历到尽头，再慢慢回退补充 } ``` 与BFS算法相同，对于一个图来说，用邻接矩阵表示时，其DFS遍历结果是唯一的，而用邻接表表示时结果是不唯一的 **算法性能分析** 空间复杂度：O(v)，因为需要借助栈进行递归 时间复杂度：用邻接矩阵时，为O(v^2)，用邻接表时，为O(V+E) 深度优先算法的执行结果可能是生成树，也可能是生成森林（非连通图的情况）图的遍历与连通性的关系
可以通过图的遍历算法的结果来判断图的连通性
*复习：连通是指，无向图中任意两个顶点间都有通路（可以是间接通路），而有向图中只有强连通的概念：任意两个顶点相互之间都有通路相互到达*
对于无向图，连通 == 从**任意一个**结点出发可以通过遍历直接访问到所有节点。
若无向图是非联通的，则从一个顶点出发只能访问到**该顶点所在连通分量**的所有节点