Задачи за самостоятелна подготовка

Топологично сортиране

Топологично сортиране

от Трифон Трифонов -
Number of replies: 0

Даден е граф с върхове - естествени числа, представен със списък с елементи от вида [<връх> <съсед 1> <съсед 2> ...]. Например:

[[a,c,d],[b,d],[c,e],[d],[e,d]]

Да се напише предикат topol_sort(G,L), който по даден граф връща топологично сортираните му върхове. Топологично сортиране на върховете наричаме линейна наредба на върховете (списък), в който всеки връх предхожда наследниците си. Не всеки граф може да се сортира топологично - в такъв случай предикатът трябва да връща No. Сортирането не е еднозначно - търси се само едно решение. По-предизвикателна задача е да напишете генератор, който генерира всички топологични сортирания на даден граф.