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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.72
Ксения7
1 / 1 / 0
Регистрация: 18.03.2013
Сообщений: 72
#1

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

18.03.2013, 21:08. Просмотров 2608. Ответов 1
Метки нет (Все метки)

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

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru