Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Дан граф, определить, является ли он связным  (Прочитано 7122 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Smile
Гость
« : 03-09-2008 10:43 » 

Помогите пожалуйста! Жаль "Дан граф, определить, является ли он связным". Вроде алгоритм нашла:
Проверка связности графа с ненаправленными ребрами. Выделение связной компоненты графа
Разделим все вершины графа на три разновидности:
1. Вершины, про которые ничего не известно; Вершины, про которые известно, что они могут быть достигнуты из начальной вершины и которые не были обработаны. Вершины, про которые известно, что они могут быть достигнуты из начальной вершины и которые были обработаны.
Выделение связной компоненты графа.
В этом алгоритме три этапа - первоначальная разметка, распространение разметки и формирование результата.
1. Первоначальная разметка
Пометим все вершины первым маркером - нам про них ничего не известно
Выберем любую вершину (например первую (или нулевую)), пометим ее вторым маркером, ведь она может быть достигнута сама из себя.
2. Разметка соседних вершин
Если нет вершин, помеченных вторым маркером - переходим к третьему этапу.
Выберем любую вершину, помеченную вторым маркером. Пометим ее третьим маркером. Все вершины, соседние с данной и помеченные первым маркером, пометим вторым маркером.
Повторим этот пункт с начала.
3. Завершение работы
Если нужно получить список вершин, входящих в одну компоненту связности с заданной вершиной, то выбираем вершины, помеченные третьим маркером, в отдельный массив.
Если нужно получить список вершин, не входящих в одну компоненту связности с заданной вершиной, то выбираем вершины, помеченные первым маркером в отдельный массив и возвращаем полученный массив.
Если нужно просто проверить граф на связность, то считаем вершины, помеченные первым маркером, и сравниваем получившееся число с нулем. Если число вершин, помеченные первым маркером, равно нулю, то граф связный.


но я не поймуууу((( напишите кто-нибудь код, пожаааалуйста Жаль
Записан
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 03-09-2008 11:04 » new

Мне кажется, выделение связной компоненты - задача более сложная, нежели проверка связности в принципе.
Разве недостаточно разделить вершины на 2 группы: 1. те, про которые ничего не известно и 2. про которые известно, что из них можно попасть в некую базовую вершину?
Тогда можно было бы рекурсивно распространять маркировку связности (перевод из группы 1 в группу 2) перебором в глубину (т.е. выбирать все смежные вершины с "неизвестным" состоянием, маркировать каждую и тут же выполнять для неё то же самое рекурсивно). Когда процесс закончится, останется посмотреть, все ли вершины промаркированы как связанные с исходной.
« Последнее редактирование: 03-09-2008 11:05 от Вад » Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines