数据结构（11）图的遍历，DFS、BFS的JAVA实现

 

目录

 

11.1.图的遍历

11.2.DFS

11.3.BFS

---

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
            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 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
                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();
    }
}