Професионална програма
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
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