深度优先遍历/搜索（DFS）

基本思想

对于连通图：从初始访问顶点开始，先访问第一个邻接顶点，再以这个邻接顶点为新的初始顶点，访问它的第一个邻接顶点对于非连通图：对图的连通分量分别进行深度优先遍历这种方式是优先纵向深入这是一个递归的过程

算法实现

邻接矩阵的实现

boolean[] isVisited ; //记录顶点是否已被访问过 void dfs(Graph<?> G) { //开始时所有顶点均未访问 isVisited = new boolean[G.getNumOfVertexes()]; for(int i = 0;i < isVisited.length; i++) isVisited[i] = false; //遍历所有顶点，进行DFS for(int i = 0; i < G.getNumOfVertexes(); i++) if( !isVisited[i]) dfs(G, i); } //DFS递归算法部分 void dfs(Graph<?> G, int i) { //访问该顶点 System.out.println(G.getValueByIndex(i).toString()); //标记为已访问 isVisited[i] = true; //访问下个邻接顶点 int j = 0; for(j = 0; j < G.getNumOfVertexes(); j++) if(G.edges[i][j] != Graph.INFINITY && G.edges[i][j] != 0 && !isVisited[j]) //有边且未被访问 dfs(G, j); }

算法分析

邻接矩阵结构：邻接矩阵是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，所以算法时间复杂度为O(n²)

广度优先遍历/搜索（BFS）

基本思想

类似于树的层序遍历使用一个辅助队列首先，将初始顶点入队列，当队列不为空的时候使队列中第一个顶点出队，将出队顶点的所有未访问过的邻接顶点入队，循环上述过程，就遍历了整个图实质上是先遍历初始顶点的所有邻接顶点，再遍历邻接顶点的邻接顶点，一层层遍历

算法实现

邻接矩阵的实现

//BFS void bfs(Graph<?> G) { //使用辅助队列（链表） LinkedList<Integer> queue = new LinkedList<>(); //开始时所有节点均未被访问 boolean[] isVisited = new boolean[G.getNumOfVertexes()]; for(int i = 0; i < G.getNumOfVertexes(); i++) isVisited[i] = false; //遍历所有顶点，进行BFS for(int i = 0; i < G.getNumOfVertexes(); i++) { //对未被访问的顶点搜索 if(!isVisited[i]) { //访问该顶点 System.out.println(G.getValueByIndex(i).toString()); //一个访问动作 isVisited[i] = true; //将该顶点标记为已访问 queue.addLast(i); //将此顶点入队列 while(!queue.isEmpty()) { i = queue.removeFirst(); //移除现队列中第一个顶点，赋给i for(int j = 0; j < G.getNumOfVertexes(); j++) { //访问下个邻接顶点 if(G.edges[i][j] != Graph.INFINITY && G.edges[i][j] != 0 && !isVisited[j]) //有边且未被访问 { //访问该顶点 System.out.println(G.getValueByIndex(j).toString()); //一个访问动作 isVisited[j] = true; //将该顶点标记为已访问 queue.addLast(j); //将此顶点入队列 } } } } } }

算法分析

邻接矩阵结构：邻接矩阵是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，所以算法时间复杂度为O(n²)

两种算法时间复杂度是一样的，区别在于对顶点的访问顺序不同

当遍历图的时间很长，目的是为了寻找合适的顶点时 深度优先遍历适合目标比较明确，以找到目标为主要目的的情况 广度优先遍历适合在不断扩大遍历范围时找到相对最优解的情况