代码小练习三 - 图

继续代码小练习系列，理念是写出简单有趣的代码，虽然践行得有点失败的说。



* 图的广度优先搜索


代码很粗暴，可以用来走走迷宫求求无权图的最短路径。
此外把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*搜索与拓扑排序