«

Java怎么实现图的遍历

时间:2024-8-6 09:04     作者:韩俊     分类: Java


本文小编为大家详细介绍“Java怎么实现图的遍历”,内容详细,步骤清晰,细节处理妥当,希望这篇“Java怎么实现图的遍历”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。

1.图的遍历

从图中某一顶点出发访问图中其余顶点,且每个顶点仅被访问一次

图的遍历有两种深度优先遍历DFS、广度优先遍历BFS

2.深度优先遍历

深度优先遍历以深度为优先进行遍历,简单来说就是每次走到底。类似于二叉树的前序遍历

思路:

1.以某一个顶点为起点进行深度优先遍历,并标记该顶点已访问

2.以该顶点为起点选取任意一条路径一直遍历到底,并标记访问过的顶点

3.第2步遍历到底后回退到上一个顶点,重复第2步

4.遍历所有顶点结束

根据遍历思路可知,这是一个递归的过程,其实DFS与回溯基本相同。

遍历:

以此图为例进行深度优先遍历

   static void dfs(int[][] graph,int idx,boolean[]visit) {
        int len = graph.length;
        //访问过
     if(visit[idx]) return;
     //访问该顶点
     System.out.println("V"+idx);
     //标志顶点
     visit[idx] = true;
     for(int i = 1;i < len;i++) {
     //访问该顶点相连的所有边
         if(graph[idx][i] == 1) {
     //递归进行dfs遍历
         dfs(graph, i, visit);
         }
     }

    }

遍历结果:

V1

V2

V3

V4

V5

V6

V7

V8

V9

创建图的代码:

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //顶点数 以1开始
        int n = scanner.nextInt();
        int[][] graph = new int[n+1][n+1];
        //边数
        int m = scanner.nextInt();

        for(int i = 1;i <= m;i++) {
            int v1 = scanner.nextInt();
            int v2 = scanner.nextInt();
            graph[v1][v2] = 1;
            graph[v2][v1] = 1;
        }

        //标记数组 false表示未访问过 
        boolean[] visit = new boolean[n+1];
        dfs(graph, 1, visit);

    }

3.利用DFS判断有向图是否存在环

思路:遍历某一个顶点时,如果除了上一个顶点之外,还存在其他相连顶点被访问过,则必然存在环

   //默认无环
   static boolean flag = false;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //顶点数 以1开始
        int n = scanner.nextInt();
        int[][] graph = new int[n+1][n+1];
        //边数
        int m = scanner.nextInt();

        for(int i = 1;i <= m;i++) {
            int v1 = scanner.nextInt();
            int v2 = scanner.nextInt();
            graph[v1][v2] = 1;

        }
     //标记数组 true为访问过
        boolean[] visit = new boolean[n+1];
        dfs(graph, 1, visit,1);
        if(flag) 
            System.out.println("有环");

    }

    static void dfs(int[][] graph,int idx,boolean[]visit,int parent) {
        int len = graph.length;

     System.out.println("V"+idx);
     //标记顶点
     visit[idx] = true;
     for(int i = 1;i < len;i++) {
         //访问该顶点相连的所有边
         if(graph[idx][i] == 1) {
         if( !visit[i] ) {
         dfs(graph, i, visit,idx);
         }
         else if(idx != i) {
             flag = true;
         }
         }
     }

     
    }

注意:是有向图判断是否存在环,无向图判断是否存在环无意义,因为任意两个存在路径的顶点都可以是环

4.广度优先遍历

广度优先遍历是以广度(宽度)为优先进行遍历。类似于二叉树的层序遍历

思路:

1.以某一个顶点为起点进行广度优先遍历,并标记该顶点已访问

2.访问所有与该顶点相连且未被访问过的顶点,并标记访问过的顶点

3.以第2步访问所得顶点为起点重复1、2步骤

4.遍历所有顶点结束

通过队列来辅助遍历,队列出队顺序即是广度优先遍历结果

遍历

以此图为例,采用邻接矩阵的方式创建图,进行BFS遍历

  static void bfs(int[][] graph) {        
        int len = graph.length;
        //标记数组 false表示未访问过 
        boolean[] visit = new boolean[len];
        //辅助队列
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(1);
        visit[1] = true;

        while(!queue.isEmpty()) {
            int num = queue.poll();
            System.out.println("V"+num);

            //遍历该顶点所有相连顶点
            for(int i = 1;i < len;i++) {
                //相连并且没有被访问过
                if(graph[num][i] == 1 && !visit[i]) {
                    queue.offer(i);
                    visit[i] = true;              
                }
            }
        }   
    }

遍历结果:

V1

V2

V6

V3

V7

V9

V5

V4

V8

创建图的代码

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //顶点数 以1开始
        int n = scanner.nextInt();
        int[][] graph = new int[n+1][n+1];
        //边数
        int m = scanner.nextInt();

        for(int i = 1;i <= m;i++) {
            int v1 = scanner.nextInt();
            int v2 = scanner.nextInt();
            graph[v1][v2] = 1;
            graph[v2][v1] = 1;
        }
        bfs(graph);
    }

标签: java

热门推荐