Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/7: Рейтинг темы: голосов - 7, средняя оценка - 5.00
Pearl_lce
0 / 0 / 0
Регистрация: 17.10.2014
Сообщений: 9
1

Список смежности во взвешенных графах

19.01.2015, 00:18. Просмотров 1330. Ответов 8
Метки нет (Все метки)

Здрасте!

Не получается реализовать списки смежности для ВЗВЕШЕННОГО графа.

Я умею реализовывать списки для не взвешенных графов. И никак не могу додуматься как добавить в него вес ребра.

Подскажите плз.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.01.2015, 00:18
Ответы с готовыми решениями:

Вывести матрицу смежности и список смежности графа
Всем привет!! Уважаемые форумчане, помогите плиз с заданием! Я написала код в Си по которому...

Граф (Матрица смежности, список смежности)
Понятия неимею, как можно написать код по условию программы так как с графами не бум бум. ...

Список пар в матрицу смежности
Нужно написать программу для преобразования списка пар в матрицу смежности для неориентированного...

Считать список смежности из файла
Добрый день! Новичок в программировании, поэтому заранее извиняюсь за код с возможными очевидными...

Конвертор из графы в список смежности
Добрый вечер. Нужна помощь в Си. Нужно сделать конвертор из графы в список смежности. Дело в том...

8
_Ivana
3239 / 1873 / 235
Регистрация: 01.03.2013
Сообщений: 5,112
Записей в блоге: 13
19.01.2015, 00:25 2
Либо вы шутите, либо я вас не понимаю. Добавляете третью колонку в список - получаете ребро как тройку: откуда, куда и вес.
1
Pearl_lce
0 / 0 / 0
Регистрация: 17.10.2014
Сообщений: 9
19.01.2015, 00:43  [ТС] 3
Увы не шучу. Я пытаюсь реализовать алгоритм Дейкстры на списках. Собираю информацию по кусочкам. Спасибо за совет, сгоняю в душ и попробую на бумаге рассчитать "добавление веса в списки".

Благодарю вас за столь быстрый ответ.
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
20.01.2015, 02:07 4
Вместо массивов с индексами хранить массивы пар (индекс, вес).
1
Pearl_lce
0 / 0 / 0
Регистрация: 17.10.2014
Сообщений: 9
20.01.2015, 11:44  [ТС] 5
Благодарю за ответ

Добавлено через 9 часов 35 минут
Сделал "третью колонку" с весом как посоветовали. Вроде как нормально получилось. Теперь пытаюсь с помощью Дейкстры рассчитать минимальный путь.
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
20.01.2015, 13:05 6
Цитата Сообщение от Pearl_lce Посмотреть сообщение
Сделал "третью колонку" с весом как посоветовали.
Можно узнать, почему третью, а не вторую? Или граф вообще списком рёбер представлен?
0
Pearl_lce
0 / 0 / 0
Регистрация: 17.10.2014
Сообщений: 9
20.01.2015, 15:31  [ТС] 7
Можно узнать, почему третью, а не вторую? Или граф вообще списком рёбер представлен?
Да, моя реализация представлена списком ребер и соответственно: куда ведет ребро, какой у него вес и какое значение следующее в списке.
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
20.01.2015, 19:53 8
Цитата Сообщение от Pearl_lce Посмотреть сообщение
и какое значение следующее в списке
А это-то зачем?
0
Pearl_lce
0 / 0 / 0
Регистрация: 17.10.2014
Сообщений: 9
20.01.2015, 21:12  [ТС] 9
Ну если коротко) То я использую алгоритм мультистек. То есть много списков в стеке в одном массиве. В каждый стек заключены списки соседей для вершин. И соответственно нужно знать следующей элемент списка.

Я не являюсь каким-то крутым программистом, я по образованию экономист. В программировании я самоучка. Собираю мозаику по кусочкам) Что-то отсюда, что-то оттуда)
0
20.01.2015, 21:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.01.2015, 21:12

Список смежности из списка ребер
Ориентированный невзвешенный граф без петель и кратных ребер задан списком ребер. По данному...

Список смежности для графа
Доброго времени суток. Не могли бы вы мне подсказать, как построить список смежности для вершин...

Список смежности и обход графа в ширину
нужно создать список смежности и пройти граф в ширину. как с помощью struct{}; создать список...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru