Поиск компонент связности в графе

Question

Задача: Граф задан матрицей смежности, необходимо вывести количество компонентов связности графа, а далее в следующих строчках вывести размер и в порядке возрастания сам компонент связности.

Вопрос: Для поиска компонент связности в графах использую поиск в ширину, но как можно модифицировать данный алгоритм, для выполнения условия? :

а далее в следующих строчках вывести размер компонента связности и в порядке возрастания сам компонент связности.

Моя реализация: Я сумел реализовать подсчёт компонентов связности графа, но затрудняюсь в выводе размера и самого компонента связности.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;


int main(){
    int N;
    cin >> N;
    int current = 0;

    vector<vector<int>> matrix (N, vector<int>(N));
    for (int i = 0; i < matrix.size(); i ++){
        for (int j = 0; j < matrix.size(); j ++){
            cin >> matrix[i][j];
        }
    }

    vector<int> path(N, -1);
    queue<int> queueForVertex;
    for (int i = 0; i < N; i ++){
        if (path[i] != -1){
            continue;
        }
        queueForVertex.push(i);
        while (!queueForVertex.empty()){
            int vert = queueForVertex.front();
            queueForVertex.pop();
            if (path[vert] != -1){
                continue;
            }

            path[vert] = current;
            for (int j = 0; j < N; j ++){
                if (matrix[i][j] != 0 and path[j] == -1){
                    queueForVertex.push(j);
                }
            }
        }
        current ++;
    }
}

Answer 1

Не смогу точно помочь по твоему коду. Приложу лишь свой код вывода компонент связности. Думаю, сможешь приделать счетчик или адаптировать под свой. Про размерность не до конца понял, нужно количество вершин и ребер у каждой компоненты?

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/// <summary>
/// Обход графа в глубину
/// </summary>
/// <param name="graph"> граф представленный списком смежности </param>
/// <param name="v"> текущая вершина </param>
/// <param name="visited"> список помеченных вершин, в которых побывали </param>
void dfs(vector<vector<int>> &graph, int v, vector <int> &visited, vector<int> &component)
{
    visited[v] = 1; //отмечаем что были в вершине
    component.push_back(v); //добавляем вершину в компоненту

    for (int to : graph[v]) // перемещаемся по списку вершины
        if (!visited[to]) // если в вершине не были
            dfs(graph, to, visited, component); // двигаемся дальше
}

void findComps(vector<vector<int>> &graph, int v, vector<int> &visited, vector<int> &component)
{
    for (int i = 0; i < v; ++i) // обнуляем все отметки
        visited[i] = 0;
    for (int i = 0; i < v; ++i) //двигаемся по вершинам от 0
        if (!visited[i]) // если не были в вершине
        {
            component.clear(); // очищаем вектор компоненты
            dfs(graph, i, visited, component); // обход графа, начиня с первой вершины

            sort(component.begin(), component.end()); // сортируем вершины компоненты
            cout << "Component:" << endl; //вывод компонента
            for (int i = 0; i < component.size(); i++) //выводим все вершины компоненты
            {
                for (int j = 0; j < graph[component[i]].size(); j++) //выводим все смежные вершины и у текущей
                    cout << graph[component[i]][j] << " ";
                cout << endl;
            }
        }
}

int main()
{
    int vertexCount, edgeCount; //количество вершин и количество ребер
    vector<vector<int>> graph(vertexCount); //граф в списке смежности размером количество вершин
    vector<int> visited(vertexCount); //массив посещений размером количество вершин
    vector<int> component; //компонента, хранит вершины входящие в компоненту

    cout << "Enter count vertex and edge:\n";
    cin >> vertexCount >> edgeCount;

    for (int i = 0; i < edgeCount; i++) // считывание графа список смежности
    {
        int a, b;
        cout << "Enter vertex of edge:\n";
        cin >> a >> b;

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    findComps(graph, vertexCount, visited, component);
}

БЛОГ НА HUSL

Поиск компонент связности в графе

Ответы (1 шт):