图算法

基本的图算法

图的表示

邻接链表

对图$G=(V,E)$，其邻接链表表示有一个包含$|V|$条链表的数组Adj所构成，每个结点都有一条链表。对于每个结点$u \in V$，邻接链表Adj[u]包含所有与结点u之间右边相连的结点v，即Adj[u]包含图中与u邻接的结点

如果G是有向图，所有的邻接链表的长度之和为$|E|$；如果G是无向图，所有邻接链表的长度之和为$2|E|$
空间复杂度有：不管是有向图还是无向图，邻接链表表示的空间存储需求都是$\Theta (V+E)$
缺点：无法快速判断一条边(u,v)是否是图中的一条边，唯一的办法是在邻接链表Adj[u]里搜索结点v

邻接矩阵

对图中结点进行编号$1,2,…,|V|$（任意的），邻接矩阵表示由一个$|V| \times |V|$的矩阵$A=(a_{ij})$予以表示：

$a_{ij}= \begin{cases} 1, & \text {若 $(i,j) \in E$} \\0, & \text{其他} \end{cases}$

空间复杂度：不管一个图有多少边，都需要空间$\Theta (V^2)$
特点：
- 无向图的邻接矩阵是一个对称矩阵（$A=A^T$)，可以只存对角线及以上部分邻接矩阵；
- 表示法更为简单，在图规模比较小的时候，倾向采用邻接矩阵表示
- 每个记录只需要1位的空间

广度优先搜索

给定图$G=(V,E)$和一个可以识别的源结点s，广度优先搜索对图G中的边进行系统性的探索来发现可以从源结点s到达的所有结点。该算法能够计算源结点s到每个可以到达的结点的距离（最少边数），同时生成一棵广度优先树。

以源结点s为根结点，包含所有可以从s到达的结点。对于每个从源结点s可以到达的v，在广度优先搜索树里从结点s到结点v的简单路径对应的就是图G中从s到v的“最短路径”，即包含最少边数的路径。该算法可用于有向图，也可用于无向图。

广度优先搜索的结果可能依赖于每个节点的邻接结点的访问顺序：广度优先树可能会不一样，但本算法所计算出来的距离d是一样的

from collections import deque

"""基本的图算法：广度优先搜索"""
def BFS(graph,s):
    color={}
    d={}
    p={}

    """初始化所有结点"""
    for node in graph:
        color[node]=0       # whilte is 0,gray is 1,black is 2
        d[node]=float('inf')
        p[node]=None
    color[s]=1
    d[s]=0
    p[s]=None

    queue=deque()
    queue.append(s)

    while queue:
        u=queue.popleft()
        for v in graph[u]:
            if color[v]==0:
                color[v]=1
                d[v]=d[u]+1
                p[v]=u
                queue.append(v)
        color[u]=2
    return d,p


def print_path(graph,s,v,p):
    if v==s:
        print(s,end=' ')
    elif p[v]==None:
        print('no path from ',s,'to',v)
    else:
        print_path(graph,s,p[v],p)
        print(v,end=' ')

if __name__=='__main__':
    graph={
        'v' : {'r'},
        'r' : {'v', 's'},
        's' : {'r', 'w'},
        'w' : {'s', 'x', 't'},
        'x' : {'w', 't', 'u', 'y'},
        't' : {'w', 'x', 'u'},
        'u' : {'t', 'x', 'y'},
        'y' : {'x', 'u'}
    }

    d,p=BFS(graph,'v')
    print('The shortest distance between s and v:\t',d)
    print('The parent of the nodes:\t',p)
    print_path(graph,'v','u',p)

复杂度分析

测试时可以确保每个结点的入队次数最多为一次，因而出队最多一次，出队和入队的时间均为$O(1)$，因而队列进行操作的总时间时$O(V)$
一个结点出队的时候才对该结点的邻接链表进行扫描，所以每个链表最多扫描一次。由于连接链表长度之和是$\Theta (E)$，用于扫描邻接链表的总时间为$O(E)$
初始化的成本是$O(V)$

因此，广度优先搜索的总运行时间为$O(V+E)$，是图G的邻接链表大小的一个线性函数

最短路径

从源结点s到结点v的最短路径距离$\delta (s,v)$：从结点s到结点v之间所有路径里面最少的边数。
从源结点s到结点v的最短路径：从结点s到结点v的长度$\delta (s,v)$

