描述
給定一個有向圖柠偶，圖節(jié)點的拓?fù)渑判虮欢x為：
對于每條有向邊A--> B，則A必須排在B之前
拓?fù)渑判虻牡谝粋€節(jié)點可以是任何在圖中沒有其他節(jié)點指向它的節(jié)點
拓?fù)渑判蚣窗凑請D中每個結(jié)點優(yōu)先級順序?qū)⒔Y(jié)點排好順序
挑戰(zhàn)
用 bfs 和 dfs 完成
注意事項
你可以假設(shè)圖中至少存在一種拓?fù)渑判?/p>
- 統(tǒng)計圖中每個點的入度
- 將入度為0的點放到隊列中去
- bfs 整個圖，每遍歷一個循環(huán)即代表當(dāng)前層全部遍歷結(jié)束间坐，結(jié)點的度減一
代碼
/*
* Definition for Directed graph.
* class DirectedGraphNode {
* int label;
* ArrayList<DirectedGraphNode> neighbors;
* DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
* };
*/
public class Solution {
/**
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
ArrayList<DirectedGraphNode> result = new ArrayList<>();
if (graph == null) {
return result;
}
// 調(diào)用定義好的方法統(tǒng)計入度
Map<DirectedGraphNode, Integer> indegree = getIndegree(graph);
Queue<DirectedGraphNode> queue = new LinkedList<>();
// 把indegree為0的存入queue中去
for (DirectedGraphNode node : graph) {
if (indegree.get(node) == 0) {
queue.offer(node);
result.add(node);
}
}
// 進入BFS計算模版
while (!queue.isEmpty()) {
DirectedGraphNode node = queue.poll();
for (DirectedGraphNode neighbor : node.neighbors) {
// node 從隊列中拿出來后潮尝，相鄰結(jié)點的 indegree 要減 1
// neighbor 的入度先減 1，然后再用 if 判斷入度是否為 0
// 在 BFS 中入度代表有幾個結(jié)點在前面沒有遍歷
indegree.put(neighbor, indegree.get(neighbor) - 1);
if (indegree.get(neighbor) == 0) {
queue.offer(neighbor);
result.add(neighbor);
}
}
}
return result;
}
private Map<DirectedGraphNode, Integer> getIndegree(ArrayList<DirectedGraphNode> graph) {
// 結(jié)點和度值之間是哈希表對應(yīng)關(guān)系
Map<DirectedGraphNode, Integer> indegree = new HashMap<>();
// 初始化每個結(jié)點的入度為0
for (DirectedGraphNode node : graph) {
indegree.put(node, 0);
}
// node->neighbor
for (DirectedGraphNode node : graph) {
for (DirectedGraphNode neighbor: node.neighbors) {
indegree.put(neighbor, indegree.get(neighbor) + 1);
}
}
return indegree;
}
}
- 應(yīng)注意graph是存儲著結(jié)點的數(shù)組
- 如下錯誤寫法：
while (!queue.isEmpty()) {
DirectedGraphNode node = queue.poll();
// 前面已經(jīng)for循環(huán)過所有結(jié)點了就不要再加下面這句
for (DirectedGraphNode node : graph) {
for (DirectedGraphNode neighbor : node.neighbors) {
indegree.put(neighbor, indegree.get(neighbor) - 1);
if (indegree.get(neighbor) == 0) {
queue.offer(neighbor);
result.add(neighbor);
}
}
}
return result;
}
3 .本題前提說明了圖一定存在拓?fù)渑判蚶砭ィ绻麤]有說明一定存在拓?fù)渑判蚝诮纾瑒t把return result;換成
if (result.size() == graph.size()) {
return result;
}
return null;
