Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
DmitryM5
Maria ->∞
106 / 86 / 44
Регистрация: 27.08.2013
Сообщений: 1,232
Записей в блоге: 1
1

Задача топологическая сортировка графа

10.10.2014, 19:42. Просмотров 1232. Ответов 5
Метки нет (Все метки)

Добрый вечер,предположим задан взвешенный,ориентированный,ациклический граф в виде матрицы смежности.
Матрица соответственно может быть задана некорректно с точки зрения топологической сортировки.
Т.е. из большего номера вершины идет путь к вершине с меньшим номером.
Топологическая сортировка помогает избежать этого,правильно нумеруя вершины,однако вопрос в том,что делать с матрицей,как её поменять?
Нужно ведь сохранить веса ребер,с правильной нумерацией теперь.
Ведь нумерация может в корне поменяться,и казалось бы простых swap'ов недостаточно!
Ниже пример:дан граф с неверной нумерацией,и матрица,вопрос как получить правую матрицу?
В num хранится правильная нумерация, по матрицам вроде легко,видно что допустим чтобы получить число 0.2([0][1]), Нужно найти индексы штрих в первой матрице [0'][1'].
Однако как получить доступ к ним с помощью enum непонятно...
Прошу помочь!
0
Миниатюры
Задача топологическая сортировка графа  
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.10.2014, 19:42
Ответы с готовыми решениями:

Топологическая сортировка графа
Написал программу топологически сортирующую граф с помощью обхода в ширину. Сдал её на информатиксе...

Неверно работает топологическая сортировка
Привет. Я написал топологическую сортировку, решил проверить на тестовом примере его, но оно не...

Топологическая сортировка графа
Задали задание, неделю пытаюсь сделать и все никак не выходит, топологическая сортировка из книгу...

Топологическая сортировка графа
Здравствуйте, у меня есть код сортировки, но он слишком громоздкий, помогите его сделать более...

Топологическая сортировка графа
Здравствуйте! Помогите, пожалуйста. Пишу программу для поиска путей на графах между всеми парами...

5
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 783
10.10.2014, 19:52 2
не надо трогать матрицу. топологическая сортировка даст вам правильную перестановку вершин. пользуйтесь ей каждый раз при обращении к матрице.
0
DmitryM5
Maria ->∞
106 / 86 / 44
Регистрация: 27.08.2013
Сообщений: 1,232
Записей в блоге: 1
10.10.2014, 20:00  [ТС] 3
Цитата Сообщение от salam Посмотреть сообщение
не надо трогать матрицу. топологическая сортировка даст вам правильную перестановку вершин. пользуйтесь ей каждый раз при обращении к матрице.
Ну допустим я и не собираюсь перестраивать матрицу,но как ей пользоваться?!
На примере показано обращение к элементу со значение 0.2, которое невозможно просто через num[i] num[j]...
0
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 783
10.10.2014, 20:21 4
топологическая сортировка породила перестановку {3, 0, 1, 2}, то есть вы отобразили
0 -> 1 // 0 теперь 1-ый элемент массива
1 -> 2 // 1 теперь 2-ой элемент
2 -> 3 // ...
3 -> 0 // ...
ну вот у вас в новой матрице клетка [0][1] - это то же самое, что и клетка [1][2] в старой.
1
DmitryM5
Maria ->∞
106 / 86 / 44
Регистрация: 27.08.2013
Сообщений: 1,232
Записей в блоге: 1
10.10.2014, 20:28  [ТС] 5
Цитата Сообщение от salam Посмотреть сообщение
топологическая сортировка породила перестановку {3, 0, 1, 2}, то есть вы отобразили
0 -> 1 // 0 теперь 1-ый элемент массива
1 -> 2 // 1 теперь 2-ой элемент
2 -> 3 // ...
3 -> 0 // ...
ну вот у вас в новой матрице клетка [0][1] - это то же самое, что и клетка [1][2] в старой.
Да вроде понял,ну тогда нужно искать в массиве числа 0,1 и возвращать их индексы...
По другом нельзя обратиться к ним?
0
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 783
10.10.2014, 20:38 6
Лучший ответ Сообщение было отмечено DmitryM5 как решение

Решение

нужно один раз составить обратную перестановку и пользоваться ей.
топсорт дал вам массив a[0] = 3, a[1] = 0, a[2] = 1, a[3] = 2.
обратная соответственно p[0] = 1, p[1] = 2, p[2] = 3, p[3] = 0.
делается это за один проход по массиву a[].
1
10.10.2014, 20:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.10.2014, 20:38

Топологическая сортировка
Требуется организовать топологическую сортировку на примере списка изучаемых дисциплин.Список...

Топологическая сортировка на Си!!!!
Народ!Помогите хоть кто-нибудь с курсовой работой на Си!!! Мне нужно сделать программу на тему...

Топологическая сортировка
Нужно расположить вершины графа в правильном порядке с помощью смежной матрицы, с использованием...


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

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

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