Форум программистов, компьютерный форум CyberForum.ru

Компоненты связности графа поиском в глубину - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.72
Ксения7
1 / 1 / 0
Регистрация: 18.03.2013
Сообщений: 72
18.03.2013, 21:08     Компоненты связности графа поиском в глубину #1
Доброго времени суток милые форумчане!!! Очень нужна ваша помощь, сама справиться не в силах. Нужно посчитать количестко компонент связности в неориентированном графе с помощью поиска в глубину,вевести их количество и вершины каждой из них. Сам граф задан текстовым файлом, в начале указано общее количество вершин. Спасибо!
Вложения
Тип файла: txt input.txt (41 байт, 41 просмотров)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.03.2013, 21:08     Компоненты связности графа поиском в глубину
Посмотрите здесь:

C++ не компилируется задание: компонент связности графа - кто разберется
Обход графа в глубину C++
C++ Найти компоненты связности
C++ Методом обхода в глубину определить число компонент связности и цикломатическое число графа
C++ Графы и компоненты связности в них
C++ Обход вершин графа в глубину стеком
Ошибка в поиске компоненты сильной связности (графы) C++
Обход неориентированного графа в глубину C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
21.03.2013, 14:02     Компоненты связности графа поиском в глубину #2
Навскидку алгоритм такой: Берём любую вершину графа, начинаем с неё обход в глубину. Как только обход завершился - инкрементируем количество компонент связности. Затем смотрим, остались ли ещё не обойдённые вершины. Если да - берём любую из них и снова начинаем обход. Обошли - инкремент счётчика. Смотрим, есть ли не обойдённые вершины... Завершаем подсчёт, когда после очередного обхода не осталось не обойдённых вершин.
Yandex
Объявления
21.03.2013, 14:02     Компоненты связности графа поиском в глубину
Ответ Создать тему
Опции темы

Текущее время: 22:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru