經(jīng)典Java面試題解析：拓撲排序

在Java的面試中，拓撲排序是一個常見的算法主題。本文將介紹一道經(jīng)典的Java面試題——拓撲排序，并提供詳細的解析和解題思路。

題目

 給定一個有向無環(huán)圖（DAG），請輸出一個拓撲排序序列。

解析與解題思路

拓撲排序是一種對有向無環(huán)圖進行排序的算法。在進行拓撲排序時，我們需要根據(jù)圖中的依賴關(guān)系確定節(jié)點的順序。

首先，讓我們定義一個數(shù)組inDegree用于記錄每個節(jié)點的入度（即指向該節(jié)點的邊的數(shù)量）。我們可以通過遍歷有向圖的邊集，統(tǒng)計每個節(jié)點的入度。

接下來，我們需要找到?jīng)]有前驅(qū)節(jié)點的起始節(jié)點。這些節(jié)點的入度為0。我們可以將這些節(jié)點加入到拓撲排序的結(jié)果列表中，并將它們的后繼節(jié)點的入度減1。

然后，我們繼續(xù)找到下一個入度為0的節(jié)點，并重復(fù)上述步驟，直到所有節(jié)點都被添加到拓撲排序的結(jié)果列表中。

如果最終結(jié)果列表中的節(jié)點數(shù)量與圖中的節(jié)點數(shù)量相同，說明圖中沒有環(huán)，可以得到一個有效的拓撲排序序列。否則，圖中存在環(huán)，無法進行拓撲排序。

以下是Java代碼實例：

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

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

        // 統(tǒng)計每個節(jié)點的入度
        for (int[] prerequisite : prerequisites) {
            inDegree[prerequisite[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();

        // 將入度為0的節(jié)點加入隊列
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            result.add(curr);

            // 減少后繼節(jié)點的入度
            for (int[] prerequisite : prerequisites) {
                if (prerequisite[1] == curr) {
                    inDegree[prerequisite[0]]--;

                    if (inDegree[prerequisite[0]] == 0) {
                        queue.offer(prerequisite[0]);
                    }
                }
            }
        }

        // 判斷是否存在環(huán)
        if (result.size() != numCourses) {
            return new ArrayList<>();
        }

        return result;
    }

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

結(jié)論

通過拓撲排序算法，我們可以有效地對有向無環(huán)圖進行排序。拓撲排序是面試中常見的算法題目，掌握了解題思路和實現(xiàn)代碼，我們能夠在面試中更加自信地回答相關(guān)問題。

 學(xué)java，就到java編程獅！