拓撲排序是對有向無圈圖的頂點的一種排序。如果存在一條vi到vj的路徑，則vi排在vj前面。如果圖含有圈，則拓撲排序是不可能的。
拓撲排序的兩種排法：
一個簡單的求拓撲排序的算法是先找出任意一個沒有入邊的頂點，然后顯示出該頂點，并將它和它的邊一起從圖中刪除，對圖的其余部分應用同樣的方法。
首先，對于每個頂點計算它的入度(入邊的數量)，將所有入度為0的頂點放入到一個隊列中。當隊列不空時，刪除一個頂點v，并將與v相鄰的所有頂點的入度
減1.只要一個頂點的入度降為0.就把該頂點放入隊列中。
圖的代碼：
class Vertex(object): def __init__(self,key): self.id=key self.adj={} def addNeighbor(self,nbr,weight=0): self.adj[nbr]=weight def getNeighbors(self): return self.adj.keys() def getId(self): return self.id def getWeight(self,key): return self.adj[key]class Graph(object): def __init__(self): self.vertexlist={} self.size=0 def addVertex(self,key): vertex=Vertex(key) self.vertexlist[key]=vertex self.size+=1 return vertex def getVertex(self,key): return self.vertexlist.get(key) def __contains__(self,key): if key in self.vertexlist: return True else: return False def addEdge(self,f,t,weight=0): if f not in self.vertexlist: self.addVertex(f) if t not in self.vertexlist: self.addVertex(t) self.vertexlist[f].addNeighbor(self.vertexlist[t],weight) def getVertices(self): return self.vertexlist.keys() def __iter__(self): return iter(self.vertexlist.values())拓撲排序：
def topSort(G): top=[] queue=[] inDegree={} for v in G: inDegree[v]=0 for v in G: for w in v.getNeighbors(): inDegree[w]+=1 for v in inDegree: if inDegree[v]==0: queue.append(v) while queue: v=queue.pop(0) top.append(v) for i in v.getNeighbors(): inDegree[i]-=1 if inDegree[i]==0: queue.append(i) return top新聞熱點
疑難解答
