拓扑排序是对有向无圈图的顶点的一种排序。如果存在一条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新闻热点
疑难解答
