11.1.图的遍历
图的遍历，即将图内所有顶点都访问一遍。
有两种遍历方式：
- BFS
- DFS
以下图的遍历为例：
11.2.DFS
DFS（depth first search），深度优先搜索，先跑到叶节点，沿着原路返回，沿途遍历其他节点。
代码示例：
public class DFS { //图 static int[][] graph=new int[7][7]; //访问记录 static boolean[] isVisited=new boolean[7]; static { graph[0][1]=1;graph[0][2]=1;graph[0][3]=1; graph[1][0]=1;graph[1][2]=1; graph[2][0]=1;graph[2][1]=1;graph[2][3]=1;graph[2][4]=1;graph[2][5]=1; graph[3][0]=1;graph[3][2]=1;graph[3][4]=1; graph[4][2]=1;graph[4][3]=1; graph[5][2]=1; graph[5][6]=1; graph[6][5]=1; } public static void DFS(int i){ System.out.println(i); isVisited[i]=true; for(int j=0;j<graph[i].length;j++){ if(graph[i][j]==1&&isVisited[j]==false){ DFS(j); } } } public static void main(String[] args) { DFS(0); } }
11.3.BFS
BFS（Breadth first search），广度优先搜索，先遍历一度关系（直接相连），再遍历二度关系（直接相连的直接相连），再遍历三度关系（直接相连的直接相连的直接相连）……直到遍历完整个图。过程类似于树的层序遍历。
public class BFS { //图 static int[][] graph=new int[7][7]; //访问记录 static boolean[] isVisited=new boolean[7]; //队列 static LinkedList<Integer> queue=new LinkedList(); static { graph[0][1]=1;graph[0][2]=1;graph[0][3]=1; graph[1][0]=1;graph[1][2]=1; graph[2][0]=1;graph[2][1]=1;graph[2][3]=1;graph[2][4]=1;graph[2][5]=1; graph[3][0]=1;graph[3][2]=1;graph[3][4]=1; graph[4][2]=1;graph[4][3]=1; graph[5][2]=1; graph[5][6]=1; graph[6][5]=1; } public static void BFS(){ while(!queue.isEmpty()){ int i=queue.poll(); System.out.println("出队:"+i); isVisited[i]=true; for(int j=0;j<graph[i].length;j++){ if(graph[i][j]==1&&isVisited[j]==false) { System.out.println("入队："+j); isVisited[j]=true; queue.offer(j); } } } } public static void main(String[] args) { queue.offer(0); BFS(); } }
