图的遍历（Java）

本是古典何须时尚 2024-04-07 15:18 16阅读 0赞

#### 目录 ####

*   *   *  10.1 图的常用概念
         *  10.2 图的表示方式
         *   *  10.2.1 二维数组（邻接矩阵）
             *  10.2.2 链表（邻接表）
         *  10.3 图的创建
         *  10.4 图的深度优先遍历
         *  10.5 图的广度优先遍历
         *  10.6完整代码
         *  本次图 的教程出自韩顺平的数据结构与算法

#### 10.1 图的常用概念 ####

1）顶点（vertex）

2）边（edge）

3）路径

4）无向图

5）有向图

6）带权图

*  无向图  
    ![在这里插入图片描述][1519f49b88994e0da79fa77605022dc2.png]
 *  有向图和带权图  
    ![在这里插入图片描述][36cc5782ff454fe3a92404a6407d7249.png]

#### 10.2 图的表示方式 ####

##### 10.2.1 二维数组（邻接矩阵） #####

**邻接矩阵**

表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是row（行）和col（列）表示1…n个点  
![在这里插入图片描述][9e6396a064834f26b1b949709db955d8.png]

##### 10.2.2 链表（邻接表） #####

**邻接表**

1）邻接表需要为每个顶点都分配n个边的空间，其实有很多边都是不存在，会造成空间上一定损失

2）邻接表的实现只关心存在的边，不关心不存在的边，因此没有空间浪费 邻接表是由：数组+链表组成

![在这里插入图片描述][71a712f8f4b246a08e2fe3a39a49f1d7.png]

#### 10.3 图的创建 ####

**要求**

![在这里插入图片描述][111aae678963415091fdc17fb0d03208.png]

**代码实现**

package com.ldm.graph;
    
    import java.lang.reflect.Array;
    import java.util.ArrayList;
    import java.util.Arrays;
    
    /**
     * @author 梁东明
     * 2022/9/7
     * 人生建议：看不懂的方法或者类记得CTRL + 点击 看看源码或者注解
     * 点击setting在Editor 的File and Code Templates 修改
     */
    public class Graph {
        
        private ArrayList<String> vertexList;  //存储顶点
        private int[][] edges;  //存储图对应的邻接矩阵
        private int numOfEdges;  //表示对应的数目
    
        public static void main(String[] args) {
        
            int n = 5;
    
            String VertexValue[] = {
        "A","B","C","D","E"};
            Graph graph = new Graph(n);
            //循环添加顶点
            for (String str: VertexValue) {
        
                graph.insertVertex(str);
            }
            //添加边
            graph.insertEdge(0,1,1);
            graph.insertEdge(0,2,1);
            graph.insertEdge(1,2,1);
            graph.insertEdge(1,3,1);
            graph.insertEdge(1,4,1);
    
            graph.showGraph();
    
    
        }
        //构造器
    
        public Graph(int n) {
        
            //初始化矩阵和vertexList
            edges = new int[n][n];
            vertexList = new ArrayList<>();
            numOfEdges = 0;
        }
        //返回节点的个数
        public int getNumOfVertex(){
        
            return vertexList.size();
        }
        //得到的边数
        public int getNumOfEdges(){
        
            return numOfEdges;
        }
        //返回结点i对应下标的数据
        public String getValueByIndex(int i){
        
            return vertexList.get(i);
        }
        //返回v1和v2的权值
        public int getWeight(int v1,int v2){
        
            return edges[v1][v2];
        }
        //遍历显示矩阵
        public void showGraph(){
        
            for (int[] link : edges){
        
                System.out.println(Arrays.toString(link));
            }
        }
    
        //插入节点
        public void insertVertex(String vertex){
        
            vertexList.add(vertex);
        }
    
        /**
         * 添加边
         *
         * @param v1     v1 第一个顶点
         * @param v2     v2 第二个顶点
         * @param weight 权值为1 则赋边
         */
        public void insertEdge(int v1, int v2, int weight){
        
            edges[v1][v2] = weight;
            edges[v2][v1] = weight;
            numOfEdges++;
        }
    
    }

