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

朱雀 2023-09-23 17:32 92阅读 0赞

##  ##

**目录**

11.1.图的遍历

11.2.DFS

11.3.BFS

--------------------

## **11.1.图的遍历** ##

图的遍历，即将图内所有顶点都访问一遍。

有两种遍历方式：

*  BFS
 *  DFS

以下图的遍历为例：

![31a3bd26eacd44f1b7acfa6824cafc79.png][]

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

[31a3bd26eacd44f1b7acfa6824cafc79.png]: https://img-blog.csdnimg.cn/31a3bd26eacd44f1b7acfa6824cafc79.png