图论算法

图论介绍

图的概念

图（Graph）：由顶点集合 V 和边集合 E（即顶点之间的连接关系）组成的数据结构，通常记作 G=(V,E)

图的存储

主要介绍两种，邻接矩阵和邻接表：

邻接矩阵表示：

邻接矩阵（Adjacency Matrix）：通过一个二维数组 adj 来表示顶点之间的连接关系

• 对于无权图，如果 adj[i][j] == 1，表示顶点 v_i 与 v_j 之间有边；如果 adj[i][j] = 0，则表示两者之间无边。
• 对于带权图，如果 adj[i][j] == w 且 w ≠ ∞，则表示 v_i 到 v_j 有一条权值为 w 的边；如果 adj[i][j] = ∞，则表示两者之间无边

邻接矩阵的主要特点如下：

• 优点：结构简单，便于实现；可以快速判断任意两个顶点之间是否存在边，也能直接获取边的权值
• 缺点：初始化和遍历效率较低，空间占用大且利用率不高，无法表示重边，顶点的增删操作不便。当顶点数量较大时，采用空间复杂度为 n × n 的二维数组存储邻接矩阵在实际应用中难以实现

邻接表表示：

邻接表（Adjacency List）：一种结合顺序存储与链式存储的图结构。它主要由两部分组成：

• 用于存放所有顶点信息的数组
• 用于存放每个顶点所有邻接边的链表

邻接表的主要特点如下：

• 优点：
  结构灵活，空间利用率高，只为存在的边分配存储空间，空间复杂度为 O(n + m)（其中 n 为顶点数，m 为边数），特别适合稀疏图；遍历某个顶点的所有邻接点效率高；顶点的增加相对方便

• 缺点：
  实现相对复杂；判断任意两个顶点之间是否存在边效率较低，通常需要遍历邻接链表；无法像邻接矩阵那样直接获取边的权值；在图较为稠密时，空间和访问效率可能不如邻接矩阵

---

图论算法

DFS-深度优先搜索

1. 岛屿数量

LeetCode 200. 岛屿数量

问题描述
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成，此外，你可以假设该网格的四条边均被水包围

思路
遍历数组中的每个点，如果发现是陆地（1），进行dfs，将他周围（属于一个岛屿）的所有陆地标记成海洋（0），岛屿数量加一，之后继续遍历，直到结束

代码实现

void dfs(char** grid, int m, int n, int i, int j){
    // 递归结束条件，这里注意先判定i和j的合法性
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
        return;
    }
    grid[i][j]=0;
    dfs(grid, m, n, i, j - 1); // 往左走
    dfs(grid, m, n, i, j + 1); // 往右走
    dfs(grid, m, n, i - 1, j); // 往上走
    dfs(grid, m, n, i + 1, j); // 往下走
}
int numIslands(char** grid, int gridSize, int* gridColSize){
    int m = gridSize, n = gridColSize[0];
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') { // 找到了一个新的岛
                dfs(grid, m, n, i, j); // 把这个岛插满旗子，这样后面遍历到的 '1' 一定是新的岛
                ans++;
            }
        }
    }
    return ans;
}

---

BFS-广度优先搜索

1. 腐烂的橘子

LeetCode 994. 腐烂的橘子

问题描述
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

思路

初始化队列：
遍历网格，所有腐烂橘子坐标入队（时间=0）

BFS扩散：

• 从队列取出当前橘子
• 向上下左右四个方向检查
• 如果是新鲜橘子则标记为腐烂，之后入队（时间 = 当前时间 + 1）
• 记录时间：用 max_time 记录遇到的最大时间

最终检查：
遍历网格，还有新鲜橘子 → 返回 -1
否则返回 `max_time

代码实现

typedef struct {
    int i;
    int j;
    int time;
} node;
int orangesRotting(int** grid, int gridSize, int* gridColSize) {

    int front = 0, rear = 0;
    int m = gridSize;
    int n = gridColSize[0];
    node queue[m * n];

    // 初始化：将所有腐烂的橘子入队
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) {
                queue[rear].i = i;
                queue[rear].j = j;
                queue[rear].time = 0;
                rear++;
            }
        }
    }

    int max_time = 0;
    int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};

    // BFS
    while (front < rear) {
        node cur = queue[front++];
        max_time = cur.time > max_time ? cur.time : max_time;

        for (int d = 0; d < 4; d++) {
            int ni = cur.i + dirs[d][0];
            int nj = cur.j + dirs[d][1];
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                grid[ni][nj] = 2; // 腐烂
                queue[rear].i = ni;
                queue[rear].j = nj;
                queue[rear].time = cur.time + 1;
                rear++;
            }
        }
    }

    // 检查是否还有新鲜橘子
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                return -1;
            }
        }
    }

    return max_time;
}

---

拓扑排序

最小生成树

单源最短路径