Graph

基础概念¶

简单路径

路径上的顶点都不相同

广度优先搜索¶

给定图G=(V, E)和一个源结点s，广度优先搜索计算从s到每个可以到达的结点的距离，同时生成一棵”广度优先搜索树“

结点颜色分为

白：还没有进入队列的点所有结点一开始涂白，表示还没有被发现的节点
黑：已经出队列的点，如果 $(u, v) \in E$ ，而且u是黑色，那么v一定已经被发现，即为灰色或黑色
灰：在队列中的点，灰色结点相连的点里，可能还会有白色结点

然后将源节点放入队列，

BFS(G, s)
    // Initialize
    for each vertex u in G.V - {s}
        u.color = WHITE
        u.d = INT_MAX
        u.prev = NULL
    // Add source node into queue
    s.color = GRAY
    s.d = 0
    s.prev = NULL
    Q = queue()
    ENQUEUE(Q, s)
    while len(Q) != 0
        u = DEQUEUE(Q)
        for each v in G.Adj[u]
            if v.color == WHITE
                v.color = GRAY
                v.d = u.d + 1
                v.prev = u
                ENQUEUE(Q, v)
        u.color = BLACK

复杂度¶

对于队列的操作，每个结点入队和出队最多为一次，总时间为O(V)

扫描临接链表时，每个点在出队时扫描一遍，总时间为O(E)

总复杂度为O(V+E)

深度优先搜索¶

深度有限搜索的前驱子图形成一个由多棵深度优先树构成的深度优先森林，因为搜索可能从多个源结点重复进行，设图 $G_\pi=(V,E_\pi)$ ，其中 $E_\pi={(v.\pi, v):v \in V 且 v.\pi \ne NIL}$

每个节点有两个时间，v.d记录结点v第一次被发现的时间(涂上灰色)，第二个时间v.f记录完成搜索v的邻接链表的时间(涂上黑色)

DFS_VISIT(G, u)
    time = time + 1
    u.d = time
    u.color = GRAY
    for each v in G.adj[u]
        if v.color == WHITE
            v.prev = u
            DFS_VISIT(G, v)
    u.color = BLACK
    time = time + 1
    u.f = time

DFS(G)
    for each vertex u in G.V
        u.color = WHITE
        u.prev = NULL
    time = 0
    for each vertex u in G.V
        if u.color == WHITE
            DFS-VISIT(G, u)

复杂度¶

O(V+E)

边(u, v)分类¶

树边: 即深度优先森林 $G_\pi$ 里面的边
后向边: 节点u连接到其在树中一个祖先节点v的边，发现v时为灰色
前向边: u连接到其在深度优先树中一个后代节点v，发现v时为黑色
横向边 (cross edge): 其他所有的边，u和v没有祖先关系，发现v时为黑色

判别方式

树边: 发现v时为白色
后向边: 发现v时为灰色
前向边: 发现v时为黑色，同时 u.d < v.d < v.f < u.f
横向边: 发现v时为黑色，同时 v.d < v.f < u.d < u.f

推论

有向图无环的充要条件是搜索过程中没有后向边的产生

习题¶

CLRS 22.3-13 对于有向图G=(V,E)来说，如果任意两点间最多只有一条简单路径，则图G是单连通图。给出一个有效算法来判断一个有向图是否是单向连通图

从u到v存在两条路径，则可以扩展成从入度为0的点到一个入度不为0的点存在两条路径，因为u总有个入度是0的祖先

那么对G进行拓扑排序，之后按顺序开始访问，更新每个点的入度为0的祖先，如果向点v添加祖先u时发现已经添加过，那么说明存在两条路径，不是单连通图

以上过程可以进行剪枝，首先如果有后向边存在，即图G存在环，一定不是单连通图，如果有前向边存在，也不是单连通图，只有跨边存在的情况，才需要进行上述操作

拓扑排序¶

对一个有向无环图进行排序，按照v.f从大到小排序，将这些点按顺序排在水平线上，则所有有向边都从左指向右

这里以leetcode 210为例，说明一下代码

正常深搜，然后标记颜色，当搜到为1的颜色时，说明出现环路

搜索完，颜色标记为2，同时逆序存储拓扑排序结果

bool dfs(const vector<vector<int>>& graph, vector<int>& color, vector<int>& result, int node, int& rank) {
    color[node] = 1;
    for (int v : graph[node]) {
        if (color[v] == 0) {
            if (!dfs(graph, color, result, v, rank)) return false;
        }
        else if (color[v] == 1) return false; // 是否有环
    }
    color[node] = 2;
    result[rank - 1] = node; rank --; // 输出排序
    return true;
}