642-图的理论和代码实现

拼搏现实的明天。 2022-09-12 12:46 15阅读 0赞

## 图的理论 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

## 有向图 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
**我们可以把图上的任意一个顶点都可以作为入口。**  
**无限图就是边的没有方向的，只有两个节点相连着，是可以来回的。**

## 图的存储-邻接矩阵 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]

**图的表示方法之一：邻接矩阵**  
![在这里插入图片描述][7d665db8e4c648a5820c08629ec08c44.png]  
**邻接矩阵都是从1开始算的。**  
比如说，从顶点1可以到达顶点5，那么1行5列就是1  
从顶点2可以到达顶点3，那么2行3列就是1  
以此类推  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
**一般用邻接矩阵存储有向图，一般出来的矩阵都是稀疏的矩阵，就是0太多了，有效值1比较少了。所以，邻接矩阵存储有向图是比较浪费空间的，除非顶点之间的边特别多。**

**节点和节点还可以带有权值，就是带权值就有向图。**  
我们可以把节点理解为城市，边理解为城市与城市之间的距离。  
就像我们刚才说的，顶点1可以到达顶点5，1行5列是1，表示这2个顶点之间是有一条有向边的。从1出发，可以到达5。  
**如果是带权值的有向图，顶点1到顶点5是20公里，那么1行5列存储的是20**

![在这里插入图片描述][4c608d2cb02346a5a0a2d3bc043ae0f4.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]

**邻接矩阵的另一个好处是：可以存储顶点的入度和出度**  
**出度**：从这个顶点出发，可以到达几个顶点，比如说1，可以到达2,4，5，所以1顶点的出度就是3  
**就是看，一行一行的，一行有几个1，就代表当前这个顶点的出度是多少**  
![在这里插入图片描述][407e22af741d43f48dc216bdc1f6bb4a.png]  
**顶点1就是在第一行，第一行的2,4，5是1，所以，顶点1的出度是3。以此类推。**

**入度：有几条边可以到达当前的这个顶点**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
**比如说，顶点4，从顶点1可以到达顶点4，从顶点2可以到达顶点4  
所以顶点4的入度是2**  
**我们看的是邻接矩阵的列。顶点4就是看第4列有多少个1，顶点4的入度就是多少。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]

## 图的存储-邻接表 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]  
**左边这列的1,2，3,4，5,6表示有向图的6个顶点  
右边对应的表示：比如说顶点1，顶点1可以到达顶点2，顶点4，顶点5**  
**顶点2可以到达顶点3和顶点4**  
**顶点3是没有出度的，以此类推**

**相比较于邻接矩阵**，邻接表不用存储那么多无效的0值，内存空间的利用率是比较高的，但是邻接表的不好地方是只描述了顶点的出度，没有描述顶点的入度。

**逆邻接表**：存储顶点的入度，但是不存储顶点的出度

**有没有一种数据结构，可以既存储顶点的入度，又可以存储顶点的出度？**  
十字链表

## 图的遍历 ##

**我们看成图或者三叉树都可以**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]  
**图的深度优先遍历：**  
从A开始，一直向左遍历，直到为空，  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]  
然后回退到E，E没有右孩子，回退到B，B有右孩子，访问B的右孩子F，F-H，H后为空，然后回退到F，回退到B，回退到A，A下面有C，C下面没有，回退到C，回退到A，访问D，访问G  
![在这里插入图片描述][4bc314e18b634c6a89161017ec96a528.png]  
**广度优先遍历：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]  
**相当于二叉树的层序遍历。**  
一层一层的来，层层向外扩张  
![在这里插入图片描述][576a3822d7f6479987b0fa0fac91abdc.png]  
**我们再举一个例子：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]  
**从A开始进行深度优先遍历：**  
假设A先到达B，  
A-B-F-I-H  
H不能到达其他顶点了，回溯。  
回溯到I，I也没有其他的路径，回溯到F，F可以访问G  
F-G  
然后G再进行深度，可以到B，但是B访问过了，所以就到C  
G-C  
C-D  
D可以到C，但是C遍历过了，D可以到H，但是H遍历过了，所以D回溯  
回溯到C，回溯到G，回溯到F，回溯到B，回溯到A，然后A可以访问E，  
D-E  
![在这里插入图片描述][acbc7e5a051c4122baa95755ed3d696c.png]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]  
**从A开始广度优先遍历：**  
先访问A所有相邻的顶点，A-B-D-E  
然后看B这个顶点，跟B相邻的有：F  
![在这里插入图片描述][5fbf6d0598cc4d839b360ff109bc3ad7.png]  
然后看D这个顶点，跟D相邻的有：C-H  
![在这里插入图片描述][c15ea595a0d244ceb055a78c14caf0ff.png]  
然后看E这个顶点，跟E相邻的有：H，但是H被访问过了  
然后处理F这个顶点，跟F相邻的有：G-I  
![在这里插入图片描述][eef54f0f31294e1fbe7c78332d6c4a0e.png]  
然后处理C这个顶点：跟C相邻的有：B之前访问过了，D之前访问过了，  
然后处理H这个顶点，跟H相邻的有：没有  
然后处理G这个顶点，跟G相邻的有：C之前访问过了，B之前访问过了  
然后处理I这个顶点，跟I相邻的有：H之前访问过了  
**广度优先遍历结束**  
![在这里插入图片描述][d09453afe55543589cc3e9850fc8f3a9.png]

