离散数学实践三判别图的连通性【JAVA实现】

我会带着你远行 2024-03-30 12:31 63阅读 0赞

#### 文章目录 ####

*  致歉
 *  思路
 *  重要算法&Warshall 算法
 *  错误避坑
 *   *  代码
 *  全部代码
 *  效果展示

## 致歉 ##

*  由于时间仓促，之前最初的蛋的代码内容有一些小问题，现已修改！

## 思路 ##

*  对于给定的邻接矩阵 A，可以用可达矩阵 Warshall 算法求出 A 所表示的图的可达矩阵 P。
    
     *  对于可达矩阵 P 来说，如果 P 的所有元素均为  1 1 1，则所给的有向图是强连通的；
     *  对于 P 的所有元素（除主对角线元素外） P i j P\_\{ij\} Pij 来说，均有： P i j + P i j > 0 P\_\{ij\}+P\_\{ij\}>0 Pij\+Pij>0，则所给有向图是单向连通的。
     *  当所给有向图既不是强连通的，又不是单向连通的时候，我们改造邻接矩阵为：对于矩阵 A 中所有的元素（除主对角线的元素外） a i j a\_\{ij\} aij，若 a i j = 1 a\_\{ij\}=1 aij=1 或 a j i = 1 a\_\{ji\}=1 aji=1，则  a i j = a j i = 1 a\_\{ij\}=a\_\{ji\}=1 aij=aji=1。
     *  对于这样改造之后所得到的新的矩阵  A ′ A' A′（ A ′ A' A′相当于原有向图忽略方向之后所得到的无向图的邻接矩阵），再用方法进行判断，当  P ′ P' P′的所有元素（除主对角线的元素外）均为  1 1 1时，原有向图是弱连通图；
     *  否则，原有向图是不连通的。

## 重要算法&Warshall 算法 ##

![在这里插入图片描述][19aab53836ea463688d4e28eff051342.png]

*  认真看图，认真体会

## 错误避坑 ##

![在这里插入图片描述][862e5d6aeb9a4659910e817078986bfb.png]

### 代码 ###

public static void warshall(int[][] matrix) {
        
        int cols=0,rows=0,i=0;
        for(cols=0;cols<matrix.length;cols++) {
        
            for(rows=0;rows<matrix.length;rows++) {
        
                if(matrix[rows][cols]==1) {
        
                    for(i=0;i<matrix.length;i++) {
        
                        matrix[rows][i]=matrix[rows][i] | matrix[cols][i];
                    }
                }
            }
        }
    }

## 全部代码 ##

package 离散数学;
    
    import java.util.Scanner;
    
    /**
     * @author 缘友一世
     * date 2022/12/30-15:53
     */
    public class demo03 {
        
        public static void main(String[] args) {
        
            int nums=0;
            Scanner scanner = new Scanner(System.in);
            System.out.print("请输入结点的个数：");
            if(scanner.hasNextInt()) {
        
                nums=scanner.nextInt();
            }
            int[][] matrix=new int[nums][nums];
            int[][] matrix2=new int[nums][nums];
            System.out.println("请输入"+nums+"阶矩阵的值[以空格隔开]:");
            for(int i=0;i<matrix.length;i++) {
        
                for(int j=0;j<matrix[i].length;j++) {
        
                    if(scanner.hasNextInt()) {
        
                        matrix2[i][j]=matrix[i][j]= scanner.nextInt();
                    }
                }
            }
            warshall(matrix);
            System.out.println("可达矩阵为:");
            display(matrix);
            int res = estimate(matrix);
            if(res==1) {
        
                System.out.println("该图为强连通图！");
            }else if(res==0) {
        
                System.out.println("该图为单向连通图！");
            }else if(res==-1){
        
                transform(matrix2);
                System.out.println("原邻接矩阵改造后为:");
                display(matrix2);
                warshall(matrix2);
                res=estimate02(matrix2);
                if(res==1) {
        
                    System.out.println("原有向图是弱连通的！");
                }else {
        
                    System.out.println("原有向图是非连通的！");
                }
            }
        }
        public static void warshall(int[][] matrix) {
        
            int cols=0,rows=0,i=0;
            for(cols=0;cols<matrix.length;cols++) {
        
                for(rows=0;rows<matrix.length;rows++) {
        
                    if(matrix[rows][cols]==1) {
        
                        for(i=0;i<matrix.length;i++) {
        
                            matrix[rows][i]=matrix[rows][i] | matrix[cols][i];
                        }
                    }
                }
            }
        }
        public static void display(int[][] matrix) {
        
            for(int i=0;i<matrix.length;i++) {
        
                for(int j=0;j<matrix.length;j++) {
        
                    System.out.print(matrix[i][j]+" ");
                }
                System.out.println();
            }
        }
        public static int estimate(int[][] matrix) {
        
            int flag=1;
            for(int i=0;i<matrix.length;i++) {
        
                for(int j=0;j<matrix.length;j++) {
        
                    if(matrix[i][j]!=1) {
        
                        flag=-1;
                    }
                }
            }
            //标志未改变，所以为强连通图
            if(flag==1) {
        
                return flag;
            }
            flag=0;//标记为单向连通
            for(int i=0;i<matrix.length;i++) {
        
                for(int j=0;j<matrix.length;j++) {
        
                    if(i!=j && !(matrix[i][j]+matrix[j][i]>0)) {
        
                        flag=-1;
                    }
                }
            }
            //单向连通图
            if(flag==0) {
        
                return flag;
            }
            //否则为弱连通
            return flag;
        }
        public static int estimate02(int[][] matrix) {
        
            int flag=1;
            for(int i=0;i<matrix.length;i++) {
        
                for(int j=0;j<matrix.length;j++) {
        
                    if(i!=j && matrix[i][j]!=1) {
        
                        flag=-1;
                        return flag;
                    }
                }
            }
            return flag;
        }
        public static void transform(int[][] matrix) {
        
            for(int i=0;i<matrix.length;i++) {
        
                for(int j=0;j<matrix.length;j++) {
        
                    if(i!=j && (matrix[i][j]==1 || matrix[j][i]==1)){
        
                        matrix[i][j]=matrix[j][i]=1;
                    }
                }
            }
        }
    }

## 效果展示 ##

![在这里插入图片描述][bb7d7565b63343d4b9fa2a7d5889bd37.png]  
![在这里插入图片描述][cdc1a42fe13541a58aaed325ae34fa55.png]  
![在这里插入图片描述][e6e86099d3d14c7992748421c3df5e9c.png]  
![在这里插入图片描述][2376affb7d1c420b9dc8d81fbaeb29ea.png]

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

[19aab53836ea463688d4e28eff051342.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9f5cafbae0a84fad90b38c7fce69f151.png
[862e5d6aeb9a4659910e817078986bfb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3d1592b2eb6f4500bef7746fc6fc9c1b.png
[bb7d7565b63343d4b9fa2a7d5889bd37.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e41569d216614df8b35354d3a8af1ebf.png
[cdc1a42fe13541a58aaed325ae34fa55.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fbd6f8e32b644fdd98629ce74b38ec47.png
[e6e86099d3d14c7992748421c3df5e9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e4225fe7d4244cdab4a5c6062e35fdf1.png
[2376affb7d1c420b9dc8d81fbaeb29ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/aea23ab6e0144f8c84d9e4d3b9c22a59.png
[c37030fc1dfd47b4b1146c421f6651b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/596401b9d7e64c5ab3b663070ad83a8d.png