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

Проверка графа на возможность достижимости одной вершины из другой - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.86
Мунир
0 / 0 / 0
Регистрация: 16.11.2010
Сообщений: 4
16.11.2010, 18:46     Проверка графа на возможность достижимости одной вершины из другой #1
Дана система двусторонних дорог, соединяющих пары городов. Является ли заданное множество дорог таким, что закрытие одной из них ведёт к нарушению сообщения между двумя указанными городами?

Как решить данную прогу? Я создал матрицу смежности, а вот прогу для проверки не могу((
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.11.2010, 18:46     Проверка графа на возможность достижимости одной вершины из другой
Посмотрите здесь:

вывод простых циклов, из каждой вершины графа C++
C++ можно ли в с++ вызвать переменную из одной функции в другую т.е. мы переменну задали в одной функции а использовали в другой... и как это реализовать?
C++ Найти степени входа и выхода каждой вершины графа.
C++ Вершины графа выводить буквами
Найти все вершины графа, к которым существует путь заданной длины от вершины, номер которой вводится с клавиатуры. C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.11.2010, 19:23     Проверка графа на возможность достижимости одной вершины из другой #2
Я создал матрицу смежности
это как?
Мунир
0 / 0 / 0
Регистрация: 16.11.2010
Сообщений: 4
16.11.2010, 19:56  [ТС]     Проверка графа на возможность достижимости одной вершины из другой #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void VVOD_MSM(int msm[NMAX][NMAX], int n)
{
 int i,j;
 printf("\nВведите матрицу смежности\n");
 printf("|");
 for(j=0;j<n;j++) printf("%d ",j);
 putchar('\n');
 for(i=0;i<2*n+2;i++) putchar('-');
 for(i=0;i<n;i++)
 {printf("\n%d| ",i);
  for(j=0;j<n;j++) scanf("%d", &msm[i][j]);
 }
 putchar('\n');
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.11.2010, 20:07     Проверка графа на возможность достижимости одной вершины из другой #4
на матрицу смежности похоже, а входные данные откуда? с клавиатуры или с файла?
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
16.11.2010, 21:16     Проверка графа на возможность достижимости одной вершины из другой #5
Цитата Сообщение от Мунир Посмотреть сообщение
Как решить данную прогу?
определить является ли заданый граф минимальным остовным деревом за алгоритмом Прима
Мунир
0 / 0 / 0
Регистрация: 16.11.2010
Сообщений: 4
16.11.2010, 21:25  [ТС]     Проверка графа на возможность достижимости одной вершины из другой #6
С клавиатуры данные)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.11.2010, 05:57     Проверка графа на возможность достижимости одной вершины из другой #7
Мунир, Я так понимаю что в матрице смежности, которая у нас есть уже отражен случай закрытия одной из дорог и имеются города между которыми нужно проверить связь.
Я бы сделал так:
Создаем массив int размером N (где N кол-во вершин) - будем использовать его в качестве очереди.
Создаем массив bool размером N (Для отметок уже пройденных вершин).
Далее алгоритм следующий:
Берем первую вершину (город от которого ищем путь), отмечаем ее в массив bool, и номер ее заносим в очередь.
Следующее ниже организуется в цикле, например с помощью while():
Затем берем первую вершину из очереди. По матрице смежности смотрим с какими вершинами она связана, если у этих вершин уже есть метки в массиве bool, то пропускаем их, если меток нет, то берем эти вершины, ставим им метки в массиве bool, а номера загоняем в очередь.
Теперь вопрос когда выйти из цикла. Выйти из цикла нужно в двух случаях: когда мы достигнем второй вершины (это легко проверить по массиву bool), или когда очередь опустеет.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.11.2010, 16:38     Проверка графа на возможность достижимости одной вершины из другой
Еще ссылки по теме:

Нахождение всех путей в графе от одной вершины до другой обходом в ширину C++
Поиск самого длинного пути от первой до последней вершины ацикличного ориентированного невзвешенного графа C++
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А C++

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

Или воспользуйтесь поиском по форуму:
Мунир
0 / 0 / 0
Регистрация: 16.11.2010
Сообщений: 4
17.11.2010, 16:38  [ТС]     Проверка графа на возможность достижимости одной вершины из другой #8
Спасибо за информацию) Буду пытаться написать что-то)
Yandex
Объявления
17.11.2010, 16:38     Проверка графа на возможность достижимости одной вершины из другой
Ответ Создать тему
Опции темы

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