## 有向图创建邻接表的代码 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]  
**西安（3,5）表示西安可以到达安徽和福建**  
**这样的有向图相当于是不带权值的。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 13]  
**左边这一列相当于是数组，数组里面的节点类型：地址域和数据域（城市的编号）**

/**
     * 实现不带权值的有向图，用邻接表组织
     */
    public class Digraph
    {
        
        private ArrayList<Vertic> adj;//邻接表结构，向量数组 
    
        /**
         * 邻接表初始化
         */
        public Digraph() {
        //构造函数 
            this.adj = new ArrayList<>();
        }
    
        /**
         * 从文件中读取城市定点和边的信息
         * @param reader
         */
        public void read(BufferedReader reader) throws Exception{
        
    
            //把adj的第0号位置占用，让顶点编号和adj数组的位置一一对应
            adj.add(new Vertic("", null));
    
            String city = null;
            String[] vertic = null;
            for(;;){
        
                city = reader.readLine();//读一行城市信息 
                if(city == null){
        //没找到 
                    break;
                }
                //读边，读一行，出度，用逗号隔开的 
                LinkedList<Integer> list = new LinkedList<>();
                vertic = reader.readLine().split(",");//，隔开 
                for (int i = 0; i < vertic.length; i++) {
        
                    list.add(Integer.parseInt(vertic[i].trim()));//字符串的前后空格去掉 
                }
    
                adj.add(new Vertic(city, list));
            }
        }
    
        /**
         * 打印有向图的邻接表结构
         */
        public void showAdj(){
        
            for(int i=1; i < adj.size(); ++i){
        
                System.out.print(adj.get(i).data + " : ");
                for (Integer integer : adj.get(i).adjList) {
        
                    System.out.print(integer + " ");
                }
                System.out.println();
            }
        }
        
        /**
         * 定义有向图的定点类型
        */
        static class Vertic{
        
    
            public Vertic(String data, LinkedList<Integer> adjList) {
        
                this.data = data;
                this.adjList = adjList;
            }
    
            String data;//表示邻接表数组的数据(城市名称)
            LinkedList<Integer> adjList;//描述定点出度的链表结构
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 14]

## 深度优先和广度优先遍历邻接表的代码 ##

/**
     * 从指定的start顶点开始，深度遍历有向图
     * @param start
     */
    public void dfs(int start) {
        
        System.out.println("深度优先遍历:");
        boolean[] visited = new boolean[adj.size()];//判断顶点是否已经被遍历过了
        dfs(start, visited);
    }
    
    private void dfs(int start, boolean[] visited) {
        
        //表示当前顶点已经被访问过
        if (visited[start]) {
        
            return;
        }
    
        //访问当前顶点
        System.out.print(adj.get(start).data + " ");
        visited[start] = true;//已经访问过了
    
        //深度遍历，访问其它顶点信息
        for (int i = 0; i < adj.get(start).adjList.size(); ++i) {
        //访问当前顶点的后面的链表的第一个节点
            dfs(adj.get(start).adjList.get(i), visited);
        }
    }
    
    /**
     * 从指定的start顶点开始，进行广度优先遍历
     * @param start
     */
    public void bfs(int start) {
        
        System.out.println("广度优先遍历:");
        boolean[] visited = new boolean[adj.size()];
        LinkedList<Vertic> queue = new LinkedList<>();
    
        //把入口顶点信息入队列
        queue.offer(adj.get(start));
        visited[start] = true;
    
        while (!queue.isEmpty()) {
        
            Vertic front = queue.poll();//取出队头元素
            System.out.print(front.data + " ");
    
            LinkedList<Integer> list = front.adjList;
            for (int i = 0; i < list.size(); i++) {
        
                //表示front.adjList.get(i)顶点没有被访问过
                if (!visited[list.get(i)]) {
        
                    queue.offer(adj.get(list.get(i)));//入队
                    visited[list.get(i)] = true;//访问过了
                }
            }
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 15]

## 不带权值有向图最短路径代码 ##

/**
     * 找start到end的最短路径信息
     * @param start
     * @param end
     */
    public void shortestPath(int start, int end) {
        
        int[] path = new int[adj.size()];//定义和节点一样多的数组，记录路径
        boolean[] visited = new boolean[adj.size()];//是否已经访问过了
        LinkedList<Integer> queue = new LinkedList<>();//队列
        boolean flag = false;
    
        //把入口顶点信息入队列
        queue.offer(start);
        visited[start] = true;//现在访问过了！
    
        while (!queue.isEmpty()) {
        
            int front = queue.poll();//出队
            if (front == end) {
        
                flag = true;
                break;
            }
    
            LinkedList<Integer> list = adj.get(front).adjList;//拿到顶点的链表信息
            for (int i = 0; i < list.size(); i++) {
        
                //表示front.adjList.get(i)顶点没有被访问过
                if (!visited[list.get(i)]) {
        
                    queue.offer(list.get(i));//放编号
                    //记录当前顶点的前驱顶点信息
                    path[list.get(i)] = front;
                    visited[list.get(i)] = true;//可以通行
                }
            }
        }
    
        if (!flag) {
        
            System.out.println(adj.get(start).data + " => "
                + adj.get(end).data + " 不存在路径!");
            return;
        }
    
        printShortestPath(start, end, path);
    }
    
    /**
     * 打印start到end的最短的路径信息
     * @param start
     * @param end
     * @param path
     */
    private void printShortestPath(int start, int end, int[] path) {
        
        if (start == end) {
        
            System.out.print(adj.get(end).data + " -> ");
            return;
        }
    
        printShortestPath(start, path[end], path);//先递归，后打印
        System.out.print(adj.get(end).data + " -> ");
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/449981b752e045438fba5a2caee6f384.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/58464f663b564958a3bb0038e1581ec0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/b5104cd310b04f648abad1208fb5b21a.png
[7d665db8e4c648a5820c08629ec08c44.png]: /images/20220828/9615d0925e474a6380984ab91f4876a5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/e30fb10c7d3f4fdcb52c905a53d21326.png
[4c608d2cb02346a5a0a2d3bc043ae0f4.png]: /images/20220828/d799dc49e9344494a04144101828a973.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/d419ed8b3f4e4c959749398ebd228c60.png
[407e22af741d43f48dc216bdc1f6bb4a.png]: /images/20220828/e530eb360ba94f2da12ee9c3bc9a0630.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/8700bfc9a52f427994361c0532ad621e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/ec9948d106d9462d9d0e365055c6b55a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/c45739256f0d4cb080a5b8f543f00c81.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/deb538e84e5e4180b7a7eb05de9123c3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/70e3e3407a1844a99a07166ba97ec990.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/6d1ca2b75c984d0f99eb5c902c38cec5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/9d24729f95e445fd8ae16f6360435d44.png
[4bc314e18b634c6a89161017ec96a528.png]: /images/20220828/1ff8f48e70c94b9caad97b0389bcdf17.png
[576a3822d7f6479987b0fa0fac91abdc.png]: /images/20220828/bca4df56ae0942c9bea9db29f1de0258.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220828/856f197ec9374d7897462e25c724a26d.png
[acbc7e5a051c4122baa95755ed3d696c.png]: /images/20220828/931675c2380c43939fad84cc90cc7f20.png
[5fbf6d0598cc4d839b360ff109bc3ad7.png]: /images/20220828/1604026d5c1541a0bba41fcf3bb340a1.png
[c15ea595a0d244ceb055a78c14caf0ff.png]: /images/20220828/8775947752fa4bbfaed8bcc19365b644.png
[eef54f0f31294e1fbe7c78332d6c4a0e.png]: /images/20220828/9bd1de9837f2469994361884c251046e.png
[d09453afe55543589cc3e9850fc8f3a9.png]: /images/20220828/15e5da251dd246f29c7910c7fa66abd8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/8d8b761db0eb461ea48c4dfcd0eb2a12.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 13]: /images/20220828/f2855b816cef4b6d8494bae173412318.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 14]: /images/20220828/983b09724d3e4dd1bc34e499fe1534ee.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 15]: /images/20220828/437e399d8a7e4649be54bed4282065b1.png