#### 10.4 图的深度优先遍历 ####

**图的遍历介绍**

所谓的遍历，即是对节点的访问

**深度优先DFS遍历基本思想**

图的深度优先搜索（Depth First Search）

1）深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略是：首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始节点，访问它的第一邻接结点。可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。

2）我们可以看到，这样的访问策略是优先纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。

3）显然：深度优先搜索是一个递归的过程

**深度优先遍历算法步骤**

1）访问初始结点v，并标记结点v为已访问。

2）查找结点v的第一邻接结点w

3）若w存在，则继续执行4，如果w不存在，则返回第1步，将从v的下一个结点继续

4）若w未被访问，对w进行深度优先遍历递归（即把w当作另外一个v，然后进行步骤123）

5）查找结点v的w邻接结点的下一个邻接结点，转到步骤3  
![在这里插入图片描述][712019c17b2c495fb52f5d1909c10e33.png]

**代码实现**

//得到第一个邻接结点的下标w
        public int getFirstNeighbor(int index){
        
            for (int j = 0; j < vertexList.size(); j++) {
        
                if (edges[index][j] > 0){
        
                    return j;
                }
            }
            return -1;
        }
        //根据前一个邻接结点的下标得到下一个邻接结点的下标
        public int getNextNeighbor(int v1, int v2){
        
            for (int j = v2 + 1; j < vertexList.size(); j++) {
        
                if (edges[v1][j] > 0){
        
                    return j;
                }
            }
            return -1;
        }
    
        /**
         *深度优先遍历
         * @param isVisited ,记录某个结点是否被访问
         * @param i         某个结点的下标
         */
        public void dfs(boolean[] isVisited, int i){
        
            //输出访问的结点
            System.out.print( getValueByIndex(i)+"->");
            //将被访问过的结点置为已访问
            isVisited[i] = true;
            //查找结点i的第一个邻接结点
            int w = getFirstNeighbor(i);
            //如果存在就继续访问
            while (w != -1){
        
                //还需要判断这个结点是否被访问过
                if ( ! isVisited [w] ){
        
                    //没被访问过，那我们就递归,
                    dfs(isVisited,w);
                }
                //如果已经被访问过了，就对w的下一个邻接结点进行查找
                w = getNextNeighbor(i,w);
            }
        }
        //对dfs重载，遍历所有的结点
        public void dfs(){
        
            //遍历所有的结点，进行dfs回溯
            for (int i = 0; i < getNumOfVertex(); i++) {
        
                if (!isVisited[i]){
        
                    dfs(isVisited,i);
                }
            }
        }

#### 10.5 图的广度优先遍历 ####

**广度优先遍历基本思想**

图的广度优先搜索（BroadFirstSearch)

类似于一个分层搜索的过程，广度优先遍历需要使用一个队列保持访问过的结点的顺序。以便按照这个顺序来访问这些结点的邻接结点。

**广度优先遍历算法步骤**

1）访问初始节点并标记v为已访问。

2）结点v进入duilie

3）当队列非空，继续执行，否则算法结束

4）出队列，取得队头结点u

5）查找结点u的第一个邻接结点w。

6）若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤

1、若结点w尚未被访问，则访问结点w并标记已访问

2、结点w入队

3、查找结点u的j继w邻接结点后的下一个邻接结点w，转到步骤6.

