拓扑排序

拓扑排序（Topological Sorting）是一种针对有向无环图（DAG）的排序算法。在拓扑排序中，图中的顶点被安排成一个线性序列，使得如果图中存在一条从顶点 u 到顶点 v 的有向边，则在序列中顶点 u 出现在顶点 v 之前。

拓扑排序通常用于描述一组任务或事件之间的依赖关系，其中每个任务都有一些前置任务，必须在它们完成后才能执行。通过拓扑排序，我们可以确定一种合理的执行顺序，以确保所有任务都按照其依赖关系得到正确执行。

在实现上，拓扑排序可以根据下面的步骤实现：

找到入度为 0 的顶点，把这些节点加入到排序结果中，这些节点没有前置任务
将已经加入到排序结果中的节点及其相连的边删去，更改图中其他节点的入度
重复 1，2 步，直到图中没有入度为 0 的节点

如果被拓扑排序的图是一个有向无环图，那么所有顶点都会被排序；而如果图中有环，则拓扑排序只会得到一部分的节点序列。

因此，拓扑排序也常被用来检测一个图中是否有环。

下面是拓扑排序入门的一个经典案例及其代码实现（2024春招字节跳动暑期实习一面代码题）：

题目描述: 一共有 n 门课你可以选，从课程0，1到课程 n-1 。有一个数组 p , p[i] = [a, b] 表示你必须要先修完课程 b 才可以修课程 a 。请写一个方程返回 true / false 表示你是否能修完所有的课程。

package com.ymiir;

import java.util.*;

public class Main {

    public static boolean topologicalSorting(int n, int[][] graph){
        // 创建入度数组，存储每个节点的入度
        int[] inDegree = new int[n];
        // 邻接矩阵
        Map<Integer, List<Integer>> map = new HashMap<>();
        // 入度数组置 0
        for(int i=0;i<n;i++){
            inDegree[i] = 0;
        }
        // 初始化邻接矩阵和入度数组
        for(int i=0;i<graph.length;i++){
            int node = graph[i][0];
            int pre = graph[i][1];
            inDegree[node]++;
            map.computeIfAbsent(pre, k->new ArrayList<>()).add(node);
        }
        // 创建队列并初始化队列，将入度为 0 的节点入队，用于拓扑排序
        Queue<Integer> queue = new ArrayDeque<>();
        for(int i=0;i<n;i++){
            if(inDegree[i]==0){
                queue.offer(i);
            }
        }

        // 拓扑排序
        // count 用于记录拓扑排序遍历到的节点
        int count = 0;
        while(!queue.isEmpty()){
            // 一个元素出队
            int temp = queue.poll();
            count++;
            // 如果邻接矩阵中有
            if(map.containsKey(temp)){
                // 删掉当前元素及与之相连的边，具体表现在子节点入度 -1
                for(int v : map.get(temp)){
                    inDegree[v]--;
                    // 如果调整之后入度为 0 ，则可以放入拓扑排序序列，入队
                    if(inDegree[v]==0){
                        queue.add(v);
                    }
                }
            }
        }
        // 如果拓扑排序遍历到了所有的节点，则说明可以修完所有的课
        return count==n;
    }

    public static void main(String[] args) {
        int[][] graph = ;
        boolean flag = topologicalSorting(4,graph);
        System.out.println(flag);
    }
}

拓扑排序

Comments