在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ù)渑判蛐蛄小7駝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ù)渑判蚴敲嬖囍谐R姷乃惴}目,掌握了解題思路和實(shí)現(xiàn)代碼,我們能夠在面試中更加自信地回答相關(guān)問題。
學(xué)java,就到java編程獅!