Влияние върху производителността

Void Graph::topsort()

For (int counter=0; counter
{ v=findNewVertexOfDegreeZero(); if (v==NOT_A_VERTEX)

throw CycleFound(); v.topNum=counter;

for each w adjacent to v w.indegree--;

} }

enqueue. Докато тя не се изпразни, връх се изнася от нея и за свързаните с него се намалява indegree.

Void Graph::topsort()

{ Queue q(NUM_VERTICES);

Int counter=0; Vertex v,w; q.makeEmpty(); for each vertex v

if (v.indegree==0) q.enqueue(v); while (!q.isEmpty())

{ v=q.dequeue(); v.topNum= ++counter; for each w adjacent to v

if (--w.indegree==0) q.enqueue(w);

}

if (counter != NUM_VERTICES) throw CycleFound(); }
Времето за обработка е O(│E│+│V│) при използ. на списъци на съседство,т.е. лин

42. Намиране на най-къс път.Алгоритъм на Дейкастра

Ще разгледаме алгоритъм за намиране на най-къс път при безтегловен граф. Зададен е безтегл. граф G=(V,E) и стартов връх v, търсим най-късия път от v до всички оста-нали върхове в G. Нека разгледаме реш. за графа, показан. Приемаме за стар-тов връх v3. Тогава пътят до v3 е 0. Търсим съседните на v3.Пътят до тях е 1.Избираме един от тях и отново търсим съседи. Пътят вече е 2 и така до изчерпване на всички върхове. Това стратегия на обхождане се нарича обхождане в ширина на графа и се използва при търсене по нива.

Алгоритъм на Дейкстра

Ще използваме същата идея и при граф с тегла. Отново всеки връх ще маркираме с Known=T, след като е обходен. Отново ще натрупваме разст. в dv и ще съхраняваме предшественика в pv. Тази идея за I път е реализирана от Дейкстра през 40-те год. Този алг.е обобщение на предходния и носи името алгоритъм на Дейкстра. Това е типичен пример за greedy algorithm Пр. за такава задача е какви монети трд се върнат до опр.ст-ст, за да бъде броят им мин. Проблем на такива алгоритми е, че не винаги работят. Пример за това са връщането на 15 цента в САЩ, което алгоритъма ще даде като 12+3*1, докато оптималното е 10+5.

Алг.на Дейкстра работи на етапи, като за всеки етап избира връх v с мин.дължина dv, измежду всички, неизползвани до момента и декларира най-късия път от s до v за известен.=> актуализация на ст-стите на dw според теглото на реброто (v,w), т.е. dw = dv + cv,w. Тази актуализация се прави само ако новото разст.е по-късо от същест-вуващото. В противен случай разст.не се променя. Ще разгледаме приложението на алг. за графа, показана на фиг. 6. Отново ще използваме табл.,но този път стартов връх ще бъде v1. Нека проследим отделни-те стъпки. Започваме от стартовия връх v1 и нанасяме разстояние 0 . Маркираме върха за обходен (Known=T). Определяме неговите съседи. Те са v2 и v4. Попълваме табл.за тях, след което маркираме v4 за обходен. Отново определяме съседите на v4: v3, v5, v6 и v7. Попълваме табл.за тях
.Сега избираме v2. Неговите съседи са v4 и v5. От тях само v5 има Known=F.Тъй като дълж.на пътя 10+2 =12 е по-голяма от съществуващата (3), не се правят промени по таблицата.Следващият връх, който ще обработим е v5. Той има само един съсед, който не е обходен: v7. Отново няма да правим
про-мени по таблицата, защото новото разсто-яние 3+6=9 е
по-голямо от 5 (съществува-щото). Следва избор на v3 и корекция на разст.на v6, което става 8 . Сега идва ред на v7. Отново се променя разст.на v6,което става 6.Накрая се обхожда v6, който няма съседи и не води до промяна на разст.,и алг.спира

42. 
    
    Изтегляне 1.47 Mb.
    
    Сподели с приятели: