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