@leo9年前
2016-12-15
22:27
# Graph Algorithms
def isGraph(edge):
a=len(edge)
for i in edge:
if len(i)!=a:
return False
return True
def findMatrixMin(edge):
row=999999
col=999999
MIN=999999
for i in range(len(edge)):
for j in range(len(edge)):
if edge[i][j]<MIN and edge[i][j]!=0:
MIN=edge[i][j]
row=i+1
col=j+1
return MIN,[row,col]
#print findMatrixMin(edge)
class graph:
edge=None
v=0
visited=[]
def __init__(self,edge):
if isGraph(edge)==True:
self.edge=[]
for i in edge:
newlist=i[:]
self.edge.append(newlist)
self.v=len(edge)
self.visited=[0]*self.v
else:
raise "Error!"
def addVertex(self,contact):
if len(contact)==self.v:
for i in range(len(contact)):
self.edge[i].append(contact[i])
contact.append(0)
self.edge.append(contact)
v=v+1
else:
raise "Error!"
def delVertex(self,vnum):
# vnum=1~v
if vnum>=1 and vnum<=self.v:
self.edge.pop(vnum-1)
for i in self.edge:
i.pop(vnum-1)
else:
raise "Error!"
def viewGraph(self):
for i in self.edge:
print i
def cutEdge(self,v1,v2):
# v1,v2=1~v
self.edge[v1-1][v2-1]=0
self.edge[v2-1][v1-1]=0
def DFS(self,root):
# root=1~v
if root>=1 and root<=self.v:
self.visited[root-1]=1
print root,
for i in range(self.v):
if self.edge[root-1][i]!=0 and self.visited[i]==0:
self.DFS(i+1)
else:
raise "Error!"
def DFS_nr(self,root):
# root=1~v
# Non-recursive
stack=[]
result=[]
if root>=1 and root<=self.v:
stack.append(root)
while stack!=[]:
peek=stack.pop()
if self.visited[peek-1]==0:
result.append(peek)
self.visited[peek-1]=1
for i in range(self.v):
if self.edge[peek-1][self.v-1-i]!=0 and self.visited[self.v-1-i]==0:
stack.append(self.v-i)
else:
raise "Error!"
return result
def BFS_nr(self,root):
# root=1~v
# Non-recursive
queue=[]
result=[]
if root>=1 and root<=self.v:
queue.append(root)
self.visited[root-1]=1
while queue!=[]:
node=queue.pop(0)
result.append(node)
for i in range(self.v):
if self.edge[node-1][i]!=0 and self.visited[i]==0:
self.visited[i]=1
queue.append(i+1)
else:
raise "Error!"
return result
def Kruskal(self):
if self.v<=1:
return 0,None
def findSet(element,forest):
for i in forest:
if i!=None:
if element in i:
return i
return None
forest=[]
for i in range(self.v):
forest.append([i+1])
minST=0
minEdges=[]
while len(forest)>1:
m,[v1,v2]=findMatrixMin(self.edge)
set1=findSet(v1,forest)
set2=findSet(v2,forest)
#print m,set1,set2
if set1!=set2:
self.edge[v1-1][v2-1]=0
self.edge[v2-1][v1-1]=0
minST+=m
minEdges.append([v1,v2])
newTree=set1+set2
forest.remove(set1)
forest.remove(set2)
forest.append(newTree)
return minST,minEdges
def Prim(self):
if self.v<=1:
return 0,None
minEdges=[]
minST=0
notInTree=[]
prim=[]
for i in range(self.v):
notInTree.append(i+1)
# start with node 1
notInTree.remove(1)
prim.append(1)
while notInTree:
minEdge=[999999,999999]
minL=999999
for i in prim:
for j in notInTree:
if self.edge[i-1][j-1]<minL and self.edge[i-1][j-1]!=0:
minL=self.edge[i-1][j-1]
minEdge=[i,j]
minST+=minL
minEdges.append(minEdge)
prim.append(minEdge[1])
notInTree.remove(minEdge[1])
return minST,minEdges
def Floyd_Warshall(self):
dist=self.edge
for i in range(self.v):
for j in range(self.v):
if dist[i][j]==0:
dist[i][j]=999999
for i in range(self.v):
dist[i][i]=0
for k in range(self.v):
for i in range(self.v):
for j in range(self.v):
if dist[i][j]>dist[i][k]+dist[k][j]:
dist[i][j]=dist[i][k]+dist[k][j]
return dist
def Dijkstra(self,s):
dist=self.edge
result=[999999]*self.v
result[s-1]=0
for i in range(self.v):
for j in range(self.v):
if i!=j and dist[i][j]==0:
dist[i][j]=999999
S=[]
U=[]
for i in range(self.v):
U.append(i+1)
while U!=[]:
MIN=999999
index=0
for i in S:
for j in U:
dist[s-1][j-1]=min(dist[s-1][j-1],dist[s-1][i-1]+dist[i-1][j-1])
for j in U:
if dist[s-1][j-1]<MIN:
MIN=dist[s-1][j-1]
index=j
S.append(index)
U.remove(index)
return dist[s-1]
edge=[[0,3,2,4,0,0,0],
[3,0,4,0,0,0,6],
[2,4,0,0,0,1,0],
[4,0,0,0,5,0,0],
[0,0,0,5,0,3,0],
[0,0,1,0,3,0,2],
[0,6,0,0,0,2,0]]
# 0 3 2 4 0 0 0
# 3 0 4 0 0 0 6
# 2 4 0 0 0 0 1
# 4 0 0 0 5 0 0
# 0 0 0 5 0 3 0
# 0 0 1 0 3 0 2
# 0 6 0 0 0 2 0
Graph=graph(edge)
print Graph.DFS_nr(1)
Graph=graph(edge)
print Graph.BFS_nr(1)
Graph=graph(edge)
minST,minEdges=Graph.Kruskal()
print "Kruskal:",minEdges," Min:",minST
Graph=graph(edge)
minST,minEdges=Graph.Prim()
print "Prim:",minEdges," Min:",minST
Graph=graph(edge)
dist=Graph.Floyd_Warshall()
for i in dist:
print i
Graph=graph(edge)
print "Dijstrak(1):",Graph.Dijkstra(1)
Python 2.7.10 (default, Jul 14 2015, 19:46:27)
[GCC 4.8.2] on linux
[1, 2, 3, 6, 5, 4, 7]
[1, 2, 3, 4, 7, 6, 5]
Kruskal: [[3, 6], [1, 3], [6, 7], [1, 2], [5, 6], [1, 4]] Min: 15
Prim: [[1, 3], [3, 6], [6, 7], [1, 2], [6, 5], [1, 4]] Min: 15
[0, 3, 2, 4, 6, 3, 5]
[3, 0, 4, 7, 8, 5, 6]
[2, 4, 0, 6, 4, 1, 3]
[4, 7, 6, 0, 5, 7, 9]
[6, 8, 4, 5, 0, 3, 5]
[3, 5, 1, 7, 3, 0, 2]
[5, 6, 3, 9, 5, 2, 0]
Dijstrak(1): [0, 3, 2, 4, 6, 3, 5]