图论

图的基本概念

二维坐标中，两点可以连成线，多个点连成的线就构成了图。

当然图也可以就一个节点，甚至没有节点（空图）

图的种类

整体上一般分为有向图和无向图。

加权有向图，就是图中边是有权值的，加权无向图也是同理

度

无向图中有几条边连接该节点，该节点就有几度。在有向图中，每个节点有出度和入度。出度：从该节点出发的边的个数。入度：指向该节点边的个数。

连通性

在图中表示节点的连通情况，我们称之为连通性。

连通图

在无向图中，任何两个节点都是可以到达的，我们称之为连通图，如果有节点不能到达其他节点，则为非连通图

强连通图

在有向图中，任何两个节点是可以相互到达的，我们称之为强连通图。强连通图是在有向图中任何两个节点是可以相互到达

连通分量

在无向图中的极大连通子图称之为该图的一个连通分量。

强连通分量

在有向图中极大强连通子图称之为该图的强连通分量。

图的构造

一般使用邻接表、邻接矩阵或者用类来表示。主要是朴素存储、邻接表和邻接矩阵。

邻接矩阵

邻接矩阵使用二维数组来表示图结构。邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。

例如： grid[2]][5] = 6，表示节点 2 连接节点5 为有向图，节点2 指向节点5，边的权值为6。如果想表示无向图，即：grid[2][5] = 6，grid[5][2] = 6，表示节点2 与节点5 相互连通，权值为6。

在一个 n （节点数）为8 的图中，就需要申请 8 * 8 这么大的空间。

邻接矩阵的优点：

表达方式简单，易于理解
检查任意两个顶点间是否存在边的操作非常快
适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。

缺点：

遇到稀疏图，会导致申请过大的二维数组造成空间浪费且遍历边的时候需要遍历整个n * n矩阵，造成时间浪费

邻接表

邻接表使用数组 + 链表的方式来表示。邻接表是从边的数量来表示图，有多少边才会申请对应大小的链表。

邻接表的构造如图：

20241208_120929_473_copy

这里表达的图是：

节点1 指向节点3 和节点5
节点2 指向节点4、节点3、节点5
节点3 指向节点4
节点4指向节点1

邻接表的优点：

对于稀疏图的存储，只需要存储边，空间利用率高
遍历节点连接情况相对容易

缺点：

检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
实现相对复杂，不易理解

图的遍历方式

图的遍历方式基本是两大类：

深度优先搜索（dfs）
广度优先搜索（bfs）

DFS基础知识

DFS关键就两点：

搜索方向，是认准一个方向搜，直到碰壁之后再换方向
换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。

代码框架

正是因为dfs搜索可一个方向，并需要回溯，所以用递归的方式来实现是最方便的。

void dfs(参数) {
    处理节点
    dfs(图，选择的节点); // 递归
    回溯，撤销处理结果
}

98. 所有可达路径

卡码网题目链接（ACM模式）

【题目描述】

给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

【输入描述】

第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边

后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径

【输出描述】

输出所有的可达路径，路径中所有节点的后面跟一个空格，每条路径独占一行，存在多条路径，路径输出的顺序可任意。

如果不存在任何一条路径，则输出 -1。

邻接矩阵

import java.util.*;

public class Main{
    static List<Integer> path = new ArrayList<>();
    static List<List<Integer>> result = new ArrayList<>();
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(); // 节点
        int M = in.nextInt(); // 边
        int[][] graph = new int[N+1][N+1];
        for(int i = 0; i < M; i++){
            int s = in.nextInt();
            int t = in.nextInt();
            graph[s][t] = 1;
        }
        path.add(1);
        dfs(graph, 1, N);
        if(result.size() == 0) System.out.println(-1);
        else{
            for(List<Integer> p : result){
                for(int i = 0; i < p.size()-1; i++){
                    System.out.print(p.get(i) + " ");
                }
                System.out.println(p.get(p.size()-1));
            }
        }
        in.close();
    }
    private static void dfs(int[][] graph, int x, int n){
        if(x == n){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = 1; i <= n; i++){
            if(graph[x][i] == 1){
                path.add(i);
                dfs(graph, i, n);
                path.remove(path.size()-1);
            }
        }
    }
}

邻接表

import java.util.*;

public class Main{
    static List<Integer> path = new ArrayList<>();
    static List<List<Integer>> result = new ArrayList<>();
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(); // 节点
        int M = in.nextInt(); // 边
        List<LinkedList<Integer>> graph = new ArrayList<>(N+1);
        for(int i = 0; i <= N; i++){
            graph.add(new LinkedList<>());
        }
        for(int i = 0; i < M; i++){
            int s = in.nextInt();
            int t = in.nextInt();
            graph.get(s).add(t);
        }
        path.add(1);
        dfs(graph, 1, N);
        if(result.size() == 0) System.out.println(-1);
        else{
            for(List<Integer> p : result){
                for(int i = 0; i < p.size()-1; i++){
                    System.out.print(p.get(i) + " ");
                }
                System.out.println(p.get(p.size()-1));
            }
        }
        in.close();
    }
    private static void dfs(List<LinkedList<Integer>> graph, int x, int n){
        if(x == n){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i : graph.get(x)){
            path.add(i);
            dfs(graph, i, n);
            path.remove(path.size()-1);
        }
    }
}

