|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
20.12.2012, 16:54 | #1 |
Пользователь
Регистрация: 04.04.2011
Сообщений: 12
|
C++. Графы
Доброго времени суток.
Делаю задание по графам(граф неориентированный): Для графа, представленного матрицей смежности построить все цепи, исходящие из заданной вершины. На данный момент реализовал такой алгоритм: Заносим в стэк начальную вершину.(последующие вершины также помещаются в стэк). Проходим по строке в матрице, если встречаем 1, проверяем есть ли в стэке данная вершина,если нет - переходим к той вершине(записываем в стэк) и зануляем данный элемент в матрице и так далее.Когда произойдет тупик, то есть пройдём по всей строке в матрице и не перейдём на другую вершину(вывожу всю цепь),удаляем эту вершину из стэка и далее повторяются все действия,которые я описал раньше. Всё работает отлично только в том случае, если граф без циклов. Если же граф с циклами,например: то , программа выведет все цепи, кроме 0-2-3-4, так как после построения цепи 0-1-3-4 вершина 4 для вершины 3 стала недостижимой.Как можно доработать программу? Исходный код: Код:
Код:
Последний раз редактировалось ZavriK; 20.12.2012 в 17:43. |
20.12.2012, 17:19 | #2 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
Объявите mas как const int**. |
|
20.12.2012, 17:30 | #3 |
Пользователь
Регистрация: 04.04.2011
Сообщений: 12
|
Каким образом тогда мне устанавливать связи между вершинами в графе?
Я ввожу координату строки,столбца(вершина и вершина с ней связанная) и этому элементу массива присваивается значение, равное 1. Если массив будет объявлен с const так сделать не получится. |
20.12.2012, 17:35 | #4 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
|
|
20.12.2012, 17:47 | #5 |
Пользователь
Регистрация: 04.04.2011
Сообщений: 12
|
В таком случае программа зациклится.
Будет постоянно выводиться цепь: 0-1-3-2 |
20.12.2012, 17:59 | #6 |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
1) К цепи может быть прибавлена только вершина, инцидентная к последней в цепи;
2) К цепи не может быть прибавлена вершина, уже присутствующая в цепи; 3) Цепь построена, когда к ней не может быть прибавлена ни одна вершина; 4) Цепь начинается с заданной вершины. Я бы делал через рекурсивные вызовы вида "удлинить цепь на шаг". Но можно развернуть и в цикл. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Графы | Sarmat) | Помощь студентам | 2 | 21.06.2011 21:48 |
Графы в С++ | lilu777 | C++ Builder | 3 | 26.05.2011 00:59 |
Графы | Daniya.ru | Общие вопросы C/C++ | 1 | 11.12.2010 21:33 |
графы! | Daniya.ru | Общие вопросы C/C++ | 6 | 09.12.2010 21:16 |
графы | delete | Общие вопросы C/C++ | 2 | 28.10.2009 21:31 |