邻接矩阵

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

邻接表

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

深度优先搜索

深搜三部曲

  1. 确认递归函数，参数
  2. 确认终止条件
  3. 处理目前搜索节点出发的路径

所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

题目中暗含了邻接表的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> path;
    vector<vector<int>> ans;
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        path.push_back(0);//第一个点一定是0
        dfs(graph,0);
        return ans;
    }

    void dfs(vector<vector<int>>& graph,int pos){
        if(pos==graph.size()-1){
            ans.push_back(path);
            return ;
        }
        for(int i=0;i<graph[pos].size();i++){
            path.push_back(graph[pos][i]);//加入邻接表中连接的点
            dfs(graph,graph[pos][i]);
            path.pop_back();
        }
    }
};

广度优先搜索

一般采取队列作为容器进行遍历

岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

实例

输入：grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出：1

深度搜索优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int m,n;
    int numIslands(vector<vector<char>>& grid) {
        m=grid.size(),n=grid[0].size();
        vector<vector<bool>> visited(m,vector<bool>(n,false));
        int count=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(!visited[i][j]&&grid[i][j]=='1'){
                    count++;
                    dfs(grid,visited,i,j);
                }
            }
        }
        return count;
    }

    void dfs(vector<vector<char>>& grid,vector<vector<bool>>& visited,int i,int j){
        visited[i][j]=true;
        int dx[4]={0,0,1,-1};
        int dy[4]={1,-1,0,0};
        for(int k=0;k<4;k++){
            int x=i+dx[k];
            int y=j+dy[k];
            if(x>=0&&x<m&&y>=0&&y<n&&!visited[x][y]&&grid[x][y]=='1'){
                dfs(grid,visited,x,y);
            }
        }
    }
};

广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int m, n;
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    count++;
                    bfs(grid, visited, i, j);
                }
            }
        }
        return count;
    }

    void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int i,
             int j) {
        queue<pair<int, int>> q;
        q.push({i, j});
        visited[i][j] = true;
        int dx[4] = {0, 0, 1, -1};
        int dy[4] = {1, -1, 0, 0};
        while (!q.empty()) {
            auto cur=q.front();
            q.pop();
            int x=cur.first,y=cur.second;
            for(int k=0;k<4;k++){
                int newX=x+dx[k];
                int newY=y+dy[k];
                if(newX>=0&&newX<m&&newY>=0&&newY<n&&!visited[newX][newY]&&grid[newX][newY]=='1'){
                    q.push({newX,newY});
                    visited[newX][newY]=true;
                }
            }
        }
    }
};

并查集

并查集主要有两个功能:

  1. 将两个元素添加到一个集合中
  2. 判断两个元素在不在同一个集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}