BSF基础知识

广搜的搜索方式就适合于解决两个点之间的最短路径问题。

因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。

99. 岛屿数量

卡码网题目链接（ACM模式）

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

DFS

import java.util.*;

public class Main{
    public static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[][] arr = new int[N][M];
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                arr[i][j] = in.nextInt();
            }
        }

        in.close();
        int count = 0;
        boolean[][] visited = new boolean[N][M];
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(!visited[i][j] && arr[i][j] == 1){
                    count++;
                    visited[i][j] = true;
                    dfs(visited, i, j, arr);
                }
            }
        }

        System.out.println(count);
    }


    public static void dfs(boolean[][] visited, int x, int y, int[][] arr){
        for(int k = 0; k < 4; k++){
            int next_x = x + dir[k][0];
            int next_y = y + dir[k][1];
            if(next_x < 0 || next_x >= arr.length || next_y < 0 || next_y >= arr[0].length)
                continue;
            if(!visited[next_x][next_y] && arr[next_x][next_y] == 1){
                visited[next_x][next_y] = true;
                dfs(visited, next_x, next_y, arr);
            }

        }
    }
}

BFS

import java.util.*;

public class Main{
    public static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[][] arr = new int[N][M];
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                arr[i][j] = in.nextInt();
            }
        }

        in.close();
        int count = 0;
        boolean[][] visited = new boolean[N][M];
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(!visited[i][j] && arr[i][j] == 1){
                    count++;
                    bfs(visited, i, j, arr);
                }
            }
        }

        System.out.println(count);
    }


    public static void bfs(boolean[][] visited, int x, int y, int[][] arr){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x,y});
        visited[x][y] = true;


        while(!queue.isEmpty()){
            int cur_x = queue.peek()[0];
            int cur_y = queue.poll()[1];
            for(int k = 0; k < 4; k++){
                int next_x = cur_x + dir[k][0];
                int next_y = cur_y + dir[k][1];
                if(next_x < 0 || next_x >= arr.length || next_y < 0 || next_y >= arr[0].length)
                    continue;
                if(!visited[next_x][next_y] && arr[next_x][next_y] == 1){
                    queue.add(new int[]{next_x,next_y});
                    visited[next_x][next_y] = true;
                }
            }
        }
    }
}

01. 孤岛的总面积

卡码网：101. 孤岛的总面积(opens new window)

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。

解答：

DFS

BFS

import java.util.*;

public class Main{
    public static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
    public static int count = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[][] arr = new int[N][M];
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                arr[i][j] = in.nextInt();
            }
        }

        in.close();
        for(int i = 0; i < N; i++){ // 遍历左侧和右侧边界
            if(arr[i][0] == 1) bfs(i, 0, arr);
            if(arr[i][M-1] == 1) bfs(i, M-1, arr);
        }

        for(int j = 0; j < M; j++){ // 遍历上侧和下侧边界
            if(arr[0][j] == 1) bfs(0, j, arr);
            if(arr[N-1][j] == 1) bfs(N-1, j, arr);
        }

        count = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(arr[i][j] == 1) bfs(i, j, arr);
            }
        }

        System.out.println(count);
    }


    public static void bfs(int x, int y, int[][] arr){
        Queue<int[]> queue = new LinkedList<>();
        count++;
        queue.add(new int[]{x,y});
        arr[x][y] = 0;


        while(!queue.isEmpty()){
            int cur_x = queue.peek()[0];
            int cur_y = queue.poll()[1];
            for(int k = 0; k < 4; k++){
                int next_x = cur_x + dir[k][0];
                int next_y = cur_y + dir[k][1];
                if(next_x < 0 || next_x >= arr.length || next_y < 0 || next_y >= arr[0].length)
                    continue;
                if(arr[next_x][next_y] == 1){
                    count++;
                    queue.add(new int[]{next_x,next_y});
                    arr[next_x][next_y] = 0;
                }
            }
        }
    }
}

未完待续~~~

图的基本概念​

图的种类​

度​

连通性​

连通图​

强连通图​

连通分量​

强连通分量​

图的构造​

邻接矩阵​

邻接表​

图的遍历方式​

DFS基础知识​

代码框架​

98. 所有可达路径​

邻接矩阵​

邻接表​

BSF基础知识​

99. 岛屿数量​

DFS​

BFS​

01. 孤岛的总面积

DFS​

BFS​

图的基本概念

图的种类

度

连通性

连通图

强连通图

连通分量

强连通分量

图的构造

邻接矩阵

邻接表

图的遍历方式

DFS基础知识

代码框架

98. 所有可达路径

邻接矩阵

邻接表

BSF基础知识

99. 岛屿数量

DFS

BFS

DFS

BFS