拓扑排序是对有向无圈图的顶点的一种排序。如果存在一条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
您可以选择一种方式赞助本站
支付宝扫一扫赞助
微信钱包扫描赞助
赏