Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.10.2021, 18:53   #1
nut_filling
Новичок
Джуниор
 
Регистрация: 28.10.2021
Сообщений: 2
По умолчанию Максимальная компонента связности

Нужно найти компоненту связности с максимальным числом элементов (используя поиск в глубину).
Граф задается матрицей смежности.

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

Код:
#include <iostream>
#include <queue> // очередь
using namespace std;
int main() {
    queue<int> Queue;
    cout << "Введите размер матрицы: ";
    int n; cin >> n;
    int mas[n][n];
    int nodes[n]; // вершины графа
 
    cout << "Введите матрицу матрицу: " << endl;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> mas[i][j];
 
    for (int i = 0; i < n; i++) {
        nodes[i] = 0;
        Queue.push(0); // помещаем в очередь первую вершину
 
        while (!Queue.empty()) { // пока очередь не пуста
            int node = Queue.front(); // извлекаем вершину
            Queue.pop();
            nodes[node] = 2;                                // отмечаем ее как посещенную
 
            for (int j = 0; j < n; j++) {                    // проверяем для нее все смежные вершины
                if (mas[node][j] == 1 && nodes[j] == 0) {    // если вершина смежная и не обнаружена
                    Queue.push(j);                          // добавляем ее в очередь
                    nodes[j] = 1;                           // отмечаем вершину как обнаруженную
                }
            }
            cout << node + 1 << " "; // выводим номер вершины
        }
        cout << endl;
    }
 
    return 0;
}
вывод будет выглядеть так:
1
1
1 3
1 4
1
nut_filling вне форума Ответить с цитированием
Старый 28.10.2021, 19:09   #2
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Не хватает ввода вашей программы, чтобы как-то интерпретировать вывод. Не нужно начинать печатать вершины, когда вы только еще ищете компоненту связности (только если для отладки). Неверно занулять nodes[i] в начале тела цикла, так как элемент уже может принадлежать другой компоненте связности. Неверно помещать в очередь нулевой, а не i-ый элемент, как первый элемент компоненты связности. Направление решения верное. В каком именно виде требуется вывод компоненты связности - номера элементов этой компоненты? Что если есть несколько компонент одинакового размера?
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 28.10.2021, 19:38   #3
nut_filling
Новичок
Джуниор
 
Регистрация: 28.10.2021
Сообщений: 2
По умолчанию

BDA, не совсем понимаю как зациклить на проверку всех вершин, можете сказать что примерно нужно искать(в плане статей)?
nut_filling вне форума Ответить с цитированием
Старый 28.10.2021, 20:07   #4
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

В плане статей не знаю. А по коду у вас и так есть цикл для выбора начальной вершины очередной компоненты связности (но с небольшими ошибками) и цикл для поиска смежных вершин (визуально без ошибок).
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Подсчет числа компонент связности С++ Li*zA Помощь студентам 3 20.04.2011 05:41
формирование матрицы связности по списку по контактам hed Помощь студентам 1 19.09.2010 00:58
Поиск в глубину и проверка связности fallti Общие вопросы C/C++ 4 12.05.2010 21:47
Компоненты связности Imelstron Помощь студентам 3 31.12.2007 20:49