經(jīng)典Java面試題解析：拓?fù)渑判?/h1>

待在綠匣里的貓 2023-07-11 09:22:08 瀏覽數(shù) (1862)

反饋

---

在Java的面試中，拓?fù)渑判蚴且粋€(gè)常見的算法主題。本文將介紹一道經(jīng)典的Java面試題——拓?fù)渑判?，并提供詳?xì)的解析和解題思路。

題目

 給定一個(gè)有向無環(huán)圖（DAG），請(qǐng)輸出一個(gè)拓?fù)渑判蛐蛄小?/p>

解析與解題思路

拓?fù)渑判蚴且环N對(duì)有向無環(huán)圖進(jìn)行排序的算法。在進(jìn)行拓?fù)渑判驎r(shí)，我們需要根據(jù)圖中的依賴關(guān)系確定節(jié)點(diǎn)的順序。

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

接下來，我們需要找到?jīng)]有前驅(qū)節(jié)點(diǎn)的起始節(jié)點(diǎn)。這些節(jié)點(diǎn)的入度為0。我們可以將這些節(jié)點(diǎn)加入到拓?fù)渑判虻慕Y(jié)果列表中，并將它們的后繼節(jié)點(diǎn)的入度減1。

然后，我們繼續(xù)找到下一個(gè)入度為0的節(jié)點(diǎn)，并重復(fù)上述步驟，直到所有節(jié)點(diǎn)都被添加到拓?fù)渑判虻慕Y(jié)果列表中。

如果最終結(jié)果列表中的節(jié)點(diǎn)數(shù)量與圖中的節(jié)點(diǎn)數(shù)量相同，說明圖中沒有環(huán)，可以得到一個(gè)有效的拓?fù)渑判蛐蛄小７駝t，圖中存在環(huán)，無法進(jìn)行拓?fù)渑判颉?/p>

以下是Java代碼實(shí)例：

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)計(jì)每個(gè)節(jié)點(diǎn)的入度
        for (int[] prerequisite : prerequisites) {
            inDegree[prerequisite[0]]++;
        }

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

        // 將入度為0的節(jié)點(diǎn)加入隊(duì)列
        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é)點(diǎn)的入度
            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("拓?fù)渑判蛐蛄袨椋? + result);
    }
}

結(jié)論

通過拓?fù)渑判蛩惴ǎ覀兛梢杂行У貙?duì)有向無環(huán)圖進(jìn)行排序。拓?fù)渑判蚴敲嬖囍谐Ｒ姷乃惴}目，掌握了解題思路和實(shí)現(xiàn)代碼，我們能夠在面試中更加自信地回答相關(guān)問題。

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