在图的连通性问题中,我们有时候需要判断两图是否连通同构,本文给出两种配合并查集的判断方法。

哈希

对每个顶点$V$,生成一个随机权值,当两个区域合并时将两个区域的所对应权值异或,若两个图所有区域的权值之和相同就可以认为是连通同构。

伪代码如下:

随机初始化每个并查集(此时是每个顶点)权值w[i]
初始化图权值和
def merge(u, v):    
    x, y = w[find(u)], w[find(v)]
    并查集合并(u, v)
    图权值和 -= (x + y)
    图权值和 += (x xor y)
    w[find(u)] = x xor y
    
for 每条边x in 边:
    并查集merge顶点merge(u, v)
    if 图1权值和 == 图2权值和
        两张图连通同构

队列

对两张图$G_1,G_2$,维护两个队列$Q_1,Q_2$,当其中一张图有加边操作时,在另一张图的队列里加入这条边,每次操作完成后判断队列内的边是否是连通的,若是,则弹出。当两个队列均为空的时候,则可认为两张图连通同构。

伪代码如下:

初始化Queue_1 Queue_2
for 每条边x in 边:
    并查集merge顶点<u,v>
    向另一张图的队列内压入x
    for 每条边y in Queue_1:
        if 连通:
            Queue_1.pop()
        else:
            break
            
    for 每条边y in Queue_2:
        if 连通:
            Queue_2.pop()
        else:
            break
            
    if Queue_1.empty() and Queue_2.empty():
        两张图连通同构
Last modification:March 8th, 2020 at 12:04 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