图论

图论

LuluyLand
  2025-04-14 22:38:34 2025-04-14 22:38:34 创建   2025-04-20 15:13:18 2025-04-20 15:13:18 更新      1.7k 字  9 分钟  

1. 岛屿问题

1.1. DFS遍历基本结构

DFS遍历关键点：①相邻结点 ②判断base case

图片1 图片2

避免重复遍历：标记——0 - 海洋； 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
26
void dfs(int[][] grid, int r, int c){
    //1. 判断base case
    if(!inArea(grid, r, c)){
        return;
    }
    
    //2. 如果不是岛屿，直接返回
    if(grid[r][c] != 1){
        return;
    }
    
    //3. 标记为已遍历
    grid[r][c] = 2; 
    
    //4. 访问上下左右四个相邻结点
    dfs(grid, r-1, c);
    dfs(grid, r+1, c);
    dfs(grid, r, c-1);
    dfs(grid, r, c+1);
}

//判断坐标(r,c)是否在网格中
boolean inArea(int[][] grid, int r, int c){
    return r>=0 && r<grid.length 
        && c>=0 && c<grid[0].length
}

1.2. BFS遍历基本结构

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
41
42
43
44
45
46
47
48
49
public void bfs(int[][] matrix, int i, int j){
    if(!inArea(matrix, i, j){
        return;
    }

    int n = matrix.length;
    int m = matrix[0].length;

    // 存储待访问结点
    Queue<int[]> queue = new LinkedList<>();
    // 标记是否被王文
    boolean[][] visited = new boolean[n][m];
    
    //起始节点加入
    queue.offer(new int[]{i, j});

    // 开始广度优先搜索
    while(!queue.isEmpty()){
        int[] current = queue.poll();
        int cur_i = current[0];
        int cur_j = current[1];
        //访问当前结点的操作...
        // System.out.println(matrix[cur_i][cur_j]);

        //遍历当前结点的相邻节点
        if(inArea(matrix, cur_i-1, cur_j)){
            queue.offer(new int[]{cur_i-1, cur_j});
            visited[cur_i-1][cur_j] = true;
        }
        if(inArea(matrix, cur_i+1, cur_j)){
            queue.offer(new int[]{cur_i+1, cur_j});
            visited[cur_i+1][cur_j] = true;
        }
        if(inArea(matrix, cur_i, cur_j-1)){
            queue.offer(new int[]{cur_i, cur_j-1});
            visited[cur_i][cur_j-1] = true;
        }
        if(inArea(matrix, cur_i, cur_j+1)){
            queue.offer(new int[]{cur_i, cur_j+1});
            visited[cur_i][cur_j+1] = true;
        }
    }

    
}

public boolean inArea(int[][] matrix, int i, int j){
    return i >= 0 && i < matrix.length && j >= 0 && j < matrix[0].length;
}

2. 最短路径

2.1. Dijkstra算法

适合场景：单源最短路径，权值非负

1. 三部曲
  1. 选源点到哪个节点近且该节点未被访问过
  2. 标记该节点
  3. 更新非访问节点到源点距离（minDist数组）
2. 重要数组

minDist[n]：记录每个节点距离源点的最小距离

3. 代码框架
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.*;

public class Main{
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt(); //节点个数
    int m = scanner.nextInt(); //边个数
    int[][] grid = new int[n+1][n+1]; //节点编号从1开始，存储图
    int[] minDist = new int[n+1]; //源点到每个节点的最短路径
    boolean[] visited = new boolean[n+1]; //顶点是否被访问过
    
    Arrays.fill(minDist, Integer.MAX_VALUE);
    for(int i = 0; i <= n; i++){ 
        Arrays.fill(grid[i], Integer.MAX_VALUE); //最大值填充
    }
    for(int i = 0; i < m; i++){
        int p1 = scanner.nextInt();
        int p2 = scanner.nextInt();
        int val = scanner.nextInt();
        grid[p1][p2] = val;
    }

    int start = 1;
    int end = n;
    minDist[start] = 0; //起始点到自身距离为0

    for(int i = 1; i <= n; i++){ //遍历所有节点
        int minVal = Integer.MAX_VALUE;
        int cur = 1;  //本轮选择的节点

        //1.选距离源点最近且未访问过的节点
        for(int v = 1; v <= n; v++){
            if(!visited[v] && minDist[v] < minVal){
                minVal = minDist[v];
                cur = v;
            }
        }
        
        //2. 标记该结点被访问过
        visited[cur] = true;
        
        // 3.更新非cur节点到原点距离
        for(int v = 1; v <= n; v++){
            if(!visited[v] 
               && grid[cur][v] != Integer.MAX_VALUE 
               && minDist[cur] + grid[gur][v] > minDist[v]){
                minDist[v] = minDist[cur] + grid[gur][v];
               }
        }
    }

    if(minDist[end] == Integer.MAX_VALUE){
        System.out.println(-1); //不能到达终点
    }
    else{
        System.out.println(minDist[end]); 
    }
}

用堆优化后

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.util.*;

class Edge{
    int to; //邻接顶点
    int val; //边权重

    Edge(int to, int val){
        this.to = to;
        this.val = val;
    }
}

class Pair<U,V>{
    public final U first;  //节点编号
    public final V second; //最短路径

    public Pair(U first, V second){
        this.first = first;
        this.second = second;
    }
}

class MyComparator implements Comparator<Pair<Integer, Integer>>{
    @Override
    public int compare(Pair<Integer, Integer> lhs, Pair<Integer, Integer> rhs){
        return Integer.compare(lhs.second, rhs.second);
    }
}

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); //节点数
        int m = scanner.nextInt(); //边数
        List<List<Edge>> grid = new ArrayList<>(n+1);//邻接表
        int[] minDist = new int[n+1]; //到源点最短路径
        Arrays.fill(minDist, Integer.MAX_VALUE);
        boolean[] visited = new boolean[n+1]; //记录是否被访问过
        
        for(int i = 0; i <= n; i++){
            grid.add(new ArrayList<>());
        }
        for(int i = 0; i < m; i++){
            int p1 = scanner.nextInt();
            int p2 = scanner.nextInt();
            int val = scanner.nextInt();
            grid.get(p1).add(new Edge(p2, val);
        }

        int start = 1, end = n;
        minDist[start] = 0;
    
        //优先队列存放Pair<节点，源点到该节点的权值
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(new MyComparator()); 
        // 初始化队列
        pq.add(new Pair<>(start, 0));


        while(!pq.isEmpty()){
            // 1.选源点到哪个节点近且该节点未被访问过（通过优先级队列实现）
            Pair<Integer, Integer> cur = pq.poll();
            if(visited[cur.first]) continue;

            // 2.标记该节点
            visited[first] = true;

            // 3.更新minDist数组
            for(Edge edge : grid.get(cur.first)){
                if(!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]){
                    minDist[edge.to] = minDist[cur.first] + edge.val;
                    pq.add(new Pair<>(edge.to, minDist[edge.to]));
            }
            
        }
            
        if (minDist[end] == Integer.MAX_VALUE) {
            System.out.println(-1); // 不能到达终点
        } else {
            System.out.println(minDist[end]); // 到达终点最短路径
        }
        
    }
}

