经典Java面试题解析：拓扑排序

在 Java 的面试中，拓扑排序是一个常见的算法主题。本文将介绍一道经典的 Java 面试题——拓扑排序，并提供详细的解析和解题思路。

题目

 给定一个有向无环图（DAG），请输出一个拓扑排序序列。

解析与解题思路

拓扑排序是一种对有向无环图进行排序的算法。在进行拓扑排序时，我们需要根据图中的依赖关系确定节点的顺序。

首先，让我们定义一个数组 inDegree 用于记录每个节点的入度（即指向该节点的边的数量）。我们可以通过遍历有向图的边集，统计每个节点的入度。

接下来，我们需要找到没有前驱节点的起始节点。这些节点的入度为 0。我们可以将这些节点加入到拓扑排序的结果列表中，并将它们的后继节点的入度减 1。

然后，我们继续找到下一个入度为 0 的节点，并重复上述步骤，直到所有节点都被添加到拓扑排序的结果列表中。

如果最终结果列表中的节点数量与图中的节点数量相同，说明图中没有环，可以得到一个有效的拓扑排序序列。否则，图中存在环，无法进行拓扑排序。

以下是 Java 代码实例：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TopologicalSort {public static List topologicalSort(int numCourses, int[][] prerequisites) {int[] inDegree = new int[numCourses];

        // 统计每个节点的入度
        for (int[] prerequisite : prerequisites) {inDegree[prerequisite[0]]++;
        }

        Queue queue = new LinkedList();
        List result = new ArrayList();

        // 将入度为 0 的节点加入队列
        for (int i = 0; i ();
        }

        return result;
    }

    public static void main(String[] args) {
        int numCourses = 4;
        int[][] prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        List result = topologicalSort(numCourses, prerequisites);
        System.out.println("拓扑排序序列为：" + result);
    }
}

结论

通过拓扑排序算法，我们可以有效地对有向无环图进行排序。拓扑排序是面试中常见的算法题目，掌握了解题思路和实现代码，我们能够在面试中更加自信地回答相关问题。

  学 java，就到 java 编程狮 ！