class SortPicture(object):
def __init__(self):
self.grap={}
self.visited={}
def addnode(self,node):
if node not in self.grap:
self.grap[node]=[]
def addNodes(self,*nodelist):
for node in nodelist:
self.addnode(node)
def addEdge(self,nodel,var=1):
u,v=nodel
if u == v:
return None
if v not in self.grap[u]:
self.grap[u].append((v,var))
def nodes(self):
return self.grap.keys()
def dsort(self,root=None):
order=[]
def compositor(node):#一条道走到黑
order.append(node)
self.visited[node]=1
for n,v in self.grap[node]:
if n not in self.visited:
compositor(n)
if root:
compositor(root)
for node in self.nodes():#把未遍历到的节点都找到挨个做顺序
if node not in self.visited:
compositor(node)
return order
for node in self.nodes():
if node not in self.visited:
compositor(node)
return order
if __name__=="__main__":
s=SortPicture()
s.addNodes(1,2,3,4,5)
s.addEdge((1,2))
s.addEdge((1,3))
s.addEdge((1,5))
s.addEdge((3,4))
print s.dsort()
s.visited={}
print s.dsort(2)
图形算法之深度优先遍历
原文：https://www.cnblogs.com/zhangtebie/p/11185819.html
