[Java]图论详解(内附详细代码)

柔光的暖阳◎ 2024-03-31 13:45 65阅读 0赞

![73801d080e2744a4877a24b28fe91767.gif][]

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

> ![c4304daa3a1846adadc000eea43efbf4.png][]专栏简介 :java语法及数据结构
> 
> ![1254c5b119a44cf0ae350489fb7736ad.png][]题目来源:leetcode,牛客,剑指offer.
> 
> ![4366a93aaa3142b5a0f16c7a2200339b.png][]创作目标:记录学习MySql学习历程
> 
> ![52a3437a932f4621b25533c330f7c6cb.png][]希望在提升自己的同时,帮助他人,,与大家一起共同进步,互相成长.
> 
> ![14aa2f0648ae44a299b8f9832af57d2c.png][]学历代表过去,能力代表现在,学习能力代表未来!

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

## 目录 ##

1.图的基本概念

2.图的存储结构

2.1 邻接矩阵

2.2 邻接表

3. 图的遍历

3.1 图的广度优先遍历

3.2 图的深度优先遍历

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

## 前言 ##

> 本文旨在言简意赅的介绍图论基本知识 , 尽量避免冗杂的知识方便大家快速入门 , 进阶算法后续更新.

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

## 1.图的基本概念 ##

图是由顶点集合以及顶点间的关系组成的一种数据结构:G = \{V,E\}.(顶点:vertex , 边:edge)

V是顶点集合 , V = \{x|x属于某个对象集\}.

E是边集 , E = \{(x,y)|x , y 属于V\}或者E = \{<x,y>|x , y 属于V\}.

> Tips: (x,y)表示x,y 之间的双向通路 , 即(x,y)是无方向的.<x,y>表示x,y之间的有向通路 . 即<x,y>是有向的.

*  **完全图**

> 假设有n个顶点 , 对于无向图任意两个顶点之间有且仅有一条边.
> 
>  *  完全无向图有n\*(n-1)/2条边 .(因为每个顶点都重复计算了一次)
> 
> 对于无向图 , 任意两个顶点之间都存在方向相反的两条弧.
> 
>  *  完全有向图有n\*(n-1)条边 .

*  **领接顶点**

> 两个顶点 v1 , v2 之间有边相连 , 则称 v1是v2的领接顶点或v2是v1的领接顶点.

*  **顶点的度**

> 顶点的度指的是它关联边的条数.有向图中顶点的度=入度(指出顶点的边)与出度(指入顶点的边)之和.

*  **简单路径与回路**

> 若路径上 v1,v2...vm均不重复 , 称这样的路径为简单路径. 若路径上第一个顶点 v1与最后一个顶点 vm 重合 , 则称这样的路径为回路或者环.

*  **连通图**

> 在无向图中 , 如果图中任意顶点都是连通的 , 则称此图为连通图.

*  **强连通图**

> 在有向图中，若在每一对顶点 vi 和 vj 之间都存在一条从 vi 到 vj 的路径，也存在一条从 vj 到 vi 的路径，则称此图是强连通图

*  **极小连通子图**

> 既有要保证连通 , 又要保证边数最小.

*  **生成树**

> 一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边

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

## 2.图的存储结构 ##

因为图中既有节点又有边(节点与节点之间的关系) , 因此在图的存储中 , 我们可以使用一段连续的数组来存储**节点** , 但**边**的关系存储较为复杂 , 通常有以下两种方式~~

### 2.1 邻接矩阵 ###

因为节点与节点之间的关系就是是否连通 , 即为0 或 1 , 因此可以使用一个二维数组(领接矩阵)来保存节点与节点之间的关系.

![01871dd86ff44c6a815187d1f969044a.png][]

**Tips:**

>  *  无向图的矩阵是对称的 , 第 i 行(列)元素之和就是顶点 i 的度. 有向图的领接矩阵不一定是对称的 , 第 i 行(列)元素之和就是顶点 i 的出度(入度).
>  *  如果边带权值 , 并且两个顶点之间是连通的 , 上图中的边的关系就用**权值**代替 , 如果两个节点不通 , 则用无穷大代替.
>  *  用领结矩阵存储图的优点是能够快速知道两个节点之间是否连通 , 缺陷是如果顶点较多 , 边较少(领接矩阵较为稀疏) , 矩阵中存储了大量的0 , 比较浪费空间 , 并且要求两个顶点之间的路径不是很好求.
>  *  有向图的领接矩阵表示法中 , 顶点 i 的出度为: **第 i 行非0元素之和**.顶点 i 的入度为: 第 i 列非0元素之和.

