 |
|
|
 
|
|
граф связность 
| implements |
|
|||
|
Бывалый  Профиль Группа: Участник Сообщений: 210 Регистрация: 20.7.2010 Репутация: нет Всего: нет |
Здравствуйте, не подскажите ли алгоритм проверки графа на связность
(связность -что от любой вершины графа можно дойти до любой другой), дали такое описание т.е. получается, если от одной вершины можно добраться до всех остальных, то это связной граф, если до какой либо добраться нельзя, значит нет, так? |
|||
|
||||
Загрузка ...
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| implements |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 210 Регистрация: 20.7.2010 Репутация: нет Всего: нет |
спасибо, почитаю, вообще я так понял,для любого графа, что из любой вершины можно дойти до любой другой, или я не так, что-то понимаю? |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Можешь вообще использовать тупо метод заливки.
Красишь все вершины графа в чёрный цвет. Затем одну вершину делаешь белой. Выбираешь все рёбра, где одна вершина белая, а другая чёрная, красишь чёрные в белый цвет. Если была покрашена хотя бы одна вершина - повторяешь. Если осталась хотя бы одна чёрная вершина - граф несвязный. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| implements |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 210 Регистрация: 20.7.2010 Репутация: нет Всего: нет |
Akina, так ну с алгоритмом в принципе более менее понятно, не понятно каким образом(видом) задать граф для этой задачи
|
|||
|
||||
| Akina |
|
||||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Вектором связности. Скажем, в терминах SQL это может быть (схематично):
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
||||
|
|||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0847 ] [ Использовано запросов: 20 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |