FB4-求无向图的连通分量个数¶

[[#并查集方式]]

代码实现¶

DFS¶

C
/**
 * 求无向图的连通分量个数
 * 
 * 定义：连通分量是无向图中极大连通子图的个数
 * 在无向图中，如果任意两个顶点之间都存在路径，则称该图为连通图
 * 否则，该图由多个连通分量组成
 * 
 * 算法思想：
 * 1. 遍历所有顶点
 * 2. 对于每个未被访问的顶点，进行一次DFS/BFS遍历
 * 3. 每次完整的DFS/BFS遍历对应一个连通分量
 * 4. 统计遍历次数即为连通分量个数
 * 
 * 核心思路：
 * - 利用图遍历的特性：一次遍历可以访问一个连通分量中的所有顶点
 * - 通过访问标记避免重复访问
 * - 每发现一个未访问顶点，就意味着发现了一个新的连通分量
 * 
 * @param G 无向图的邻接表表示
 * @return 连通分量的个数
 */
int countConnectedComponents(Graph G) {
    // 全局访问标记数组，记录所有顶点的访问状态
    int visit[maxsize] = {0};

    // 连通分量计数器
    int count = 0;

    // 遍历所有顶点
    for (int i = 0; i < G.numver; ++i) {
        // 如果顶点i未被访问，说明发现了一个新的连通分量
        if (visit[i] == 0) {
            // 从顶点i开始进行DFS遍历，访问整个连通分量
            DFS(G, i, visit);
            // 连通分量计数加1
            count++;
        }
    }

    // 返回连通分量总数
    return count;
}

/**
 * 图的深度优先搜索遍历（辅助函数）
 * 
 * @param G 图的邻接表表示
 * @param v 起始顶点
 * @param visit 访问标记数组（全局共享）
 */
void DFS(Graph G, int v, int visit[]) {
    // 标记当前顶点为已访问
    visit[v] = 1;

    // 遍历当前顶点的所有邻接顶点
    Node p = G.adjlist[v].firstarc;
    for (; p != NULL; p = p->nextarc) {
        // 如果邻接顶点未被访问，则递归访问
        if (visit[p->adjvex] == 0) {
            DFS(G, p->adjvex, visit);
        }
    }
}

BFS¶

C
/**
 * 使用BFS实现的连通分量计算
 * 
 * 优点：在某些情况下BFS可能有更好的性能表现
 */
int countConnectedComponents_BFS(Graph G) {
    int visit[maxsize] = {0};
    int count = 0;

    for (int i = 0; i < G.numver; ++i) {
        if (visit[i] == 0) {
            // 使用BFS遍历整个连通分量
            BFS(G, i, visit);
            count++;
        }
    }

    return count;
}

/**
 * BFS辅助函数
 */
void BFS(Graph G, int v, int visit[]) {
    int que[maxsize];
    int front = 0, rear = 0;

    // 起始顶点入队并标记
    que[rear++] = v;
    visit[v] = 1;

    // BFS遍历
    while (front != rear) {
        v = que[front++];

        Node p = G.adjlist[v].firstarc;
        for (; p != NULL; p = p->nextarc) {
            if (visit[p->adjvex] == 0) {
                visit[p->adjvex] = 1;
                que[rear++] = p->adjvex;
            }
        }
    }
}

并查集方式¶

C
/**
 * 使用并查集（Union-Find）计算图的连通分量数量
 * 
 * 算法思路：
 * 1. 初始化并查集，每个顶点初始时独立成一个集合。
 * 2. 遍历图中每一条边 (u, v)，将两个端点合并到同一集合。
 *    - 由于是无向图，每条边只需处理一次即可保证连通性正确合并。
 * 3. 最终统计并查集中根节点的个数，即为连通分量的数量。
 * 
 * 时间复杂度：O(E × α(V))，其中 α 是阿克曼函数的反函数，实际中接近常数。
 * 空间复杂度：O(V)，来自并查集的 parent 数组。
 * 
 * 优点：
 * - 支持动态添加边后实时查询连通性。
 * - 路径压缩与按大小合并使操作高效。
 * 
 * @param G 图的邻接表表示
 * @return 连通分量的个数
 */
int countConnectedComponents_UnionFind(Graph G) {
    // 步骤1：初始化并查集，每个顶点自成一个集合
    init();  // 将 parent[i] 初始化为 -1

    // 步骤2：遍历每个顶点及其邻接边，合并相连的顶点
    for (int i = 0; i < G.numver; i++) {
        Node* p = G.adjlist[i].firstarc;  // 获取顶点 i 的第一条边
        while (p != NULL) {
            // 将顶点 i 和其邻接点 p->adjvex 合并到同一集合
            // 注意：无向图中边 (i, p->adjvex) 只需处理一次
            unionSet(i, p->adjvex);
            p = p->nextarc;  // 移动到下一条边
        }
    }

    // 步骤3：统计当前并查集中根节点的数量，即连通分量个数
    return countSet();
}

C
int parent[MAX_SIZE];  // parent[i] < 0 表示 i 是根，其绝对值为集合大小

/**
 * 初始化：每个元素自成一个集合
 */
void init() {
    for (int i = 0; i < MAX_SIZE; ++i) {
        parent[i] = -1;  // 初始大小为 1（用 -1 表示）
    }
}

/**
 * 查找元素 x 的根，并进行路径压缩
 * @param x 元素下标
 * @return 根节点下标
 */
int find(int x) {
    int root = x;
    // 找根
    while (parent[root] >= 0) {
        root = parent[root];
    }
    // 路径压缩：所有节点直接连到根
    while (x != root) {
        int temp = parent[x];
        parent[x] = root;
        x = temp;
    }
    return root;
}

/**
 * 合并元素 x 和 y 所在的集合（按大小合并）
 * @param x 元素 x
 * @param y 元素 y
 */
void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if (rootX == rootY) return;  // 已在同一集合，无需合并

    // 按大小合并：小树合并到大树
    if (parent[rootY] > parent[rootX]) {
        // rootY 的树更小（负得少），挂到 rootX 下
        parent[rootX] += parent[rootY];  // 更新大小
        parent[rootY] = rootX;
    } else {
        // rootX 更小或相等，挂到 rootY 下
        parent[rootY] += parent[rootX];
        parent[rootX] = rootY;
    }
}

/**
 * 统计当前集合的个数（即根节点的个数）
 * @return 集合数量
 */
int countSet() {
    int count = 0;
    for (int i = 0; i < MAX_SIZE; ++i) {
        if (parent[i] < 0) {  // 根节点的标志
            count++;
        }
    }
    return count;
}

复杂度分析¶

时间复杂度：O(V + E)¶

V: 顶点数，E: 边数
每个顶点被访问一次：O(V)
每条边被检查一次：O(E)
总时间复杂度：O(V + E)

注意：原代码注释中的O(V×(V+E))是错误的，正确的时间复杂度应该是O(V+E)

空间复杂度：O(V)¶

visit[]数组：O(V)
DFS递归调用栈：最坏情况O(V)
总空间复杂度：O(V)

图解说明¶

Text Only

示例无向图结构（包含3个连通分量）：
连通分量1: 0-1-2    连通分量2: 3-4    连通分量3: 5
    0 ── 1          3 ── 4            5
    │
    2

执行过程：

初始状态：
visit: [0,0,0,0,0,0]
count: 0

检查顶点0：
visit[0] = 0 → 发现新连通分量
DFS(0): 访问 0→1→2
visit: [1,1,1,0,0,0]
count: 1

检查顶点1,2：
visit[1] = 1, visit[2] = 1 → 已访问，跳过

检查顶点3：
visit[3] = 0 → 发现新连通分量
DFS(3): 访问 3→4
visit: [1,1,1,1,1,0]
count: 2

检查顶点4：
visit[4] = 1 → 已访问，跳过

检查顶点5：
visit[5] = 0 → 发现新连通分量
DFS(5): 访问 5
visit: [1,1,1,1,1,1]
count: 3

最终结果：连通分量个数为3

相关知识点延伸¶

1. 连通分量的应用场景¶

C
// 社交网络分析
int analyzeSocialNetwork(UserGraph G) {
    int components = countConnectedComponents(G);
    if (components == 1) {
        printf("社交网络是连通的\n");
    } else {
        printf("社交网络包含%d个孤立群体\n", components);
    }
    return components;
}

// 计算机网络连通性检查
int checkNetworkConnectivity(NetworkGraph G) {
    return countConnectedComponents(G);
}

// 岛屿计数问题（二维网格）
int countIslands(char grid[][MAX], int rows, int cols) {
    // 将二维网格转换为图，然后计算连通分量
    Graph G = convertGridToGraph(grid, rows, cols);
    return countConnectedComponents(G);
}

2. 特殊图类型的处理¶

C
// 树的连通分量（总是1）
int countTreeComponents(Graph tree) {
    return 1;  // 树本身就是连通的
}

// 完全图的连通分量（总是1）
int countCompleteGraphComponents(Graph completeGraph) {
    return 1;  // 完全图是连通的
}

// 空图的连通分量
int countEmptyGraphComponents(Graph emptyGraph) {
    return emptyGraph.numver;  // 每个孤立顶点是一个连通分量
}

3. 连通分量的进一步分析¶

C
// 找出最大的连通分量
int findLargestComponent(Graph G) {
    int visit[maxsize] = {0};
    int maxSize = 0;

    for (int i = 0; i < G.numver; ++i) {
        if (visit[i] == 0) {
            int componentSize = 0;
            DFS_Count(G, i, visit, &componentSize);
            if (componentSize > maxSize) {
                maxSize = componentSize;
            }
        }
    }

    return maxSize;
}

// 带计数功能的DFS
void DFS_Count(Graph G, int v, int visit[], int* count) {
    visit[v] = 1;
    (*count)++;

    Node p = G.adjlist[v].firstarc;
    for (; p != NULL; p = p->nextarc) {
        if (visit[p->adjvex] == 0) {
            DFS_Count(G, p->adjvex, visit, count);
        }
    }
}

4. 动态连通性问题¶

C
// 支持动态添加边的连通分量计算
typedef struct {
    Graph G;
    int componentCount;
    UnionFind uf;
} DynamicConnectivity;

void initDynamicConnectivity(DynamicConnectivity* dc, int vertexCount) {
    dc->componentCount = vertexCount;
    initUnionFind(&dc->uf, vertexCount);
}

void addEdge(DynamicConnectivity* dc, int u, int v) {
    if (unionSets(&dc->uf, u, v)) {
        dc->componentCount--;  // 合并了两个不同的连通分量
    }
}

int getComponentCount(DynamicConnectivity* dc) {
    return dc->componentCount;
}

5. 错误处理和边界情况¶

C
// 完整的错误处理版本
int countConnectedComponents_Robust(Graph G) {
    // 边界情况处理
    if (G.numver <= 0) {
        return 0;
    }

    if (G.numver == 1) {
        return 1;
    }

    // 正常处理
    int visit[maxsize] = {0};
    int count = 0;

    for (int i = 0; i < G.numver; ++i) {
        if (visit[i] == 0) {
            DFS(G, i, visit);
            count++;
        }
    }

    return count;
}

连通分量是图论中最基础也是最重要的概念之一，广泛应用于网络分析、社交计算、图像处理等领域。理解这个算法对于掌握图论知识具有重要意义。