Carson带你学数据结构：手把手带你了解 ”图“ 所有知识！(含DFS、BFS）

悠悠 2022-12-06 15:16 241阅读 0赞

![e42c52b9af8d79486a0f3cd0e50df7b7.png][]

# 前言 #

本文主要讲解 数据结构中的图 结构，包括 深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树算法等，希望你们会喜欢。

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

# 目录 #

![示意图][1fe7770e3ec479aea5d0e0df08b724c5.png]

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

# 1. 简介 #

*  数据结构的中属于 **圆形结构** 的逻辑结构
 *  具体介绍如下

![示意图][cf9a0fb348316d07f65623dbdea0e2e2.png]

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

# 2. 基础概念 #

*  在图的数据结构中，有许多基础概念，如 边类型、图顶点 & 边间的关系等等
 *  具体请看下图

![示意图][1be840903055a2d99655729557e89330.png]

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

# 3. 类型 #

图的类型分为很多种，具体如下：

### 3.1 有向图 & 无向图 ###

![示意图][a6addc3b4437bcd7847e60856fdb555e.png]

### 3.2 连通图 ###

*  定义  
    图中任意顶点都是连通的图
 *  具体相关概念  
    对于有向图 & 无向图，连通图的的具体概念又不同，具体如下

对于无向图：

![示意图][0a173dfc47179e38b3a652275ea69b8d.png]

对于有向图：

![示意图][dff8325a54963bd3d82db23e9f0ca21c.png]

### 3.3 其余类型图 ###

![示意图][6a2a5cc7aa20b3fac99c18a19a05a8e7.png]

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

# 4. 存储结构 #

图的存储结构共有5种，具体请看下图

![示意图][5c339a1e9c8d6081fafc7bd2383cde98.png]

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

# 5. 图的遍历 #

[数据结构：图文详解二叉树（遍历、类型、操作）][Link 1]

### 5.1 定义 ###

从图中某1顶点出发，遍历图中其余所有顶点 & 使每1个顶点仅被访问1次

### 5.2 遍历方式 ###

深度优先遍历（`DFS`）、广度优先遍历（`BFS`）

### 5.3 具体介绍 ###

##### 5.3.1 深度优先遍历（ DFS ） #####

*  简介

![示意图][5a28db50ba894f683b57fbb453638b54.png]

*  算法示意图

![示意图][ff26f611a5cf39d8e69f8dacc0fea3c8.png]

*  具体实现：递归 & 非递归

> 此处图的存储结构 = 邻接矩阵

import java.util.Stack;
    
    public class MyGraph {
    
        /**
         * 准备工作1：设置变量
         */
        private int vexnum;  // 存放图中顶点数量
        private char[] vertices;  // 存放结点数据
        private int [][] arcs;  // 存放图的所有边
        private boolean[] visited;// 记录节点是否已被遍历
    
        /**
         * 准备工作2：初始化图的顶点数量、数据 & 边
         */
        public MyGraph(int n){
            vexnum = n;
            vertices = new char[n];
            visited = new boolean[n];
            arcs = new int[n][n];
        }
    
        /**
         * 图的深度优先遍历算法实现：递归
         * 类似 前序遍历
         */
        public void DFSTraverse(){
            // 1. 初始化所有顶点的访问标记
            // 即，都是未访问状态
            for (int i = 0; i < vexnum; i++) {
                visited[i] = false;
            }
    
            // 2. 深度优先遍历顶点（从未被访问的顶点开始）
            for(int i=0;i < vexnum;i++){
    
                if(visited[i]==false){
    
                    // 若是连通图，只会执行一次
                    traverse(i); // ->>看关注1
                }
            }
        }
    
        /**
         * 关注1：邻接矩阵的深度优先搜索递归算法
         * 即，从第i个顶点开始深度优先遍历
         */
        private void traverse(int i){
    
            // 1. 标记第i个顶点已遍历
            visited[i] = true;
    
            // 2. （输出）访问当前遍历的顶点
            visit(i);
    
            // 3. 遍历邻接矩阵中第i个顶点的所有邻接顶点
            for(int j=0;j<vexnum;j++){
    
                // a. 若当前顶点的邻接顶点存在 & 未被访问，则递归 深度优先搜索 算法
    
                if(arcs[i][j]==1 && visited[j]==false){
                    // b. 将当前顶点的邻接顶点作为当前顶点，递归 深度优先搜索 算法
                    traverse(j);
                }
            }
        }
        
        /**
         * 辅助算法1：访问顶点值
         */
        public void visit(int i){
            System.out.print(vertices[i] + " ");
        }
    
        
        
        /**
         * 图的深度优先遍历算法实现：非递归
         * 原理：采用 栈实现
         */
        public void DFSTraverse2(){
            // 1. 初始化顶点访问标记
            // 全部标记为：未访问
            for (int i = 0; i < vexnum; i++) {
                visited[i] = false;
            }
    
            // 2. 创建栈
            Stack<Integer> s = new Stack<Integer>();
    
    
            for(int i=0 ; i<vexnum; i++){
    
                // 3. 若该顶点未被访问
                if(!visited[i]){
                    // 4. 入栈该顶点
    
                    s.add(i);
    
                    do{
                        // 出栈
                        int curr = s.pop();
    
                        // 如果该节点还没有被遍历，则遍历该节点并将子节点入栈
                        if(visited[curr]==false){
                            // 遍历并打印
                            visit(curr);
                            visited[curr] = true;
    
                            // 没遍历的子节点入栈
                            for(int j=vexnum-1; j>=0 ; j-- ){
                                if(arcs[curr][j]==1 && visited[j]==false){
                                    s.add(j);
                                }
                            }
                        }
                    }while(!s.isEmpty());
                }
            }
        }
    
        
        /**
         * 测试（递归 & 非递归）
         */
        public static void main(String[] args) {
    
            // 1. 初始化图的结构（顶点数量 = 9）
            MyGraph g = new MyGraph(9);
    
            // 2. 设置顶点数据
            char[] vertices = {'A','B','C','D','E','F','G','H','I'};
            g.setVertices(vertices);
    
            // 3. 设置边
            g.addEdge(0, 1);
            g.addEdge(0, 5);
            g.addEdge(1, 0);
            g.addEdge(1, 2);
            g.addEdge(1, 6);
            g.addEdge(1, 8);
            g.addEdge(2, 1);
            g.addEdge(2, 3);
            g.addEdge(2, 8);
            g.addEdge(3, 2);
            g.addEdge(3, 4);
            g.addEdge(3, 6);
            g.addEdge(3, 7);
            g.addEdge(3, 8);
            g.addEdge(4, 3);
            g.addEdge(4, 5);
            g.addEdge(4, 7);
            g.addEdge(5, 0);
            g.addEdge(5, 4);
            g.addEdge(5, 6);
            g.addEdge(6, 1);
            g.addEdge(6, 3);
            g.addEdge(6, 5);
            g.addEdge(6, 7);
            g.addEdge(7, 3);
            g.addEdge(7, 4);
            g.addEdge(7, 6);
            g.addEdge(8, 1);
            g.addEdge(8, 2);
            g.addEdge(8, 3);
    
            // 4. 执行 图的深度优先遍历：（递归 & 非递归）
            System.out.println("深度优先遍历（递归）");
            g.DFSTraverse();
            System.out.println("深度优先遍历（非递归）");
            g.DFSTraverse2();
    
        }
    
        /**
         * 辅助算法1：添加边(无向图)
         */
        public void addEdge(int i, int j) {
            // 边的头尾不能为同一节点
            if (i == j) return;
    
            // 将邻接矩阵的第i行第j列的元素值置为1；
            arcs[i][j] = 1;
            // 将邻接矩阵的第j行第i列的元素值置为1；
            arcs[j][i] = 1;
            // 设置为1代表2顶点之间存在 边 （设置相等原因 = 邻接矩阵 是对称的）
        }
    
        /**
         * 辅助算法2：设置顶点数据
         */
        public void setVertices(char[] vertices) {
            this.vertices = vertices;
        }
    }

*  测试结果

深度优先遍历（递归）
    A B C D E F G H I 
    深度优先遍历（非递归）
    A B C D E F G H I

*  特别注意  
    对于图的存储结构 = **邻接表**实现，只需要**将 存储边 的2维数组 改成链表即可。**
 *  图的存储结构 = 邻接矩阵 / 邻接表 的性能对比

![示意图][584756cf62d957b94e137b7f7a3e3bec.png]

##### 5.3.2 广度优先遍历（BFS） #####

*  简介

![示意图][f4663632aa27e2975b0778dfcd3274d5.png]

*  算法示意图

![示意图][7d6036f779ec2ce70129ac223565523e.png]

*  具体流程

![示意图][82f4e90c524c36a249ddf94de422eaf8.png]

> 注：`G` 比 `I` 先访问的原因 = 用数组存储顶点时，`G`的下标 比 `I`的下标小（按`ABCDEFGHI`顺序存储）

*  具体实现

> 非递归：采用队列

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    public class MyGraph {
    
        /**
         * 准备工作1：设置变量
         */
        private int vexnum;  // 存放图中顶点数量
        private char[] vertices;  // 存放结点数据
        private int [][] arcs;  // 存放图的所有边
        private boolean[] visited;// 记录节点是否已被遍历
    
        /**
         * 准备工作2：初始化图的顶点数量、数据 & 边
         */
        public MyGraph(int n){
            vexnum = n;
            vertices = new char[n];
            visited = new boolean[n];
            arcs = new int[n][n];
        }
        
        /**
         * 广度优先搜索 算法实现
         * 原理：非递归（采用队列）
         */
        public void BFS(){
    
            // 1. 初始化所有顶点的访问标记
            // 即，设置为未访问状态
            for (int i = 0; i < vexnum; i++) {
                visited[i] = false;
            }
    
            // 2. 创建队列
            Queue<Integer> q=new LinkedList<Integer>();
    
            // 3. 对所有顶点做遍历循环（从第1个顶点开始）
            // 若遍历完毕，则结束整个层序遍历
            for(int i=0;i < vexnum;i++){
    
                // 4. 若当前顶点未被访问，就进行处理
                // 若当前顶点已被访问，则回到3进行判断
                if( visited[i]==false ) {
    
                    // 5. （输出）访问当前顶点
                    visit(i);
    
                    // 6. 标记当前顶点已被访问
                    visited[i] = true;
    
                    // 7. 入队当前顶点
                    q.add(i);
    
                    // 8.判断当前队列是否为空
                    // 若为空则跳出循环，回到3进行判断
                    while(!q.isEmpty()) {
    
                        // 9. 出队队首元素 & 将出队的元素 赋值为 当前顶点
                        i =  q.poll();
    
                        // 10. 遍历当前顶点的所有邻接点
                        // 若遍历完毕，则回到8判断
                        for(int j=0; j< vexnum ; j++){
    
                            // 11. 若当前顶点的邻接顶点存在 & 未被访问，则执行处理
                            // 否则回到10判断
                            if(arcs[i][j]==1 && visited[j]==false){
    
                                // 12. （输出）访问当前顶点的邻接顶点
                                visit(j);
    
                                // 13. 标记当前顶点的邻接顶点已被访问
                                visited[j] = true;
    
                                // 14. 入队当前顶点的邻接顶点
                                q.add(j);
    
                            }
                        }
    
                    }
    
                }
            }
        }
    
      /**
        * 辅助算法1：访问该顶点
        */
        public void visit(int i){
            System.out.print(vertices[i] + " ");
        }
    
      /** 
        * 测试算法
        */
        public static void main(String[] args) {
            // 1. 初始化图的结构（顶点数量 = 9
            MyGraph g = new MyGraph(9);
    
            // 2. 设置顶点数据
            char[] vertices = {'A','B','C','D','E','F','G','H','I'};
            g.setVertices(vertices);
    
            // 3. 设置边
            g.addEdge(0, 1);
            g.addEdge(0, 5);
            g.addEdge(1, 0);
            g.addEdge(1, 2);
            g.addEdge(1, 6);
            g.addEdge(1, 8);
            g.addEdge(2, 1);
            g.addEdge(2, 3);
            g.addEdge(2, 8);
            g.addEdge(3, 2);
            g.addEdge(3, 4);
            g.addEdge(3, 6);
            g.addEdge(3, 7);
            g.addEdge(3, 8);
            g.addEdge(4, 3);
            g.addEdge(4, 5);
            g.addEdge(4, 7);
            g.addEdge(5, 0);
            g.addEdge(5, 4);
            g.addEdge(5, 6);
            g.addEdge(6, 1);
            g.addEdge(6, 3);
            g.addEdge(6, 5);
            g.addEdge(6, 7);
            g.addEdge(7, 3);
            g.addEdge(7, 4);
            g.addEdge(7, 6);
            g.addEdge(8, 1);
            g.addEdge(8, 2);
            g.addEdge(8, 3);
    
            // 4. 执行 图的广度优先遍历（非递归）
            System.out.print("广度优先遍历（非递归）：");
            g.BFS();
            }
    
      /**
        * 辅助算法1：添加边(无向图)
        */
    
        public void addEdge(int i, int j) {
            // 边的头尾不能为同一节点
            if (i == j) return;
    
            // 将邻接矩阵的第i行第j列的元素值置为1；
            arcs[i][j] = 1;
            // 将邻接矩阵的第j行第i列的元素值置为1；
            arcs[j][i] = 1;
            // 设置为1代表2顶点之间存在 边 （设置相等原因 = 邻接矩阵 是对称的）
        }
    
        /**
         * 辅助算法2：设置顶点数据
         */
        public void setVertices(char[] vertices) {
            this.vertices = vertices;
        }
            
    }

*  执行结果

广度优先遍历（非递归）：A B F C G I E D H

### 5.4 遍历方式对比 ###

![示意图][4a37c249499c7ac4e7c0f1b592d46f72.png]

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

# 6. 最小生成树 #

本节主要讲解 图中的 **最小生成树**

### 6.1 定义 ###

构造 连通网图 的最小成本生成树

> 1.  网图：带有权值的图
> 2.  最小成本：用（n-1）条边将 含n个顶点的连通图 连接起来 & 使得权值和最小

### 6.2 寻找最小生成树的算法 ###

*  主要包括：（`Prim`）普利姆算法 & （`Kruskal`）克鲁斯卡尔算法
 *  具体介绍如下

#### 6.2.1 （Prim）普利姆算法 ####

*  算法概述

![示意图][5391f6039af12173a5cdb8632e083121.png]

*  算法原理流程示意图

![示意图][99cfe01a304e4c9de5edd4d4ad61ca9c.png]

*  举例说明

![示意图][e64fc1b42cb902099bb6b659211270bc.png]

#### 6.2.2（Kruskal）克鲁斯卡尔算法 ####

*  算法概述

![示意图][665e75347318bf0f44cc33e235a3143b.png]

### 6.3 算法对比 ###

![示意图][1437ec3b514fc02ed34ec64f504ce133.png]

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

# 7. 最短路径 #

### 7.1 定义 ###

*  对于非网图（无权值），最短路径 = 两顶点间经过的边数最少的路径
 *  对于网图（有权值）：最短路径 = 两顶点间经过的边上权值和最少的路径

> 第1个顶点 = 源点、第2个顶点 = 终点

### 7.2 需解决的问题 ###

从源点 -> 其余各顶点的最短路径

### 7.3 寻找最短路径 算法 ###

*  主要包括：迪杰斯特拉算法`（Dijkstra）`、弗洛伊德算法`（Floyd）`
 *  具体介绍如下

![示意图][d19e340ceab09a8e21fa30c37bc3c8d9.png]

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

# 8. 总结 #

*  本文主要讲解了数据结构中的图
 *  下面我将继续对 **数据结构**，有兴趣可以继续关注[Carson\_Ho的安卓开发笔记][Carson_Ho]

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

# 帮顶 / 评论点赞！因为你的鼓励是我写作的最大动力！ #

[e42c52b9af8d79486a0f3cd0e50df7b7.png]: /images/20221123/0a13edde55ba471593fc4375de0ec24f.png
[1fe7770e3ec479aea5d0e0df08b724c5.png]: /images/20221123/e78fe95791ec419e8c08c6b043614918.png
[cf9a0fb348316d07f65623dbdea0e2e2.png]: /images/20221123/23861bc1f55f450fb77e44c456b32d30.png
[1be840903055a2d99655729557e89330.png]: /images/20221123/358955171b334f61addcf9421d1b1490.png
[a6addc3b4437bcd7847e60856fdb555e.png]: /images/20221123/a197f1fd0af54b71bd0b049388c67e7a.png
[0a173dfc47179e38b3a652275ea69b8d.png]: /images/20221123/afec635b557a47b8a6722713a62e4ae0.png
[dff8325a54963bd3d82db23e9f0ca21c.png]: /images/20221123/86cbada533604def9b46967ab2cac93b.png
[6a2a5cc7aa20b3fac99c18a19a05a8e7.png]: /images/20221123/de52d91d634e4120b67fd976e4f56c27.png
[5c339a1e9c8d6081fafc7bd2383cde98.png]: /images/20221123/566d8e85b77e483cb2f358682db916ca.png
[Link 1]: https://blog.csdn.net/carson_ho/article/details/103676620
[5a28db50ba894f683b57fbb453638b54.png]: /images/20221123/234b1f630f9d45879c214dda8ed86068.png
[ff26f611a5cf39d8e69f8dacc0fea3c8.png]: /images/20221123/4f27041a3cdf463c80eb65bfbfd7e45a.png
[584756cf62d957b94e137b7f7a3e3bec.png]: /images/20221123/8aca64a45f234a1b80cbbd42e0b42b5f.png
[f4663632aa27e2975b0778dfcd3274d5.png]: /images/20221123/8cd265122c4247338a32cb3c73602649.png
[7d6036f779ec2ce70129ac223565523e.png]: /images/20221123/9394cda4d29445bcaf9f3bf5d28ecb4c.png
[82f4e90c524c36a249ddf94de422eaf8.png]: /images/20221123/50056249c78448ddb2ca4a53fcf9f29a.png
[4a37c249499c7ac4e7c0f1b592d46f72.png]: /images/20221123/d4dc3e1a0b204aae9b4eef564c90824e.png
[5391f6039af12173a5cdb8632e083121.png]: /images/20221123/2a382ffcd49e4a9cac581bf708637862.png
[99cfe01a304e4c9de5edd4d4ad61ca9c.png]: /images/20221123/f277e36d095f47c5a82055858b4b6fdc.png
[e64fc1b42cb902099bb6b659211270bc.png]: /images/20221123/d848c27e7f1b4d968018a023ed563bf7.png
[665e75347318bf0f44cc33e235a3143b.png]: /images/20221123/448ec4905c4b401482e29cc18be9dbf8.png
[1437ec3b514fc02ed34ec64f504ce133.png]: /images/20221123/ca79e4a4c98345548bd634b5fc12b457.png
[d19e340ceab09a8e21fa30c37bc3c8d9.png]: /images/20221123/114a72f67846418fb0a41969fa5d7cf8.png
[Carson_Ho]: https://blog.csdn.net/carson_ho/article/list/1