Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 03.02.2015, 22:06   #51
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Проще всего бахнуть
vector<list<int> > v(n);
тогда это будет вектор списков.. То есть.. v[i] будет список вершин, в которые мы можем попасть из i-ой..
Вот..
Тогда нужно будет поправить Флойда и прочее..
Poma][a вне форума Ответить с цитированием
Старый 03.02.2015, 22:20   #52
Вероника99
Форумчанин
 
Регистрация: 15.12.2013
Сообщений: 414
По умолчанию

А без использования шаблонов?Я при вводе одномерного массива заношу значения сразу в матрицу,а пустые потом обнуляю,но может есть более логичный способ
Вероника99 вне форума Ответить с цитированием
Старый 03.02.2015, 22:26   #53
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Фишка в том, что использование списков смежности(ребер) позволяет использовать меньше памяти и времени за счет разреженности графа..
В другом случае никаких плюшек нет..
Вот и подумайте, надо оно вам?
Если не делать шаблонами, то там будет печалька с динамическим выделением памяти..
Poma][a вне форума Ответить с цитированием
Старый 03.02.2015, 22:28   #54
Вероника99
Форумчанин
 
Регистрация: 15.12.2013
Сообщений: 414
По умолчанию

Poma][a,это по заданию нужно, чтобы граф был представлен как список смежности и найти пути по Флойду без использования шаблонов Не обязательно по Флойду,просто найти самый короткий путь
Вероника99 вне форума Ответить с цитированием
Старый 03.02.2015, 23:30   #55
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 474
По умолчанию

Вероника99, а если применить гибридное решение?
В проге, что я приводил ранее в подпрограмму FU передаётся матрица смежности mV, потом при инициализации переменных для алгоритма она модифицируется в матрицу D, далее алгоритм и выдача результатов (путь от A к B).
Есть ограничение от преподавателя на преобразование исходного списка в матрицу D или нет?
FPaul вне форума Ответить с цитированием
Старый 03.02.2015, 23:38   #56
Вероника99
Форумчанин
 
Регистрация: 15.12.2013
Сообщений: 414
По умолчанию

FPaul,про ограничения он ничего не говорил,поэтому я думаю,что можно так делать. Я пришла к решению,что можно значения из одномерного массива присваивать матрице смежности,а потом уже к образованной матрице применять алгоритм Ф-У. Или у вас другая идея?
Вероника99 вне форума Ответить с цитированием
Старый 04.02.2015, 00:05   #57
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 474
По умолчанию

Да и у меня почти такая идея.
Различие:
1. В основной программе чтение и работа производится со списком смежности.
2. В FU (хотя второй-то не U, а Warshall) передаётся список, где на его основе получается матрица D.
-----------------------------------
Можно, правда попытаться и работать со списком, но придется добавлять три цикла поиска значений Dij, Dik, Dkj эквивалентных D[i][j] и т.д. Но простое предположение, что в конечном итоге из произвольной вершины можно будет попасть в большинство других вершин, приводит к мысли о перерождении списков в подобие матрицы при отсутствии простого доступа к его элементам. Хотя можно придумать случаи, где это не так.
В общем всё зависит от заказчика - преподавателя.

Последний раз редактировалось FPaul; 04.02.2015 в 00:11.
FPaul вне форума Ответить с цитированием
Старый 04.02.2015, 07:41   #58
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Не-не-не! Нам не нужно искать значения. Просто будет цикл от 1 до n. А потом будем пробегаться по всем ребрам и пытаться улучшить путь с помощью каждого ребра. Вот
Poma][a вне форума Ответить с цитированием
Старый 04.02.2015, 08:42   #59
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 474
По умолчанию

Да? А я представлял себе алгоритм Ф-У как D[i][j]=min(.....), т.е. выбор промежуточной вершины k, к которой уже определены стоимости пути как от i так и до j. Вполне вероятно, что что-то упускаю - не могу представить как это будет работать со списками иначе, чем с тремя доп. циклами.
Если не сложно, приведи детальный псевдокод (а лучше код), работающий с новым представлением графов. А вам слабо?!
FPaul вне форума Ответить с цитированием
Старый 04.02.2015, 09:27   #60
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Фигня-вопрос но только вечером, ибо с телефона совсем не ахти
Poma][a вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
ПОстроение графа по заданным вершинам 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