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

Двудольный граф?? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
Astin TorN
11 / 11 / 1
Регистрация: 02.05.2011
Сообщений: 28
26.05.2011, 15:33     Двудольный граф?? #1
Проверка является ли граф двудольным))
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2011, 15:33     Двудольный граф??
Посмотрите здесь:

C++ Граф
Граф C++
C++ Граф
Считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл C++
Граф C++
C++ Граф в С
Граф C++
Двудольный граф C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
BEL-28
1 / 1 / 0
Регистрация: 12.02.2011
Сообщений: 5
26.05.2011, 16:00     Двудольный граф?? #2
Цитата Сообщение от Astin TorN Посмотреть сообщение
Проверка является ли граф двудольным))
Стандартная задача на графы. Дан граф - проверить является ли он двудольным. Граф двудольный тогда и только тогда когда все циклы четны. Решается за один обход в глубину. На каждом шаге обхода в глубину метим вершину. Допустим мы пошли в первую вершину - добавляем ее в первую группу. То есть ставим метку один. Затем просматриваем все смежные вершины и если не помечена вершина, то метим ее как 2(то есть запихиваем в противоположную группу) и и рекурсивно переходим в нее. Если же она мечена и у нее такая же метка как у нашей - то все граф не двудольный.
Yandex
Объявления
26.05.2011, 16:00     Двудольный граф??
Ответ Создать тему
Опции темы

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