Как по матрице смежности нескольких графов найти множество отдлеьных графов?

Question

Как по матрице смежности нескольких графов найти множество отдлеьных графов?

Рейтинг: 1Ответов: 2Опубликовано: 07.04.2023

Пусть граф задаётся как множество вершин = (в1,в2 ...) и есть матрица смежности для подобного набора графов:

В данном случае она будет выглядеть так :

Как по матрице смежности понять, что граф (в1,в2,в3) это отдельный граф? Какие есть подходы к этому?

PS: вершины отдельного графа не обязательно стоят подряд в матрице смежности

c# алгоритм графы

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

Выполните серию обходов в ширину (или в глубину, без разницы).

Когда обход из первой вершины завершён - помечен первый компонент связности.

Теперь найдите непомеченную вершину и обойдите следующий компонент связности. Повторяйте, пока не останется вершин непомеченных

Answer 2

▲ 0

#include <map>
#include <vector>
#include <cstdlib>
#include <iostream>

#define noColorCode 0

int checkVecForValue(std :: vector <int>* vec, int value){
    for(size_t i = 0; i < vec->size(); ++i){
        if(vec->at(i) == value){
            return i;
        }
    }
    return -1;
}

void recursColor(std :: map< int, std :: vector <int> >* adjacencyMatrix, std :: vector <int>* colors, int actualNum, int color){
    if(colors->at(actualNum) == color){return;}
    colors->at(actualNum) = color;
    auto currNeibVec = adjacencyMatrix->at(actualNum+1); //я точно знаю, что ключ и индекс разнятся на 1
    for(size_t i = 0; i < currNeibVec.size(); ++i){
        int currNeib = currNeibVec.at(i);
        int currNeibIdx = checkVecForValue(&currNeibVec, currNeib);
        if(currNeibIdx == -1){
            std :: cout << "\nBIG ERROR"<< std :: flush;
            abort();
        }
        recursColor(adjacencyMatrix, colors, currNeib - 1, color);
    }
}

void recStart(std :: map< int, std :: vector <int> >* adjacencyMatrix, std :: vector <int>* colors){
    if(adjacencyMatrix->size() < 2){
        return;
    }
    int color = noColorCode + 1;
    recursColor(adjacencyMatrix, colors, 0, color); ++color;
    int newPos;
    while( (newPos = checkVecForValue(colors, noColorCode)) != -1){
        recursColor(adjacencyMatrix, colors, newPos, color); ++color;
    }
}

int main()
{
    std :: map< int , std :: vector <int> > adjacencyMatrix = {
        {1,{1,3}},
        {2,{2,3}},
        {3,{3,1,2}},
        {4,{4,5}},
        {5,{5,4}}
    };
    std :: vector <int> colors(adjacencyMatrix.size(), noColorCode);

    recStart(&adjacencyMatrix, &colors);
    for (int x : colors)
            std :: cout << x << " ";
    return 0;
}

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

сам граф из программы:

Как по матрице смежности нескольких графов найти множество отдлеьных графов?

Ответы