【数据结构】图—图的连通分量

叶茂林

发布于 2023-07-30 13:27:47

2230

发布于 2023-07-30 13:27:47

文章被收录于专栏：叶子的开发者社区

题目描述

输入无向图顶点信息和边信息，创建图的邻接矩阵存储结构，计算图的连通分量个数。

输入

测试次数t

每组测试数据格式如下：

第一行：顶点数顶点信息

第二行：边数

第三行开始，每行一条边信息

输出

每组测试数据输出，顶点信息和邻接矩阵信息

输出图的连通分量个数，具体输出格式见样例。

每组输出直接用空行分隔。

输入样例1

3 4 A B C D 2 A B A C 6 V1 V2 V3 V4 V5 V6 5 V1 V2 V1 V3 V2 V4 V5 V6 V3 V5 8 1 2 3 4 5 6 7 8 5 1 2 1 3 5 6 5 7 4 8

输出样例1

A B C D 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 2 V1 V2 V3 V4 V5 V6 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 2 3 4 5 6 7 8 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 3

思路分析

建立邻接矩阵，用DFS的方式遍历图，如果只需要从一个节点出发就能遍历所有节点，那么只有一个联通分量，如果需要从多个节点出发才能遍历完所有节点，那么有多个联通分量。

因此，解决方式就是，从所有节点出发DFS，每遍历一个节点就标记下来，即不会遍历已遍历的节点，那么联通分量的数目就是需要DFS节点的数目。

AC代码

#include<iostream>

using namespace std;
const int MaxLength = 100;
struct Vertex {
    int index;
    string data;
} vertex[MaxLength];

class Map {
    bool visited[MaxLength] = {false};
    int matrix[MaxLength][MaxLength] = {0};
    int vertexNumber;
    int connectedComponent = 0, tempCount;
public:
    Map() {
        connectedComponent = 0;
        cin >> vertexNumber;
        for (int i = 0; i < vertexNumber; i++) {
            cin >> vertex[i].data;
            vertex[i].index = i;
        }
        int edgeNumber;
        cin >> edgeNumber;
        for (int i = 0; i < edgeNumber; i++) {
            string tail, head;
            cin >> tail >> head;
            matrix[GetIndex(tail)][GetIndex(head)] = matrix[GetIndex(head)][GetIndex(tail)] = 1;
        }
        for (int i = 0; i < vertexNumber; i++) {
            tempCount = 0;
            if(!visited[i])
            DFS(i);
            if (tempCount>=1)
                connectedComponent++;
        }
    }

    int GetIndex(string &data) {
        for (int i = 0; i < vertexNumber; i++)
            if (vertex[i].data == data)
                return i;
    }

    void Show() {
        for (int i = 0; i < vertexNumber - 1; i++)
            cout << vertex[i].data << ' ';
        cout << vertex[vertexNumber - 1].data << endl;
        for (int i = 0; i < vertexNumber; i++) {
            for (int j = 0; j < vertexNumber - 1; j++)
                cout << matrix[i][j] << ' ';
            cout << matrix[i][vertexNumber - 1] << endl;
        }
        cout << connectedComponent << endl << endl;
    }

    void DFS(int current) {
        if (visited[current])
            return;
        visited[current] = true;
        tempCount++;
        for (int i = 0; i < vertexNumber; i++)
            if (matrix[current][i])
                DFS(i);
    }
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        Map test;
        test.Show();
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-11-16，如有侵权请联系 cloudcommunity@tencent.com 删除

存储