Day58--图论--117. 软件构建（卡码网），47. 参加科学大会（卡码网）

Day58–图论–117. 软件构建（卡码网），47. 参加科学大会（卡码网）

今天主要学习：拓扑排序，和最短路算法之Dijkstra

拓扑排序：给出一个有向图，把这个有向图转成线性的排序就叫拓扑排序。也是图论中判断有向无环图的常用方法。

Dijkstra：和Prim是一个模具里面刻出来的。

117. 软件构建（卡码网）

方法：拓扑排序

思路：

1. 记录每个节点的入度
2. 添加入度为零的节点入队
3. 把这个节点从图中删除（这题，把这个节点的to所在节点的入度减一就好）
4. 如果再有入度为零的节点，再入队，再删除。
5. 直到队列为空，且节点已经处理完。否则就是存在环。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 录入数据
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        // 记录每个节点的入度
        int[] inDegree = new int[n];
        // 记录每一条边
        int[][] edges = new int[m][2];
        // 录入边，并记录每个节点的入度
        for (int i = 0; i < m; i++) {
            edges[i][0] = in.nextInt();
            edges[i][1] = in.nextInt();
            inDegree[edges[i][1]]++;
        }
        // 队列，添加入度为0的节点
        Deque<Integer> que = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                que.offer(i);
            }
        }
        // 结果集
        List<Integer> res = new ArrayList<>();
        // 处理入度为0的节点
        while (!que.isEmpty()) {
            int node = que.poll();
            // 加入结果集
            res.add(node);
            // 把这个节点从图中删掉，其实就是去边集中，找到以这个节点为from起点的边，把它们的to终点的入度减一
            for (int i = 0; i < m; i++) {
                if (edges[i][0] == node) {
                    inDegree[edges[i][1]]--;
                    // 如果入度减一为零，那么这个节点也入队
                    if (inDegree[edges[i][1]] == 0) {
                        que.offer(edges[i][1]);
                    }
                }
            }
        }
        // 如果队列已经空了，还没有处理完所有文件的话，那就是有环
        if (que.isEmpty() && res.size() != n) {
            System.out.println(-1);
            return;
        }
        // 打印输出
        System.out.print(res.get(0));
        for (int i = 1; i < n; i++) {
            System.out.print(" " + res.get(i));
        }
    }
}

47. 参加科学大会（卡码网）

方法：dijkstra

思路：

和Prim算法，差不多是一个模具里面刻出来的。

都是以“点”为中心，都需要visited数组标记，都需要minDist记录距离。连步骤都一样。

唯一的区别是：minDist[j] = minDist[cur] + grid[cur][j];，这里是累加和，Prim是只用记录grid[cur][j]

重复一下三个步骤：

1. 第一步，选源点到哪个节点近且该节点未被访问过
2. 第二步，该最近节点被标记访问过
3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] grid = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(grid[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i < m; i++) {
            int from = in.nextInt();
            int to = in.nextInt();
            int val = in.nextInt();
            grid[from][to] = val;
        }

        int start = 1;
        int end = n;

        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);

        boolean[] visited = new boolean[n + 1];
        minDist[start] = 0;

        for (int i = 1; i <= n; i++) {
            int minVal = Integer.MAX_VALUE;
            int cur = 1;

            for (int j = 1; j <= n; j++) {
                if (!visited[j] && minDist[j] < minVal) {
                    minVal = minDist[j];
                    cur = j;
                }
            }

            visited[cur] = true;

            for (int j = 1; j <= n; j++) {
                if (!visited[j]
                        && grid[cur][j] != Integer.MAX_VALUE
                        && minDist[cur] != Integer.MAX_VALUE
                        && minDist[cur] + grid[cur][j] < minDist[j]) {
                    minDist[j] = minDist[cur] + grid[cur][j];
                }
            }
        }
        if (minDist[end] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(minDist[end]);
        }
    }
}