jit-hakase

图 论

图的遍历

1   2   \ /
3   4

深度优先搜索(DFS)

``````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)
``````

广度优先搜索(BFS)

``````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] = True

while 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] = True

bfs(0)
``````

最小生成树

普里姆(prim)算法

``````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 = v

for item in E:
print(item.begin, item.end, len(item))
``````

克鲁斯卡尔(kruskal)算法

``````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
``````

最短路径

迪杰斯特拉(dijkstra)算法

``````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)
``````

网络流

匈牙利(Hungary)算法

``````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 False

cnt = 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]))
``````

增广路(Ford-Fulkerson)算法

``````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] == True

def 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_flow

S, T = 0, N-1

max_flow = FF()

print(max_flow)
``````

jit-hakase

【转】关于邦迪（J.A. Bondy）的图论教材

http://bbs.math.org.cn/viewthread.php?tid=360 我想很多学习图论的人都知道J.A. Bondy和U.S.R. Murty著的《Graph Theory with Application》(Elsevier,1976)是图论教材中的经典，时至今日，...

MtrS
2017/03/09
171
0
[概念辨析 系列 之四] 树的概念

2017/02/09
0
0

2017/10/20
0
0
PJ考试可能会用到的数学思维题选讲-自学教程-自学笔记

PJ考试可能会用到的数学思维题选讲 by PleiadesAntares 是学弟学妹的讲义——然后一部分题目是我弄的一部分来源于洛谷用户@ 普及组的一些数学思维题，所以可能有点菜咯别怪我 OI中的数学题—...

2018/10/02
0
0
2017蓝桥杯模拟赛

hahohehehe
2017/04/03
0
0

Spring Security 自定义登录认证（二）

33分钟前
3
0
php yield关键字以及协程的实现

php的yield是在php5.5版本就出来了,而在初级php界却很少有人提起,我就说说个人对php yield的理解 Iterator接口 在php中,除了数组,对象可以被foreach遍历之外,还有另外一种特殊对象,也就是继承...

46分钟前
4
0
servlet请求和响应的过程

46分钟前
4
0
golang 1.13 errors 包来了，不用写“err 气功波”代码

guonaihong
50分钟前
28
0

Alex_Java
51分钟前
5
0