第26章 图论基础

1、稀疏图判断

算法分析

判断一共有多少个1 ，若i == j的情况是自环情况，需要去掉

时间复杂度

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 110;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int res = 0;
        for(int i = 0;i < n;i ++)
        {
            for(int j = 0;j < n;j ++)
            {
                int x = scan.nextInt();
                if(x == 1 && i != j) res ++;
            }
        }
        if(res <= n * 10) System.out.println("Yes");
        else System.out.println("No");
    }
}

2、图论入门

算法分析

读入以后，判断邻接矩阵 m 那一行有多少非 0 数，这就是 m 的出度，看 m 那一列有多少非 0 数，这就是 m 的入度，看整个矩阵有多少非 0 数，这就是总边数。

时间复杂度

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 1010;
    static int[][] a = new int[N][N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int count = 0;
        for(int i = 1;i <= n;i ++)
        {
            for(int j = 1;j <= n;j ++)
            {
                a[i][j] = scan.nextInt();
                if(a[i][j] > 0) count ++;
            }
        }
        //出度
        int out = 0;
        for(int i = 1;i <= n;i ++)
        {
            if(a[i][m] > 0) out ++;
        }
        //入度
        int in = 0;
        for(int i = 1;i <= n;i ++) 
        {
            if(a[m][i] > 0) in ++;
        }
        System.out.println(m + " " + in + " " + out);
        System.out.println(count);
    }
}

3、朋友的距离

算法分析

读入以后对邻接矩阵的每一位计算它与它对称位置的较大值，并把这一位赋值成这个值。

时间复杂度

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 110;
    static int[][] a = new int[N][N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 1;i <= n;i ++)
        {
            for(int j = 1;j <= n;j ++)
            {
                a[i][j] = scan.nextInt();
            }
        }
        for(int i = 1;i <= n;i ++)
        {
            for(int j = 1;j <= i;j ++)
            {
                if(a[i][j] >= a[j][i]) a[j][i] = a[i][j];
                else a[i][j] = a[j][i];
            }
        }
        for(int i = 1;i <= n;i ++)
        {
            for(int j = 1;j <= n;j ++)
            {
                if(j != n) System.out.print(a[i][j] + " ");
                else System.out.println(a[i][j]);
            }
        }
    }
}