继续代码小练习系列，理念是写出简单有趣的代码，虽然践行得有点失败的说。
* 图的广度优先搜索
代码很粗暴，可以用来走走迷宫求求无权图的最短路径。
此外把Queue换成Stack就是深度优先搜索了，递归也行。
type graph = int list*(int*int) list
let g = ([1;2;3;4],[(1,2);(2,3);(3,4);(3,1);(2,4)])
let bfs (g:graph) s =
let q = Queue.create() in
let module S = Set.Make(struct type t = int let compare = compare end) in
let set = ref (S.add s S.empty) in
let rec loop c = begin
print_int c;
List.iter
(fun (x,y)->if x==c && not (S.mem y !set) then begin
(set := (S.add y (!set))); Queue.push y q end)
(match g with _,edges->edges);
if Queue.is_empty q then () else loop (Queue.pop q);
end in loop s;;
bfs g 1;;
* 有权无向连通图的最小生成树
MinimumSpanningTrees就是用那啥Kruskal和Prim，往生成树中贪婪地添加最优边。
关于所添加的最优的边的选择，前者是图中权最小的边，后者是生成树相邻的边。
type weight=int
and vertex=int
and edge=vertex*vertex*weight
and graph=vertex list*edge list
let g = ([1;2;3;4],[(1,2,2);(2,3,3);(3,4,2);(1,3,4);(2,4,2)])
let mst_kruskal g=
let s = Hashtbl.create 0 in
let rec find_set (x:vertex) =
if x=(try (Hashtbl.find s x) with Not_found->x)
then x else find_set (Hashtbl.find s x) in
let union x y = Hashtbl.replace s (find_set x) (find_set y) in
let module P = Set.Make(
struct type t = vertex*vertex let compare = compare end) in
let a = ref P.empty in
let edges = List.sort (fun (_,_,w1) (_,_,w2)->w1-w2) (snd g) in
List.iter (fun (x,y,z)->if find_set(x)<>find_set(y) then
begin union x y; a := (P.add (x,y) (!a)) end) edges;
P.iter (fun (x,y)->begin Printf.printf "\\/(%d,%d)" x y end) !a;
;;
mst_kruskal g;;
g = ([1,2,3,4],[(1,2,2),(2,3,3),(3,4,2),(1,3,4),(2,4,2)])
def mst_prim(g,r):
k,p,q,w={r:0},{},g[0][:],dict(sum([[[(x,y),z],[(y,x),z]] for x,y,z in g[1]],[]))
while q: u = min(q,key=lambda x:k.get(x,float('+inf'))); q.remove(u)
for v in set([y for x,y,_ in g[1] if x==u]+[x for x,y,_ in g[1] if y==u]):
if v in q and w[(u,v)]<k.get(v,float('+inf')):
k[v], p[v] = w[(u,v)], u
return p
print mst_prim(g,1)
* 带权有向图的单源最短路径
Single-Source Shortest Paths可从起点按照距离动态规划。
Dijkstra可以得到从单一起点到其他所有顶点的距离及路径。
Bellman-Ford当负权边存在时路径若经过负圈则路径不存在。
g = ([1,2,3,4],[(1,2,2),(2,3,3),(3,4,2),(1,3,4),(2,4,2)])
def dijkstra(g,s,t):
q, w = g[0][:], {(x,y):z for x,y,z in g[1]}
d, p = {i:0 if i==s else float('+inf') for i in g[0]}, {}
while q:
u = min(q,key=lambda x:d[x]); q.remove(u)
if u==t:
f = lambda i:[i]+([] if i==s else f(p[i]))
return list(reversed(f(t)))
for v in {y for x,y,_ in g[1] if x==u}:
if d[v] > d[u] + w[(u,v)]:
d[v], p[v] = d[u]+w[(u,v)], u
return None
print dijkstra(g,1,4)
g2 = ([1,2,3,4],[(1,2,2),(2,3,3),(3,4,2),(3,1,-9),(2,4,2)])
g3 = ([1,2,3,4],[(1,2,2),(2,3,3),(3,4,2),(3,1,-4),(2,4,2)])
def bellman_ford(g,s,t):
d, p = {i:0 if i==s else float('+inf') for i in g[0]}, {}
for i in range(len(g[0])-1):
for u,v,w in g[1]:
if d[v] > d[u] + w:
d[v], p[v] = d[u]+w, u
if any(d[v] > d[u] + w for u,v,w in g[1]):
return None
f = lambda i:[i]+([] if i==s else f(p[i]))
return list(reversed(f(t)))
print bellman_ford(g,1,4)
print bellman_ford(g2,1,4)
print bellman_ford(g3,1,4)
好吧，咱承认是在对着书敲的代码，脑子已经不大清楚了囧。
这里的Dijkstra改改就是Prim，虽然作用不同代码结构一样。
* 任意两点间的最短路径
All-Pairs Shortest Paths，用Floyd-Warshall算法动态规划 ，一次得到图中任意两点间距离。
g = ([1,2,3,4],[(1,2,2),(2,3,3),(3,4,2),(3,1,4),(2,4,2)])
def floyd_warshall(g):
n = len(g[0])
d = [[float('+inf')]*n for i in g[0]]
t = {v:k for k,v in enumerate(g[0])}
for u,v,w in g[1]:
d[t[u]][t[v]] = min(d[t[u]][t[v]],w)
for k in range(n):
for i in range(n):
for j in range(n):
d[i][j] = min(d[i][j],d[i][k]+d[k][j])
return [(u,v,d[t[u]][t[v]]) for u in g[0] for v in g[0]]
print "\n".join("%s->%s : %s"%(u,v,w) for u,v,w in floyd_warshall(g))
* 网络流的最大流
Maximum Flow，可以通过不断添加流量到增广路上（Augmenting Path）计算。
其中增广路通过广度优先搜索在剩余网络（Residual Network）上查找得到。
g = ([1,2,3,4],[(1,2,2),(2,3,3),(3,4,2),(3,1,4),(2,4,2)])
g2 = ([1,2,3,4],[(1,2,3),(2,3,3),(3,4,2),(3,1,4),(2,4,2)])
g3 = ([1,2,3,4],[(1,2,5),(2,3,3),(3,4,2),(3,1,4),(2,4,2)])
g4 = (['s','o','p','q','r','t'],[('s','o',3),('s','p',3),('o','p',2),('o','q',3),('p','r',2),('r','t',3),('q','r',4),('q','t',2)])
def edmonds_karp(g,s,t):
w = dict(sum(([[(u,v),w],[(v,u),0]] for u,v,w in g[1]),[]))
f = {i:0 for i in w.keys()}
def bfs():
q, u, p = [], s, []
while u!=t:
q.extend(p+[e] for e in w.keys() if e[0]==u and e not in p and f[e]<w[e])
if not q: return None
p = q.pop(0)
u = p[-1][1]
return p
for p in iter(bfs,None):
c = min(w[e]-f[e] for e in p)
for u,v in p:
f[(u,v)] += c
f[(v,u)] -= c
return sum(f[e] for e in w.keys() if e[0]==s)
print edmonds_karp(g,1,4)
print edmonds_karp(g2,1,4)
print edmonds_karp(g3,1,4)
print edmonds_karp(g4,'s','t')
这里没理解错什么吧，有些细节还未考虑过，感觉有不大对劲。。
* A*搜索与拓扑排序