**代码实现:**

package Review;
    
    import java.util.Arrays;
    import java.util.HashMap;
    import java.util.HashSet;
    
    public class GraphOfMatrix {
        private char[] arrayV;//节点数组
        private int[][] Matrix;//领接矩阵
        private boolean isDirect;//是否是有向图
        HashMap<Character, Integer> map;//优化版的写法 , 目的是建立节点数组与其下标之间的映射关系
    
        //构造节点数组和领接矩阵 size表示当前节点的个数
        public GraphOfMatrix(int size, boolean isDirect) {
            arrayV = new char[size];
            Matrix = new int[size][size];
            //将领接矩阵的每一位都初始化为无穷大
            for (int i = 0; i < size; i++) {
                Arrays.fill(Matrix[i], Integer.MIN_VALUE);
            }
            this.isDirect = isDirect;
        }
    
        /**
         * 初始化节点数组
         *
         * @param array
         */
        public void initArray(char[] array) {
    
            for (int i = 0; i < array.length; i++) {
                //要么初始化节点数组 , 要么建立映射关系.二选一
                map.put(array[i], i);
    //            arrayV[i] = array[i];
            }
        }
    
        /**
         * 添加边
         *
         * @param src    起始节点
         * @param dest   终止节点
         * @param weight 权值
         */
        public void addEdg(char src, char dest, int weight) {
            //首先要确定起始节点和终止节点在矩阵中的位置
            int srcIndex = getIndexOfV(src);
            int destIndex = getIndexOfV(dest);
            //将节点和节点之间的关系存储在矩阵中
            Matrix[srcIndex][destIndex] = weight;
            //如果是无向图 , 矩阵对称的位置同样需要赋值
            if (!isDirect) {
                Matrix[destIndex][srcIndex] = weight;
            }
        }
    
        /**
         * 获取节点数组的下标
         *
         * @param v
         * @return
         */
        public int getIndexOfV(char v) {
            //同样两种写法二选一
            return map.get(v);
    //        for (int i = 0; i < arrayV.length; i++) {
    //            if (arrayV[i]==v){
    //                return i;
    //            }
    //        }
    //        return -1;
        }
    
        /**
         * 获取顶点的度
         *
         * @param v 有向图 = 入度+出度
         * @return
         */
        public int getDevOfV(char v) {
            int count = 0;
            int srcIndex = getIndexOfV(v);
            for (int i = 0; i < Matrix.length; i++) {
                if (Matrix[srcIndex][i] != Integer.MIN_VALUE) {
                    count++;
                }
            }
            //计算有向图的出度
            if (isDirect) {
                for (int i = 0; i < Matrix[0].length; i++) {
                    if (Matrix[i][srcIndex] != Integer.MIN_VALUE) {
                        count++;
                    }
                }
            }
            return count;
        }
    
        //打印领接表
        public void printGraph() {
            for (int i = 0; i < Matrix.length; i++) {
                for (int j = 0; j < Matrix[0].length; j++) {
                    if (Matrix[i][j] != Integer.MIN_VALUE) {
                        System.out.print(Matrix[i][j] + " ");
                    } else {
                        System.out.print("∞ ");
                    }
                }
                System.out.println();
            }
        }
    
        public static void main(String[] args) {
            char[] chars = {'A', 'B', 'C', 'D',};
            graph.GraphOfMatrix graph = new graph.GraphOfMatrix(chars.length, true);
            graph.initArray(chars);
    
            graph.addEdge('A', 'B', 1);
            graph.addEdge('A', 'D', 1);
            graph.addEdge('B', 'A', 1);
            graph.addEdge('B', 'C', 1);
            graph.addEdge('C', 'B', 1);
            graph.addEdge('C', 'D', 1);
            graph.addEdge('D', 'A', 1);
            graph.addEdge('D', 'C', 1);
    
            graph.printGraph();
            System.out.print("输入节点的度为: ");
            System.out.println(graph.getDevOfV('A'));
            System.out.println("=============");
        }
    
    }

![9d6010df36f54bcfbd09d9c05711950f.png][]

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

### 2.2 邻接表 ###

使用数组表示节点的集合 , 使用链表表示边的关系 , 每个链表的节点中即存放边的关系也存放权重.

**1. 无向图临接表存储**

**A , B , C , D 分别代表 0 , 1 , 2, 3.**

![b4945159be464f8dba9f161657a5b21a.png][]

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

**2. 有向图领接表存储**

