|
Вопрос # 2 379/ вопрос открыт / |
|
Здравствуйте!Подскажите пожайлуста, как найти и вывести путь между заданными вершинами графа?
 |
Вопрос задала: Milady (статус: Посетитель)
Вопрос отправлен: 2 февраля 2009, 18:11
Состояние вопроса: открыт, ответов: 0.
|
Мини-форум вопроса
Всего сообщений: 5; последнее сообщение — 2 февраля 2009, 19:15; участников в обсуждении: 3.
|
Вадим К (статус: Академик), 2 февраля 2009, 18:24 [#1]:
А как сам граф задан?
в общем, задача решается обычной банальной рекурсией. То есть, вначале запускается рекурсия с одной вершины, и когда достигается другая, то выписывается путь. Если надо найти путь легче (то есть есть цена веток), то надо составлять список возможных путей...
Задача решаема, главное иметь полное условие.
Галочка "подтверждения прочтения" - вселенское зло.
|
|
|
Milady (статус: Посетитель), 2 февраля 2009, 18:39 [#2]:
граф такой: 6 узлов и 7 ребрер,неориентированный, взвешенный, его матрица смежности:
0 5 0 0 0 7
5 0 4 0 0 0
0 4 0 2 1 0
0 0 2 0 3 0
0 0 1 3 0 8
7 0 0 0 8 0
а как программно реализовать поиск путей?
|
|
|
Вадим К (статус: Академик), 2 февраля 2009, 18:45 [#3]:
к сожалению, я не знаю, как читать такие матрицы смежности. Хотя есть идеи как... А так как я не знаю, как он выглядит.... я ничего не могу помочь
Галочка "подтверждения прочтения" - вселенское зло.
|
|
Dron (статус: Студент), 2 февраля 2009, 19:01 [#4]:
Обычно матрицы смежности задаются квадратными матрицами: по вертикали и по горизонтали перечисляются вершины. Если вершины смежны, на их пересечении в клетке ставится единица (1), если нет - 0.
С уважением.
|
|
|
Dron (статус: Студент), 2 февраля 2009, 19:15 [#5]:
Цитата (Milady):
Вооот! а как найти путь между заданными вершинами?
Вероятно, перебором. А как ещё? Не припомню, чтобы были какие-то действенные способы.
С уважением.
|
Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.
|
