8 / 8 / 5
Регистрация: 27.10.2013
Сообщений: 170
|
||||||
1 | ||||||
Графы-Поиск в ширину22.11.2013, 13:53. Показов 5499. Ответов 4
Метки нет (Все метки)
В неориентированном графе требуется найти минимальный путь между двумя вершинами.
Формат входных данных Первым на вход поступает число N – количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной. Формат выходных данных Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а затем L + 1 число – путь от одной вершины до другой, заданный своими вершинами. Если пути не существует, выведите одно число –1. Пример: Входные данные: 5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5 Выходные данные: 3 3 2 1 5 Есть наработки с учителем, но все равно не догоняю как все должно работать. Вот собственного сама программа, но в ней присутствуют ошибки. Не могли бы вы объяснить как это все работать должно.
Блин вот убейте не помню для чего нужен массив q. P.S. Заранее буду благодарен.
0
|
22.11.2013, 13:53 | |
Ответы с готовыми решениями:
4
Графы. Поиск путей. Алгоритм Йена поиск в ширину Графы: поиск в ширину, поиск вершины с максимальной степенью графы. поиск в ширину |
Супер-модератор
|
|||||||||||
22.11.2013, 16:28 | 2 | ||||||||||
Сообщение было отмечено volvo как решение
Решение
Пишем вот такие 2 подпрограммы:
1
|
8 / 8 / 5
Регистрация: 27.10.2013
Сообщений: 170
|
|
22.11.2013, 19:20 [ТС] | 3 |
А можно как нибудь объяснить этот алгоритм?
0
|
Супер-модератор
|
|
22.11.2013, 19:27 | 4 |
http://ru.wikipedia.org/wiki/%... 0%BD%D1%83 там есть и неформальное и формальное описание.
0
|
18 / 11 / 5
Регистрация: 27.05.2013
Сообщений: 36
|
|
22.11.2013, 22:34 | 5 |
Mikky Lova, массив q (я так понимаю, это первая буква английского слова queue - очередь) нужен для того, чтобы реализовать алгоритм поиска в ширину. Мы рассматриваем вершину, и добавляем все связанные с ней в очередь. А потом делаем то же самое для следующей вершины в очереди.
0
|
22.11.2013, 22:34 | |
22.11.2013, 22:34 | |
Помогаю со студенческими работами здесь
5
Обход в ширину (графы) Графы, обход вершин в ширину и глубину Графы, нахождение наименьшего пути между вершинами обходом в ширину Графы. Метод, отличающийся от поиска в ширину тем, что вновь достигнутая вершина помещается не в очередь, а в стек Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |