Софтуерно Инженерство
Loading...
+ Нов въпрос
Ivaylo.Goranov avatar Ivaylo.Goranov 68 Точки

[Homework] Advanced Graph Algоrithms - Как да построя списък на наследниците от списък на ребрата?

Здравейте,

Въпросът ме интересува по принцип, но текущо ми трябва за първа задача от домашното по Advanced Graph Algоrithms. Та как да съзадм списък на възлите-наследници (Adjacency List), имайки списък на ребрата (Edge List)?
Модификацията на алгоритъма на Прим, която прилагам при първа задача от домашното, ползва и двата типа списъци. Списъкът на ребрата е ясен - него го построявам от входа (дори правя два отделни - на свързаните и несързаните  в "мрежата" ребра). Пробвах различни варианти, но така и не успях да създам изцяло пълен списък на наследниците. А иначе задачата ми работи с "hardcoded" стойности, но трябва да я направя да работи и с вход от конзолата. 
Ще бъда благодарен на съвет относно проблема ми. Може и под формата на алгоритъм или насоки, не нужно да е готов код. За мое съжаление аз не успях. И в интернет нищо не намерих по въпроса.

0
Структури от данни и алгоритми 02/11/2015 23:14:26
Innos avatar Innos SoftUni Team 419 Точки
Best Answer

Според мене колега е много просто, както сам каза имаш всички ребра, автоматично това означава че имаш и всички наследници, ребро е просто връзка между родител - наследник. Да не би да те затруднява факта че ребрата са ненасочени?, ненасочено ребро просто значи че имаш 2 насочени ребра примерно реброто 4<-->6 показва че 4 има наследник 6 и че 6 има наследник 4, не би трябвало да те затруднява да постройш структура която показва всеки възел и наследниците му с тази информация. Помисли каква структура от данни ще ти позволи да запазиш всеки възел и наследниците му по някакъв обвързан начин.

0
03/11/2015 01:23:42
Ivaylo.Goranov avatar Ivaylo.Goranov 68 Точки

Справих се. Благодаря за отговора. Структурата от данни е матрица от тип списък, т.е. List<int>[]. И за списъка с ребрата ползвам същата структура от данни.
Обхождам списъка (матрицата) с ребрата веднъж (по цялата дължина на матрицата) по първия елемент от всеки списък като родител и в списъка с наследниците за този родител поставям като наследник втория елемент от всеки списък от матрицата с ребрата. Аналогичното правя за втория елемент от всеки отделен списък в матрицата държаща инфо за ребрата. Станаха два цикъла така и вероятно има и по-лесен начин, но поне работи. Тествах с примерите от задачата.

0
03/11/2015 09:59:37
krach avatar krach 65 Точки

По списъка с ребрата List<Edge> го обхождам елемент по елемент и съответно създавам Речник със ключ конкретния връх, а като стойност пазя List<Edge> в който добавям конкретното ребро. За всеки елемент правя 2 проверки дали двата върха фгигурират в речника и ако не ги добавям. Например:
Имаме лист от ребра
List<Edge> edges:
0, 1, 10 - ребрео между връх 0 и връх 1 с тежест 10
0, 2, 5 - ребро между връх 0 и връх 2 с тежест 5
1, 3, 20 - ....
2, 3, 20 - ....
Взимам първия елемент 0, 1, 10
Проверявам в речника дали имам ключ 0 ако няма го добавям и във стойността му добавям 0, 1, 10
Проверявам в речника дали има ключ 1 ако няма го добавям и в стойността му добавям 1, 0, 10
Съответно като стигна до елемента 1, 3, 20 проверявам дали има ключ 1, имам и в стойността добавям 1, 3, 20

1
Ivaylo.Goranov avatar Ivaylo.Goranov 68 Точки

Мерси за обяснението. Този подход е използван в демо примера към лекцията за Алгоритъма на Прим. Не ми беше много ясен, понеже се създава клас "Edge" - още не ми е съвсем ясна материята за създаване на обекти. Но благодарение на обяснението ти ми се изясни повече. Аз предпочетох да ползвам  List<int>[].

0