本文为图算法的python实现。github
#!/usr/bin/env python
#coding=utf-8
def getWeight(V,E,u,v):
if E.has_key(u):
for i in E[u]:
if i[1] is v:
return i[2]
return 100000
def BFS(V,E,start):
color=[-1]len(V)
depth=[0]len(V)
queue=[]
queue.append(start)
color[start]=0
while len(queue)>0:
p=queue.pop(0)
print “ “*depth[p],
print V[p]
if E.has_key(V[p]):
for j in E[V[p]]:
if color[V.index(j[1])]==-1:
queue.append(V.index(j[1]))
depth[V.index(j[1])]=depth[p]+1
color[V.index(j[1])]=0
color[p]=1
return depth
time=0
def DFS_start(V,E):
global time
color=[-1]len(V)
startTime=[0]len(V)
finishTime=[0]*len(V)
for i in V:
if color[V.index(i)]==-1:
DFS(V,E,color,startTime,finishTime,i)
return startTime,finishTime
def DFS(V,E,color,startTime,finishTime,i):
global time
time=time+1
startTime[V.index(i)]=time
print “ “*startTime[V.index(i)],
print i
color[V.index(i)]=0
if E.has_key(i):
for m in E[i]:
if color[V.index(m[1])]==-1:
DFS(V,E,color,startTime,finishTime,m[1])
color[i]=1
time=time+1
finishTime[V.index(i)]=time
def TopologicalSort(V,E):
indegree=[0]*len(V)
visited=[]
for i in E:
for j in E[i]:
indegree[V.index(j[1])]=indegree[V.index(j[1])]+1
while 0 in indegree:
pos=indegree.index(0)
visited.append(V[pos])
if E.has_key(V[pos]):
for j in E[V[pos]]:
indegree[j[1]]=indegree[j[1]]-1
indegree[pos]=-1
if len(visited)0:
current=Queue.pop(0)
flag=False
if E.has_key(V[current]):
for i in E[V[current]]:
if color[V.index(i[1])] is not 1:
flag=True
if color[V.index(i[1])] is not -1:
Queue.append(V.index(i[1]))
color[V.index(i[1])]=-1
break
if not flag:
visited.insert(0,V[current])
color[current]=1
else:
Queue.append(V[current])
color[current]=-1
return visited
def Kruskal(V,E):
visited=[]
visitedpoints=[]
notvisited=[]
for m in E:
for n in E[m]:
notvisited.append(n)
while len(visited)0:
temp=(0,0,65535)
for j in notvisited:
if j[2]0:
temp=(0,0,65535)
for j in notvisited:
flag=False
if len(visited)==0:
flag=True
n=visitedpoints.count(j[0])+visitedpoints.count(j[1])
if n==1:
flag=True
if j[2]0:
if E.has_key(int(m)):
E[int(m)].append((int(m),int(n),int(s)))
else:
E[int(m)]=[]
E[int(m)].append((int(m),int(n),int(s)))
b=raw_input()
print “\nthe graph you inputed is:”
print V
print E
print “\nBellman_Ford:”
path,length=Bellman_Ford(V,E,0)
for i in range(0,len(V)):
p=[]
t=i
print str(t)+”:”,
while t is not 0:
p.append(V[t])
t=path[t]
print 0,
while len(p)>0:
print p.pop(),
print “\t”+str(length[i])
print “\nFloyd:”
print Floyd(V,E)
print “\nBFS:”
BFS(V,E,0)
print “\nDFS:”
firstTime,lastTime=DFS_start(V,E)
for i in range(0,len(V)):
print “%d,%4d,%4d”%(V[i],firstTime[i],lastTime[i])
print “ToplogicalSort:”
ans=TopologicalSort(V,E)
print ans
if len(ans)>0:
print “TopologicalSort:dfs”
print TopologicalSort_dfs(V,E)
print "\\nPrim:"
print Prim(V,E)
print "\\nKruskal:"
print Kruskal(V,E)
if __name__==”__main__“:
main()