![8a6a79184bb54d44bee8636f70d82658.png][]

![a9cbd5e50b1e46fbaa921eb312792ffd.png][]

**Tips:**

>  *  若 G 为无向图 , 则所需的存储空间为 O(V + 2E)
>  *  若 G 为有向图 , 则所需的存储空间为 O(V + E)
>  *  在有向图的领接表表示中 , 求一个给定顶点的出度/入度 , 只需计算领接表中相应节点的个数.

**代码示例:**

package Review;
    
    import java.util.ArrayList;
    
    public class GraphByNode {
        //构造存储边的链表
        static class Node {
            public int src;//起始位置
    
            public int dest;//目标位置
    
            public int weight;//权值
    
            public Node next;
    
            public Node(int src, int dest, int weight) {
                this.src = src;
                this.dest = dest;
                this.weight = weight;
            }
        }
    
        //存储节点的数组
        public char[] arrayV;
        //存在链表的集合
        public ArrayList<Node> edgList;
        //判断是否为有向图
        public boolean isDirect;
    
        //构造领接表
        public GraphByNode(int size, boolean isDirect) {
            arrayV = new char[size];
            edgList = new ArrayList<>(size);
            this.isDirect = isDirect;
        }
    
        /**
         * 初始化顶点数组
         *
         * @param array
         */
        public void initArray(char[] array) {
            for (int i = 0; i < arrayV.length; i++) {
                arrayV[i] = array[i];
            }
        }
    
        /**
         * 添加边
         *
         * @param src    起点
         * @param dest   终点
         * @param weight 权重
         */
        public void addEdge(char src, char dest, int weight) {
            int srcIndex = getIndexOfV(src);
            int destIndex = getIndexOfV(dest);
            addEdgeChild(srcIndex, destIndex, weight);
        }
    
        public void addEdgeChild(int srcIndex, int destIndex, int weight) {
            //获取链表的头结点
            Node cur = edgList.get(srcIndex);
            //遍历整个链表查看之前是否已存在该边
            while (cur != null) {
                if (cur.dest == destIndex) {
                    //之前存过这条边直接返回
                    return;
                }
                cur = cur.next;
            }
            //之前没有存储过这条边 , 头插法插入链表
            Node node = new Node(srcIndex, destIndex, weight);
            node.next = edgList.get(srcIndex);
            edgList.set(srcIndex, node);
        }
    
        /**
         * 获取 顶点下标
         *
         * @param v
         * @return
         */
        public int getIndexOfV(char v) {
            for (int i = 0; i < arrayV.length; i++) {
                if (arrayV[i] == v) {
                    return i;
                }
            }
            return -1;
        }
    
        /**
         * 获取顶点的度
         *
         * @param v
         * @return
         */
        public int getDevOfV(char v) {
            int count = 0;
            int srcIndex = getIndexOfV(v);
            Node cur = edgList.get(srcIndex);
            while (cur != null) {
                count++;
                cur = cur.next;
            }
            //以上仅仅计算了出度 , 还需计算入度
            //遍历除了自身外 , 每一个顶点对应的链表中节点是否有指向srcIndex的.
            if (isDirect) {
                //将srcIndex当做目的下标.
                int destIndex = srcIndex;
                for (int i = 0; i < arrayV.length; i++) {
                    //出去自身
                    if (destIndex == i) {
                        continue;
                    }
                    Node pCur = edgList.get(i);
                    while (pCur != null) {
                        if (pCur.dest == destIndex) {
                            count++;
                        }
                        pCur = pCur.next;
                    }
                }
            }
            return count;
        }
    
        /**
         * 打印领接表
         */
        public void printGraph() {
            for (int i = 0; i < arrayV.length; i++) {
                System.out.println(arrayV[i] + "->");
                Node cur = edgList.get(i);
                while (cur != null) {
                    System.out.println(arrayV[cur.dest] + "->");
                    cur = cur.next;
                }
                System.out.println();
            }
        }
    
        public static void main(String[] args) {
            graph.GraphByNode graph = new graph.GraphByNode(4, false);
            char[] array = {'A', 'B', 'C', 'D',};
            graph.initArray(array);
    
            graph.addEdge('A', 'B', 1);
            graph.addEdge('A', 'D', 1);
            graph.addEdge('B', 'A', 1);
            graph.addEdge('B', 'C', 1);
            graph.addEdge('C', 'B', 1);
            graph.addEdge('C', 'D', 1);
            graph.addEdge('D', 'A', 1);
            graph.addEdge('D', 'C', 1);
    
            graph.printGraph();
            System.out.println(graph.getDevOfV('A'));
            System.out.println("=============");
        }
    }

