|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
10.05.2010, 22:19 | #1 |
Регистрация: 10.05.2010
Сообщений: 8
|
Поиск в глубину и проверка связности
задание - с помощью пгв проверить связность графа, граф задан списком
написал код, который создает список и формирует пгв, но при входе в функцию вылетает ошибка. функцию взял отсюда http://e-maxx.ru/algo/dfs Код:
за ранее благодарен |
11.05.2010, 00:14 | #2 |
Форумчанин
Регистрация: 18.02.2010
Сообщений: 164
|
#include <locale.h>; setlocale(LC_ALL,"Russian"); руссификация намного проще на связность графа сейчас или утром напишу . . .
|
11.05.2010, 20:10 | #3 |
Регистрация: 10.05.2010
Сообщений: 8
|
спасибо за другой метод русификации, обязательно попробую, но мне граф важнее
|
12.05.2010, 15:25 | #4 |
Форумчанин
Регистрация: 18.02.2010
Сообщений: 164
|
1. Первоначальная разметка
Пометим все вершины первым маркером - нам про них ничего не известно Выберем любую вершину (например первую (или нулевую)), пометим ее вторым маркером, ведь она может быть достигнута сама из себя. 2. Разметка соседних вершин Если нет вершин, помеченных вторым маркером - переходим к третьему этапу. Выберем любую вершину, помеченную вторым маркером. Пометим ее третьим маркером. Все вершины, соседние с данной и помеченные первым маркером, пометим вторым маркером. Повторим этот пункт с начала. 3. Завершение работы Если нужно получить список вершин, входящих в одну компоненту связности с заданной вершиной, то выбираем вершины, помеченные третьим маркером, в отдельный массив. Если нужно получить список вершин, не входящих в одну компоненту связности с заданной вершиной, то выбираем вершины, помеченные первым маркером в отдельный массив и возвращаем полученный массив. Если нужно просто проверить граф на связность, то считаем вершины, помеченные первым маркером, и сравниваем получившееся число с нулем. Если число вершин, помеченные первым маркером, равно нулю, то граф связный. И достаточно разделить вершины на 2 группы: 1. те, про которые ничего не известно и 2. про которые известно, что из них можно попасть в некую базовую вершину? Тогда можно было бы рекурсивно распространять маркировку связности (перевод из группы 1 в группу 2) перебором в глубину (т.е. выбирать все смежные вершины с "неизвестным" состоянием, маркировать каждую и тут же выполнять для неё то же самое рекурсивно). Когда процесс закончится, останется посмотреть, все ли вершины промаркированы как связанные с исходной. Отзывы не забываем)) |
12.05.2010, 21:47 | #5 |
Регистрация: 10.05.2010
Сообщений: 8
|
очень благодарен) большое спасибо)
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Поиск кратчайшего пути в графе методом полного перебора в глубину. Метод ветвей и границ | Олинька | Помощь студентам | 1 | 24.12.2008 16:22 |
Компоненты связности | Imelstron | Помощь студентам | 3 | 31.12.2007 20:49 |