//对一个结点进行广度优先遍历
        public void bfs(boolean[] isVisited, int i){
        
            int u;  //队头结点的suoyin
            int w;  //邻接结点w
            //创建队列
            LinkedList queue = new LinkedList<>();
            //访问结点
            System.out.print(getValueByIndex(i)+"=>");
            //标记为已访问
            isVisited[i] = true;
            //将结点接入队列
            queue.addLast(i);
            //如果队头元素不为null，就继续遍历
            while ( !queue.isEmpty()){
        
                //取出队头的结点下标
                u = (Integer) queue.removeFirst();
                //得到u的下一个结点w
                w = getFirstNeighbor(u);
                while ( w != -1){
        
                    //判断是否访问过
                    if (!isVisited[w]){
        
                        //没被访问过就访问
                        System.out.print(getValueByIndex(w)+"=>");
    
                        //标记为已访问
                        isVisited[w] = true;
                        //入队列
                        queue.addLast(w);
                    }
                    w= getNextNeighbor(u,w);
                }
    
            }
        }
        //对bfs重载
        public void bfs(){
        
            isVisited = new boolean[5];
            //遍历所有的结点，进行dfs回溯
            for (int i = 0; i < getNumOfVertex(); i++) {
        
                if (!isVisited[i]){
        
                    bfs(isVisited,i);
                }
            }
        }

#### 10.6完整代码 ####

**代码执行图**  
![在这里插入图片描述][2c6e1dc3611147b6b7e7630bef105562.png]

package com.ldm.graph;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.LinkedList;
    
    /**
     * @author 梁东明
     * 2022/9/7
     * 人生建议：看不懂的方法或者类记得CTRL + 点击 看看源码或者注解
     * 点击setting在Editor 的File and Code Templates 修改
     */
    public class Graph {
        
        private ArrayList<String> vertexList;  //存储顶点
        private int[][] edges;  //存储图对应的邻接矩阵
        private int numOfEdges;  //表示对应的数目
        //定义给数组boolean[],记录某个结点是否被访问
        private boolean[] isVisited;
    
        public static void main(String[] args) {
        
            int n = 5;
    
            String VertexValue[] = {
        "A","B","C","D","E"};
            Graph graph = new Graph(n);
            //循环添加顶点
            for (String str: VertexValue) {
        
                graph.insertVertex(str);
            }
            //添加边
            graph.insertEdge(0,1,1);
            graph.insertEdge(0,2,1);
            graph.insertEdge(1,2,1);
            graph.insertEdge(1,3,1);
            graph.insertEdge(1,4,1);
    
            graph.showGraph();
    
            System.out.println("深度遍历");
            graph.dfs();
            System.out.println();
            System.out.println("广度遍历");
            graph.bfs();
    
    
        }
        //构造器
        public Graph(int n) {
        
            //初始化矩阵和vertexList
            edges = new int[n][n];
            vertexList = new ArrayList<>();
            numOfEdges = 0;
    
        }
        //得到第一个邻接结点的下标w
        public int getFirstNeighbor(int index){
        
            for (int j = 0; j < vertexList.size(); j++) {
        
                if (edges[index][j] > 0){
        
                    return j;
                }
            }
            return -1;
        }
        //根据前一个邻接结点的下标得到下一个邻接结点的下标
        public int getNextNeighbor(int v1, int v2){
        
            for (int j = v2 + 1; j < vertexList.size(); j++) {
        
                if (edges[v1][j] > 0){
        
                    return j;
                }
            }
            return -1;
        }
    
        /**
         *深度优先遍历
         * @param isVisited ,记录某个结点是否被访问
         * @param i         某个结点的下标
         */
        public void dfs(boolean[] isVisited, int i){
        
            //输出访问的结点
            System.out.print( getValueByIndex(i)+"->");
            //将被访问过的结点置为已访问
            isVisited[i] = true;
            //查找结点i的第一个邻接结点
            int w = getFirstNeighbor(i);
            //如果存在就继续访问
            while (w != -1){
        
                //还需要判断这个结点是否被访问过
                if ( ! isVisited [w] ){
        
                    //没被访问过，那我们就递归,
                    dfs(isVisited,w);
                }
                //如果已经被访问过了，就对w的下一个邻接结点进行查找
                w = getNextNeighbor(i,w);
            }
        }
        //对dfs重载，遍历所有的结点
        public void dfs(){
        
            isVisited = new boolean[5];
            //遍历所有的结点，进行dfs回溯
            for (int i = 0; i < getNumOfVertex(); i++) {
        
                if (!isVisited[i]){
        
                    dfs(isVisited,i);
                }
            }
        }
        //对一个结点进行广度优先遍历
        public void bfs(boolean[] isVisited, int i){
        
            int u;  //队头结点的suoyin
            int w;  //邻接结点w
            //创建队列
            LinkedList queue = new LinkedList<>();
            //访问结点
            System.out.print(getValueByIndex(i)+"=>");
            //标记为已访问
            isVisited[i] = true;
            //将结点接入队列
            queue.addLast(i);
            //如果队头元素不为null，就继续遍历
            while ( !queue.isEmpty()){
        
                //取出队头的结点下标
                u = (Integer) queue.removeFirst();
                //得到u的下一个结点w
                w = getFirstNeighbor(u);
                while ( w != -1){
        
                    //判断是否访问过
                    if (!isVisited[w]){
        
                        //没被访问过就访问
                        System.out.print(getValueByIndex(w)+"=>");
    
                        //标记为已访问
                        isVisited[w] = true;
                        //入队列
                        queue.addLast(w);
                    }
                    w= getNextNeighbor(u,w);
                }
    
            }
        }
        //对bfs重载
        public void bfs(){
        
            isVisited = new boolean[5];
            //遍历所有的结点，进行dfs回溯
            for (int i = 0; i < getNumOfVertex(); i++) {
        
                if (!isVisited[i]){
        
                    bfs(isVisited,i);
                }
            }
        }
    
    
    
        //返回节点的个数
        public int getNumOfVertex(){
        
            return vertexList.size();
        }
        //得到的边数
        public int getNumOfEdges(){
        
            return numOfEdges;
        }
        //返回结点i对应下标的数据
        public String getValueByIndex(int i){
        
            return vertexList.get(i);
        }
        //返回v1和v2的权值
        public int getWeight(int v1,int v2){
        
            return edges[v1][v2];
        }
        //遍历显示矩阵
        public void showGraph(){
        
            for (int[] link : edges){
        
                System.out.println(Arrays.toString(link));
            }
        }
    
        //插入节点
        public void insertVertex(String vertex){
        
            vertexList.add(vertex);
        }
    
        /**
         * 添加边
         *
         * @param v1     v1 第一个顶点
         * @param v2     v2 第二个顶点
         * @param weight 权值为1 则赋边
         */
        public void insertEdge(int v1, int v2, int weight){
        
            edges[v1][v2] = weight;
            edges[v2][v1] = weight;
            numOfEdges++;
        }
    
    }

#### 本次图 的教程出自韩顺平的数据结构与算法 ####

[数据结构和算法教程][Link 1]，哔哩哔哩详细教程  
在 146-152p.

最后，认识一下，我是小白。努力成为一名合格的程序员。期待与你的下次相遇。

[1519f49b88994e0da79fa77605022dc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/68895b2b6ffa4d7e9229a81607d02acb.png
[36cc5782ff454fe3a92404a6407d7249.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/6dc12ce6029e408d859d12fc74bc5196.png
[9e6396a064834f26b1b949709db955d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2423018063c249f0a7e0e794d839b07d.png
[71a712f8f4b246a08e2fe3a39a49f1d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/9053b27cb7b0403f9e37dc088186eed3.png
[111aae678963415091fdc17fb0d03208.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/9ddd9915b0de4117b6ec7212453db32d.png
[712019c17b2c495fb52f5d1909c10e33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/d1d60b1cf3064dbfb909f888b4737734.png
[2c6e1dc3611147b6b7e7630bef105562.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/33df595973d14cb3a37c8e9f0c5792b7.png
[Link 1]: https://www.bilibili.com/video/BV1E4411H73v?p=146&vd_source=027fde985896626031abccc06ce8b031