![ebe1d416a45647f5a5c5b9cd4f71b204.png][]

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

## 3. 图的遍历 ##

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

> 广度优先遍历类似于二叉树的层序遍历 , 由于二叉树的层序遍历借助队列 , 那么图的广度优先遍历也要借助队列. 广度优先遍历每次都访问起始节点相邻的所有节点 , 下图中的访问顺序就是B->A->C->D.

![c4fb08cae13c4dd1925d00a0dbff07ad.png][]

**图示过程:**

![531fd5e8ab0340cc9a07f705250c5b1d.png][]

**Tips:**

> 注意入队和出队都要将visited数组下标置为true , 否则会出现多次打印最后一个元素的情况.

**示例代码:**

/**
         * 广度优先搜索
         * @param v
         */
        public void bfs(char v) {
            //获取起始节点的下标
            int srcIndex = getIndexOfV(v);
            //调用队列
            Queue<Integer> queue = new LinkedList<>();
            //使用visited数组记录节点是否被访问
            boolean[] visited = new boolean[arrayV.length];
            queue.offer(srcIndex);
            while (!queue.isEmpty()) {
                int top = queue.poll();
                visited[top] = true;//每弹出一个元素visited数组相应下标就置为true
                System.out.println(arrayV[top] + "->");
                for (int i = 0; i < arrayV.length; i++) {//搜索领接矩阵中起始节点行的每一个元素
                    if (Matrix[top][i] != Integer.MAX_VALUE && visited[i] != true) {
                        queue.offer(i);
                        visited[i] = true;//每存入一个元素visited数组相应下标就置为true
                    }
                }
            }
        }

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

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

> 图的深度优先优先遍历类似于二叉树的前序遍历 , 需要递归实现.从起始位置一条路走到底 , 再返回寻找下一条路.返回时需要一个visited数组记录元素使用遍历过.

**图示过程:**

![07aba73044864a539f5305e003a6f28a.png][]

**代码示例:**

/**
         * 深度优先遍历
         *
         * @param v 起始元素
         */
        public void dfs(char v) {
            int srcIndex = getIndexOfV(v);
            boolean[] visited = new boolean[arrayV.length];
            dfsChild(srcIndex, visited);
        }
    
        public void dfsChild(int srcIndex, boolean[] visited) {
            System.out.println(arrayV[srcIndex] + "->");
            visited[srcIndex] = true;
            for (int i = 0; i < Matrix[srcIndex].length; i++) {
                if (Matrix[srcIndex][i] != Integer.MAX_VALUE) {
                    dfsChild(i, visited);
                }
            }
        }

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

[73801d080e2744a4877a24b28fe91767.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/45ca54a707e544b5a7c006eb76cdd75f.gif
[c4304daa3a1846adadc000eea43efbf4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/7f5d2077fb3342389b5bc58d8a5fea34.png
[1254c5b119a44cf0ae350489fb7736ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/00e5b97be2f347c08f864f6293e9e815.png
[4366a93aaa3142b5a0f16c7a2200339b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3b64698704a6455d97d40eaf5e6d0082.png
[52a3437a932f4621b25533c330f7c6cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/d3060ae70d164f12b605b45bed392f6b.png
[14aa2f0648ae44a299b8f9832af57d2c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/ca3587d5495c403da31fd5560b42dd40.png
[01871dd86ff44c6a815187d1f969044a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/34268cbccf4c45788f4c7b9a9d6479af.png
[9d6010df36f54bcfbd09d9c05711950f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/7bc24fa654bf4d4a8c2c5e98f756c5af.png
[b4945159be464f8dba9f161657a5b21a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/2939e96f2980457abdd345cf5f4916af.png
[8a6a79184bb54d44bee8636f70d82658.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/0c9c395045e24146896bae9049b3827e.png
[a9cbd5e50b1e46fbaa921eb312792ffd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/dae70da047034052a214131afbc11384.png
[ebe1d416a45647f5a5c5b9cd4f71b204.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/1ab23ec2de7443b89c3e03960c3285e2.png
[c4fb08cae13c4dd1925d00a0dbff07ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/dd10f751db8d4c28a6d3e8665b2ab9b2.png
[531fd5e8ab0340cc9a07f705250c5b1d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/921ec147fdc4441f827885b7e0084076.png
[07aba73044864a539f5305e003a6f28a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/39ffe48d96ae4d1c97109ce70ebaf0d3.png