拓撲序一定是有向無環(huán)圖。
拓撲排序不唯一
拓撲排序方法一：
利用入度為零進行排序
思路：誰的入度為0，誰就是開始節(jié)點，將開始節(jié)點打印完之后，將開始節(jié)點的直接鄰居的入度減1，然后重復(fù)。
package algorithmbasic.class17;
import java.util.*;
//圖的拓撲排序
public class TopologySort {
public static List<Node> sortedTopology(Graph graph) {
//result用來盛放排序結(jié)果。
List<Node> result = new ArrayList<>();
//inmap存放節(jié)點與入度的對應(yīng)值。
//key ——> 某個節(jié)點， value ——> 剩余入度
HashMap<Node, Integer> inmap = new HashMap<>();
//只有節(jié)點的入度為0才可以進入此隊列。
Queue<Node> inZeroQueue = new LinkedList<>();
for (Node node : graph.nodes.values()) {
inmap.put(node, node.in);
if (node.in == 0) {
inZeroQueue.add(node);
}
}
Node cur = inZeroQueue.poll();
result.add(cur);
for (Node next : cur.nexts) {
//剩余入度減1.
inmap.put(next, inmap.get(next) - 1);
if (inmap.get(next) == 0) {
inZeroQueue.add(next);
}
}
return result;
}
}
拓撲排序方法二：
利用點次進行排序。
點次越大的，排序位置越靠前。
而且我發(fā)現(xiàn)可以使用遞歸進行求點次。我們要求0的點次，那就需要求他的直接鄰居1，2，3的點次，然后對鄰居的點次求和再加1，就是0的點次。我們可以將每個點的點次放在一個表里面，這個表記錄著哪個節(jié)點的點次對應(yīng)著多少。這樣我們再求其他節(jié)點點次時直接從表里拿就行，減少重復(fù)性工作。
思路：
1：創(chuàng)建一個表 HashMap<DirectedGraphNode, Record> order = new HashMap<>() 用來記錄每個節(jié)點對應(yīng)的點次是多少。2：遍歷整個圖中的每一個節(jié)點，記錄其點次。
3：創(chuàng)建一個有序表ArrayList records = new ArrayList<>() 用來記錄點次。
4：根據(jù)點次進行由大到小的排序。records.sort(new MyComparator());
5：然后再創(chuàng)建一個有序表ArrayList dnodes = new ArrayList<>() 根據(jù)點次的順序記錄節(jié)點。
注意為什么要創(chuàng)建Record這個內(nèi)部類。因為在 “ 根據(jù)點次的順序記錄節(jié)點” 時，我們需要根據(jù)點次找到對應(yīng)的節(jié)點，使用map是不可以的，因為點次大小有重復(fù)的。所以我們采用內(nèi)部類的方法，這樣每個點次都會有一一對應(yīng)的節(jié)點。
package algorithmbasic.class17;
//圖的拓撲排序方法二
import java.util.*;
// OJ鏈接：https://www.lintcode.com/problem/topological-sorting
public class TopologicalOrderDFS2 {
/**
* 節(jié)點內(nèi)部類
*/
// 不要提交這個類
public static class DirectedGraphNode {
public int label;
public ArrayList<DirectedGraphNode> neighbors;
public DirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<DirectedGraphNode>();
}
}
/**
* 點次內(nèi)部類。
*/
//記錄某個節(jié)點的點次。
public static class Record {
public DirectedGraphNode node;
//點次。
public long nodes;
public Record(DirectedGraphNode node, long nodes) {
this.node = node;
this.nodes = nodes;
}
}
/**
* topSort方法
* 傳入一張圖的所有節(jié)點，返回排序好后的所有節(jié)點。
*/
public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
//采用計算每個節(jié)點點次的方法。
//建立一張表用來記錄每個節(jié)點對應(yīng)的點次是多少。
HashMap<DirectedGraphNode, Record> order = new HashMap<>();
ArrayList<Record> records = new ArrayList<>();
ArrayList<DirectedGraphNode> dnodes = new ArrayList<>();
//遍歷圖中每個節(jié)點，并記錄每個節(jié)點出現(xiàn)的點次。
for (DirectedGraphNode cur : graph) {
Record record = process(cur, order);
records.add(record);
//order.put(cur, record);
}
//Arrays.sort(records,new MyComparator());
records.sort(new MyComparator());
for (Record r : records) {
dnodes.add(r.node);//這就是為什么要建立Record這個內(nèi)部類的原因。
}
return dnodes;
}
/**
* 求點次的方法。
*/
//傳入一個節(jié)點返回這個節(jié)點的點次。在遞歸的過程當中每個節(jié)點的點次其實都已經(jīng)記錄好了。
public static Record process(DirectedGraphNode node, HashMap<DirectedGraphNode, Record> order) {
if (order.containsKey(node)) {
return order.get(node);
}
//order中沒有該點。
long count = 0;
for (DirectedGraphNode n : node.neighbors) {
Record r = process(n, order);
count += r.nodes;
}
Record record = new Record(node, count + 1);
//先把當前節(jié)點及其點次放入map中然后再返回。這樣我們再求其他節(jié)點點次時直接從表里拿就行，減少重復(fù)性工作。
order.put(node, record);
return record;
}
/**
* 比較器
*/
public static class MyComparator implements Comparator<Record> {
@Override
public int compare(Record o1, Record o2) {
//不要將long類型數(shù)據(jù)強制轉(zhuǎn)換成int類型，會出現(xiàn)溢出和截斷的風險，導(dǎo)致數(shù)據(jù)出現(xiàn)錯誤。
//例如2147483648L -> int:-2147483648
//它超過了int類型的最大值 2147483647。當將其強制轉(zhuǎn)換為int類型時，結(jié)果被截斷為int類型的最小值 -2147483648。
//return (int)(o2.nodes - o1.nodes);
return o1.nodes == o2.nodes ? 0 : (o1.nodes > o2.nodes ? -1 : 1);
}
}
}
拓撲排序方法三：
根據(jù)深度進行排序
文章來源：http://www.zghlxwxcb.cn/news/detail-469899.html
package algorithmbasic.class17;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
public class TopologicalOrderDFS1 {
/**
* 節(jié)點內(nèi)部類
*/
public static class DirectedGraphNode {
public int label;
public ArrayList<DirectedGraphNode> neighbors;
public DirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<DirectedGraphNode>();
}
}
/**
* 深度內(nèi)部類。
*/
public static class Deep {
public long deep;
public DirectedGraphNode node;
public Deep(long deep, DirectedGraphNode node) {
this.deep = deep;
this.node = node;
}
}
/**
* topSort方法
*/
public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
HashMap<DirectedGraphNode, Deep> order = new HashMap<>();
ArrayList<Deep> deeps = new ArrayList<>();
ArrayList<DirectedGraphNode> dNodes = new ArrayList<>();
for (DirectedGraphNode node : graph) {
Deep d = process(node, order);
deeps.add(d);
}
deeps.sort(new MyComparator());
for (Deep d : deeps) {
dNodes.add(d.node);
}
return dNodes;
}
public static Deep process(DirectedGraphNode node, HashMap<DirectedGraphNode, Deep> order) {
if (order.containsKey(node)) {
return order.get(node);
}
long max = Long.MIN_VALUE;
for (DirectedGraphNode n : node.neighbors) {
Deep d = process(n, order);
max = Math.max(max, d.deep);
}
Deep deep = new Deep(max + 1, node);
order.put(node, deep);
return deep;
}
public static class MyComparator implements Comparator<Deep> {
@Override
public int compare(Deep o1, Deep o2) {
return o1.deep == o2.deep ? 0 : (o1.deep > o2.deep ? -1 : 1);
}
}
}
?文章來源地址http://www.zghlxwxcb.cn/news/detail-469899.html
到了這里，關(guān)于17.4：圖的拓撲排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