给定$G=(V,E)$，G是一个有向图或无向图，设$s \in V$是任意一个结点，则对任意边$(u,v) \in E，\delta (s,v) \leq \delta(s,u)+1$
设$G=(V,E)$为一个有向图或无向图，假设BFS一给定结点$s\in V$作为源结点在图G上运行。那么在BFS终结时，对于每个节点$v \in V$，BFS所计算出的v.d满足$v.d \leq \delta(s,v)$
假定BFS在图$G=(V,E)$上运行的过程中，队列Q包含的结点$\langle v_1,v_2,…,v_r \rangle
$，这里$v_1$是队列的头，$v_r$是队列的尾，那么$v_r.d \leq v_1+1$，并且对$i=1,…,i-1，v_i.d \leq v_{i+1}.d$
假定执行BFS时，结点$v_i$和结点$v_j$都加入队列Q里，并且$v_i$在$v_j$前面入队，则在$v_j$入队时，有$v_i.d \leq v_j.d$
（广度优先搜索的正确性）设$G=(V,E)$为一个有向图或无向图，有假设BFS以s为源结点在图G上进行。那么算法执行过程中，BFS将发现从源结点s可以到达的所有节点$v \in V$，并在算法结束时，对所有的$v \in V,v.d=\delta(s,v)$。并且，对于任意可以从s到达的结点$v \neq s$，从源结点s到结点v的其中一条最短路径为从s到达$v.\pi$的最短路径加上边$(v.\pi,v)

广度优先树

过程BFS在对图进行搜索的过程中将创建一棵广度优先树。该树对应的是$\pi$属性。对图$G=(V,E)$的前驱子图$G_\pi=(V_\pi,E_\pi)$，其中$V_\pi={v \in V:v.\pi\neq NIL}\bigcup{s}，E={(v.\pi,v):v\in V_\pi-{s}}$。前驱子图是一棵优先树，树边$|E_\pi|=|V_\pi|-1$。

深度优先搜索

深度优先搜索总是对最近才发现的结点v的出发边进行搜索，知道该结点的所有出发边都被发现为止。一旦结点v的所有出发边都被发现，搜索则“回溯”到v的前驱结点（v是经过该结点才被发现），来搜索该前驱结点的出发边。该过程一直持续到从源结点可以到达的所有结点都被发现为止。如果还有未发现的结点，则深度优先搜索将从这些未被发现的结点中任选一个作为新的源结点，并重复同样的搜索过程。该算法重复整个过程，直到图中所有结点都被发现。

深度优先搜索的前驱子图形成一个有多棵深度优先搜索树构成的深度优先深林。森林$E_\pi$中的边仍称为树边。

创建一个深度优先搜索森林
在每个结点v有两个时间戳：第一个时间戳v.d记录结点v第一次被 发现的时间（涂上灰色的时候），第二个时间戳v.f记录的是搜索完成对v的邻接链表扫描的时间（结束时间）（涂上黑色的时候）。这些时间戳提供了图结构的重要信息，通常能够有助于推断深度优先搜索算法的行为。

深度优先搜索中也是对结点进行染色来指明结点的状态。每个节点的初始颜色都是白色，再借点被发现后变成灰色，在其邻接链表被扫描完成后变为黑色。该方法保证每个结点仅在一棵深度优先树中出现，因此，所有的深度优先树是不相交的。

深度优先搜索的性质

深度优先搜索生成的前驱子图$G_\pi$形成一个由多棵树构成的森林，因为搜索可能从多个源结点重复进行
结点的发现时间和结束时间具有所谓的括号化结构
可以通过搜索对数如图G的边进行分类

定理及推论

括号化定理：在对有向图或无向图$G=(V,E)$进行任意深度优先搜索中，对于任意两个结点u和v来说，下面三种情况只有一种成立：

区间[u.d,u.f]和[v.d,v.f]完全分离，在深度优先森林中，结点u不是结点v的后代，结点v也不是结点u的后代
区间[u.d,u.f]完全包含在[v.d,v.f]内，在深度优先森林中，结点u是结点v的后代
区间[v.d,v.f]完全包含在[u.d,u.f]内，在深度优先森林中，结点v是结点u的后代

后代区间嵌套：在有向或者无向图的深度优先搜索中，结点v是结点u的真后代当且仅当$u.d<v.d<v.f<u.f$

白色路径定理：在有向或者无向图的深度优先森林中，结点v是接待你u的后代，当且仅当在发现u的时间u.d，存在一条从结点u到结点v的全部白色结点所构成的路径。

算法导论基本的图算法

图算法