class Graph(object):
def __init__(self):
self.nodeNeighbors={}#使用邻街表方式表示图
self.visited={}
def addNode(self,node):#单个添加节点
if node not in self.nodeNeighbors.keys():
self.nodeNeighbors[node]=[]
def addNodes(self,*nodelist):#批量添加节点
for node in nodelist:
self.addNode(node)
def addEdge(self,edge,var=1):#使用邻街表方式添加图（有向有权图）
u,v=edge
if u==v:
return None
if v not in self.nodeNeighbors[u]:
self.nodeNeighbors[u].append([v,var])
return 1
def nodes(self):
return self.nodeNeighbors.keys()
def breathFirstSearch(self,root=None):#广度优先遍历算法
queue=[]
order=[]
def bfs():
while len(queue)>0:
node=queue.pop(0)
self.visited[node] = 1
for n,v in self.nodeNeighbors[node]:
if n not in self.visited and n not in order:
queue.append(n)
order.append(n)
if root:
queue.append(root)
order.append(root)
bfs()
for node in self.nodes():#如果节点未遍历完全重新遍历一遍节点 全部检查一遍
if node not in self.visited:
queue.append(node)
order.append(node)
bfs()
return order
if __name__=="__main__":
g=Graph()
g.addNodes(1,2,3,4,5)
g.addEdge((1,2))
g.addEdge((1,3))
g.addEdge((1,5))
g.addEdge((3,4))
print g.breathFirstSearch(3)