2.2. Floyd算法

适合场景：多源最短路径、可正可负、动态规划

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.util.*;

class Edge{
    int to; //邻接顶点
    int val; //边权重

    Edge(int to, int val){
        this.to = to;
        this.val = val;
    }
}

class Pair<U,V>{
    public final U first;  //节点编号
    public final V second; //最短路径

    public Pair(U first, V second){
        this.first = first;
        this.second = second;
    }
}

class MyComparator implements Comparator<Pair<Integer, Integer>>{
    @Override
    public int compare(Pair<Integer, Integer> lhs, Pair<Integer, Integer> rhs){
        return Integer.compare(lhs.second, rhs.second);
    }
}

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); //节点数
        int m = scanner.nextInt(); //边数
        List<List<Edge>> grid = new ArrayList<>(n+1);//邻接表
        int[] minDist = new int[n+1]; //到源点最短路径
        Arrays.fill(minDist, Integer.MAX_VALUE);
        boolean[] visited = new boolean[n+1]; //记录是否被访问过
        
        for(int i = 0; i <= n; i++){
            grid.add(new ArrayList<>());
        }
        for(int i = 0; i < m; i++){
            int p1 = scanner.nextInt();
            int p2 = scanner.nextInt();
            int val = scanner.nextInt();
            grid.get(p1).add(new Edge(p2, val);
        }

        int start = 1, end = n;
        minDist[start] = 0;
    
        //优先队列存放Pair<节点，源点到该节点的权值
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(new MyComparator()); 
        // 初始化队列
        pq.add(new Pair<>(start, 0));


        while(!pq.isEmpty()){
            // 1.选源点到哪个节点近且该节点未被访问过（通过优先级队列实现）
            Pair<Integer, Integer> cur = pq.poll();
            if(visited[cur.first]) continue;

            // 2.标记该节点
            visited[first] = true;

            // 3.更新minDist数组
            for(Edge edge : grid.get(cur.first)){
                if(!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]){
                    minDist[edge.to] = minDist[cur.first] + edge.val;
                    pq.add(new Pair<>(edge.to, minDist[edge.to]));
            }
            
        }
            
        if (minDist[end] == Integer.MAX_VALUE) {
            System.out.println(-1); // 不能到达终点
        } else {
            System.out.println(minDist[end]); // 到达终点最短路径
        }
        
    }
}

参考链接

https://leetcode.cn/problems/number-of-islands/solutions/211211/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-

  • 标题: 图论
  • 作者: LuluyLand
  • 创建于 : 2025-04-14 22:38:34
  • 更新于 : 2025-04-20 15:13:18
  • 链接: https://luluy233.github.io/2025/04/14/图论/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
图论
  1. 1. 岛屿问题
    1. 1.1. DFS遍历基本结构
    2. 1.2. BFS遍历基本结构
  2. 2. 最短路径
    1. 2.1. Dijkstra算法
      1. 1. 三部曲
      2. 2. 重要数组
      3. 3. 代码框架
    2. 2.2. Floyd算法
  3. 参考链接