Влияние върху производителността
Изтегляне 1.47 Mb.
|
Свързани:
saap conspect
Топологично сортиранеВ ацикличен ориентиран граф можем да номериране върховете така, че за всяко ребро (v,w), v да предшества w. Това се нарича топологично сортиране. За един граф може да имаме няколко топологични подредби. Пример за такава подредба може да бъде пътна карта. Топологично сортиране не съществува, ако в графа има цикли, защото за два върха v и w в един цикъл, v предшества w и w предшества v. Намирането на топологична подредба може да се сведе до построяване на линеен списък Z от върховете на графа, такъв че за , ако , то v предхожда w в Z. Множеството от всички възможни Z е пълно топологично сортиране. Пример: v1,v2,v5,v4,v3,v7,v6, както и v1,v2,v5,v4,v7,v3,v6 са две топологични подредби. Алгоритъмът първо открива връх без входящи ребра. После го премахва заедно със ребрата от него. Тази операция се повтаря докато не се изчерпи списъка с върховете без входящи ребра. Псевдокодът показва неговата реализация. Функция findNewVertexOfDegreeZero() сканира масива за връх с indegree=0, на който до момента не е присвоено топологично номериране. NOT_A_VERTEX се получава от функцията, ако няма такъв връх, т.е. налице е цикъл. Ф-ята заема O(│V│) време и след като се изпълява в цикъл за всички върхове, сложността ще бъде O(│V2│). Подобрение на алгоритъма: при рядък граф са малко върховете, чиито indegree ще се променят след всяка итерация. Затова няма смисъл да обхождаме всички. Можем да запазим всички неизползвани в топологичната подредба до момента върхове с indegree=0 в отделен масив. Тогава ф-ята ще работи само с върхове от този масив. При това когато един връх стане с indegree=0 влиза в масива. Най-добре вместо масив да се ползва стек или опашка. Всички върхове с indegree=0 се поставят в празната, за начало, опашка линейно. По същият начин стои и задачата за търсене на наследници. Проблем възниква при търсене на предшественици: няма връзка в списъка и трябва да се сканират всички списъци. В този случай е по-добре да се използват двусвързани списъци.Съхраняването може да бъде и в хеш-таблица, защото всеки връх на графа има уникално име и ще бъде ключа в хеша.Информацията за всеки връх ще съхраняваме в обект от тип Vertex. Тя задължително включва име на върха, което трябва да бъде уникално. Останалите параметри са опционни, в зависимост от алгоритъма, който решаваме. Всеки от представените по-нататък алгоритми е разработен с псевдокод, за да бъде представен по-ясно и да позволи реализация на различен език за програмиране. При това ще считаме, че графът е прочетен и зареден в паметта. Изтегляне 1.47 Mb. Сподели с приятели:
|