破晓的知识屋
0%

拓扑排序

发表于 分类于 ， ， 阅读次数： Valine：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

[toc]

概念和场景#

做法#

拓扑排序算法步骤：

  1. 得到所有节点的相邻点列表
  2. 得到所有节点的入度数量数组（切记，不可用相邻点列表代替入度数量，会炸的，因为过程中会改变，很麻烦的）
  3. 每次选入度为0的点做处理，对相邻点的入度数量做更新，减1
  4. 如果每次选很费时间，可以引入队列，队列时，每次要把队列里的全取出来再处理，而不是依次处理。每次出队的那一堆都是临时答案。

模板#

简易版本（n<=1000)#

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
int[] inCount = new int[k+1];
List<Integer>[] outLists = new List[k+1];
for (int i = 1; i <=k;i++) {
    outLists[i] = new ArrayList();
}
for (int[] row : rowConditions) {
    inCount[row[1]]++;
    outLists[row[0]].add(row[1]);
}
int y = 0;
boolean[] vis = new boolean[k+1];
int n = inCount.length; 
while (n-->0) {
    int i;
    for (i = 1; i <= k; i++) {
        if (inCount[i]  > 0 || vis[i]) {
            continue;
        }
        vis[i] = true;
        for (int out : outLists[i]) {
            inCount[out]--;
        }
        // 记录这个点
        break;
    }
}

带队列的高性能版本（但容易写错）#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
List<Integer> result = new ArrayList<>();
while(!queue.isEmpty()) {
    int size = queue.size();
    List<Integer> needDeleteNodes = new ArrayList<>();
    needDeleteNodes.addAll(queue);
    queue.clear();
    // 要每次都更新这个result
    result = new ArrayList<>();
    for (int needDeleNode : needDeleteNodes) {
        result.add(needDeleNode);
        for (int nextNode : nextNodes[needDeleNode]) {
            // 不能delete
            edgCounts[nextNode]--;
            if (edgCounts[nextNode] == 1) {
                queue.offer(nextNode);
            }
        }
    }
}

相关题目#

310. 最小高度树 - 力扣（LeetCode）

6163. 给定条件下构造矩阵 - 力扣（LeetCode）