# 图论

2017-09-13 10:33:22来源:oschina作者:jit-hakase人点击

0
/
1   2
/ /
3   4

N = 5
G = [
[ 0, 1, 1, 0, 0 ],
[ 1, 0, 0, 1, 0 ],
[ 1, 0, 0, 1, 1 ],
[ 0, 1, 1, 0, 0 ],
[ 0, 0, 1, 0, 0 ]
]
V = [False for i in range(N)]
def dfs(n):
print(n)
for j in range(N):
if not V[j] and G[n][j]:
V[j] = True
dfs(j)
V[0] = True
dfs(0)

from queue import Queue
N = 5
G = [
[ 0, 1, 1, 0, 0 ],
[ 1, 0, 0, 1, 0 ],
[ 1, 0, 0, 1, 1 ],
[ 0, 1, 1, 0, 0 ],
[ 0, 0, 1, 0, 0 ]
]
V = [False for i in range(N)]
Q = Queue()
def bfs(n):
Q.put(n)
V[0] = Truewhile not Q.empty():
i = Q.get()
print(i)
for j in range(N):
if not V[j] and G[i][j]:
Q.put(j)
V[j] = Truebfs(0)

X = 100
N = 6
G = [
[ X, 6, 1, 5, X, X ],
[ 6, X, 5, X, 3, X ],
[ 1, 5, X, 1, 5, 4 ],
[ 5, X, 1, X, X, 2 ],
[ X, 3, 5, X, X, 6 ],
[ X, X, 4, 2, 6, X ]
]
class Edge:
def __init__(self, begin, end, lens):
self.begin, self.end = begin, end
self.lens = lens
def __len__(self):
return self.lens

# init edge info
E = []
for i in range(1, N):
E.append(Edge(0, i, G[0][i]))# set kth edge
for k in range(0, N-1):
# find shortest edge
minz, idx = X, -1
for i in range(k, N-1):
if len(E[i]) < minz:
minz = len(E[i])
idx = i
# swap edge
E[k], E[idx] = E[idx], E[k]
v = E[k].end
for i in range(k+1, N-1):
d = G[v][E[i].end]
if d < len(E[i]):
E[i].lens = d
E[i].begin = vfor item in E:
print(item.begin, item.end, len(item))

X = 100
N = 6
G = [
[ X, 6, 1, 5, X, X ],
[ 6, X, 5, X, 3, X ],
[ 1, 5, X, 1, 5, 4 ],
[ 5, X, 1, X, X, 2 ],
[ X, 3, 5, X, X, 6 ],
[ X, X, 4, 2, 6, X ]
]
class Edge:
def __init__(self, begin, end, lens):
self.begin, self.end = begin, end
self.lens = lens
def __len__(self):
return self.lens

# init edge info
E = []
for i in range(N):
for j in range(i+1, N):
if G[i][j] != X:
E.append(Edge(i, j, G[i][j]))
E.sort(key=lambda x: x.lens)P = [0 for i in range(N)]
# save next vertex
def find_set(f):
while P[f] > 0:
f = P[f]
return f
# set kth edge
cnt_edge = 0
for i in range(len(E)):# find set
n = find_set(E[i].begin)
m = find_set(E[i].end)
# if no circle
if n != m:
# add next vertex for vertex n
P[n] = m
print(E[i].begin, E[i].end, len(E[i]))
# N-1 edges finish
cnt_edge += 1
if cnt_edge == N-1:
break

INF = 400
N = 5
G = [
[ 0,10, INF,30, 100 ],
[ INF, 0,50, INF, INF ],
[ INF, INF, 0, INF,10 ],
[ INF, INF,20, 0,60 ],
[ INF, INF, INF, INF, 0 ]
]# init S & D & P
# S(Set for Vertex)
# D(Distance for vertex 0 to others)
# P(Prev vertex for vertex)
S, D, P = [], [], []
S.append(0)
for i in range(N):
D.append(G[0][i])
P.append(0)# set kth vertex
for k in range(1, N):
# select shortest edge
minz = INF
for i in range(N):
if not i in S:
if D[i] < minz:
minz = D[i]
v = i# add new vertex to S
S.append(v)
for i in range(N):
if not i in S:
if D[i] > D[v]+G[v][i]:
D[i] = D[v]+G[v][i]
P[i] = v# show shortest distance
print(D)
# show shortest path
for i in range(1, N):
prev = P[i]
print(i, end='')
while prev != 0:
print('<--%d' % prev, end='')
prev = P[prev]
print('<--%d' % 0)

0 <=> 0, 1
1 <=> 1, 2
2 <=> 0
3 <=> 2

N = 4
G = [
[ 1, 0, 1, 0 ],
[ 1, 1, 1, 0 ],
[ 0, 1, 0, 1 ],
[ 0, 0, 0, 0 ]
]
R = [-1 for i in range(N)]
def find_path(n):
for j in range(N):
if not V[j] and G[n][j]:
V[j] = True
if R[j]==(-1) or find_path(R[j]):
R[j] = n
return True
return Falsecnt = 0
for i in range(N):
V = [False for i in range(N)]
if find_path(i):
cnt += 1
print(cnt)
for i in range(N):
if R[i] != (-1):
print('%d <==> %d' % (i, R[i]))

import copy
from queue import Queue
INF = 400
N = 6
G = [
[ 0, 5, 5, 0, 0, 0],
[ 0, 0, 0, 5, 5, 0],
[ 0, 0, 0, 5, 0, 0],
[ 0, 0, 0, 0, 0, 5],
[ 0, 0, 0, 0, 0, 5],
[ 0, 0, 0, 0, 0, 0]
]
def find_path(R, P):
V = [False for i in range(N)]
Q = Queue()
Q.put(S)
V[S] = True
# BFS find_path
while not Q.empty():
top = Q.get()
for i in range(N):
if not V[i] and R[top][i]>0:
Q.put(i)
V[i] = True
P[i] = top
# if find vertex T
return V[T] == Truedef FF():
# R => Rest Flow Graph(Use Reverse R)
R = copy.deepcopy(G)
max_flow = 0
# P => Path Of Flow
P = [0 for i in range(N)]
# if has path
while find_path(R, P):
min_flow = INF
# find min flow
v = T
while v != S:
u = P[v]
min_flow = min(min_flow, R[u][v])
v = P[v]

v = T
while v != S:
u = P[v]
R[u][v] -= min_flow
# reverse path => fix prior error path
R[v][u] += min_flow
v = P[v]
max_flow += min_flow
return max_flowS, T = 0, N-1
max_flow = FF()
print(max_flow)

无相关信息