![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
|
Опции темы | Поиск в этой теме |
![]() |
#51 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
Проще всего бахнуть
vector<list<int> > v(n); тогда это будет вектор списков.. То есть.. v[i] будет список вершин, в которые мы можем попасть из i-ой.. Вот.. Тогда нужно будет поправить Флойда и прочее.. |
![]() |
![]() |
![]() |
#52 |
Форумчанин
Регистрация: 15.12.2013
Сообщений: 414
|
![]()
А без использования шаблонов?Я при вводе одномерного массива заношу значения сразу в матрицу,а пустые потом обнуляю,но может есть более логичный способ
|
![]() |
![]() |
![]() |
#53 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
Фишка в том, что использование списков смежности(ребер) позволяет использовать меньше памяти и времени за счет разреженности графа..
В другом случае никаких плюшек нет.. Вот и подумайте, надо оно вам? Если не делать шаблонами, то там будет печалька с динамическим выделением памяти.. |
![]() |
![]() |
![]() |
#54 |
Форумчанин
Регистрация: 15.12.2013
Сообщений: 414
|
![]()
Poma][a,это по заданию нужно, чтобы граф был представлен как список смежности и найти пути по Флойду без использования шаблонов Не обязательно по Флойду,просто найти самый короткий путь
|
![]() |
![]() |
![]() |
#55 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 474
|
![]()
Вероника99, а если применить гибридное решение?
В проге, что я приводил ранее в подпрограмму FU передаётся матрица смежности mV, потом при инициализации переменных для алгоритма она модифицируется в матрицу D, далее алгоритм и выдача результатов (путь от A к B). Есть ограничение от преподавателя на преобразование исходного списка в матрицу D или нет? |
![]() |
![]() |
![]() |
#56 |
Форумчанин
Регистрация: 15.12.2013
Сообщений: 414
|
![]()
FPaul,про ограничения он ничего не говорил,поэтому я думаю,что можно так делать. Я пришла к решению,что можно значения из одномерного массива присваивать матрице смежности,а потом уже к образованной матрице применять алгоритм Ф-У. Или у вас другая идея?
|
![]() |
![]() |
![]() |
#57 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 474
|
![]()
Да и у меня почти такая идея.
Различие: 1. В основной программе чтение и работа производится со списком смежности. 2. В FU (хотя второй-то не U, а Warshall) передаётся список, где на его основе получается матрица D. ----------------------------------- Можно, правда попытаться и работать со списком, но придется добавлять три цикла поиска значений Dij, Dik, Dkj эквивалентных D[i][j] и т.д. Но простое предположение, что в конечном итоге из произвольной вершины можно будет попасть в большинство других вершин, приводит к мысли о перерождении списков в подобие матрицы при отсутствии простого доступа к его элементам. Хотя можно придумать случаи, где это не так. В общем всё зависит от заказчика - преподавателя. Последний раз редактировалось FPaul; 04.02.2015 в 00:11. |
![]() |
![]() |
![]() |
#58 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
Не-не-не! Нам не нужно искать значения. Просто будет цикл от 1 до n. А потом будем пробегаться по всем ребрам и пытаться улучшить путь с помощью каждого ребра. Вот
|
![]() |
![]() |
![]() |
#59 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 474
|
![]()
Да? А я представлял себе алгоритм Ф-У как D[i][j]=min(.....), т.е. выбор промежуточной вершины k, к которой уже определены стоимости пути как от i так и до j. Вполне вероятно, что что-то упускаю - не могу представить как это будет работать со списками иначе, чем с тремя доп. циклами.
Если не сложно, приведи детальный псевдокод (а лучше код), работающий с новым представлением графов. ![]() ![]() |
![]() |
![]() |
![]() |
#60 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
Фигня-вопрос
![]() |
![]() |
![]() |
![]() |
|
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
ПОстроение графа по заданным вершинам | Otar4ik | Общие вопросы C/C++ | 6 | 11.09.2014 21:47 |
создание графа по матрице и поиск кратчайшего пути из одного графа в другой | lexflax | Общие вопросы C/C++ | 1 | 06.09.2012 07:32 |
Построить ломаную линию по заданныи вершинам. Вершины указываются с клавиатуры по «методу резиновой нити». | HollywoodStar | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 17.12.2011 14:36 |
по заданной матрице смежности простого графа построить каркас этого графа с использованием поиска вширь | d1m2o3n4 | Помощь студентам | 0 | 22.06.2011 22:43 |
проход по дереву на c++ | Skilluser | Помощь студентам | 18 | 20.11.2010 19:34 |