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

Ще търсим мин.обхващащо дърво в неори-ентиран граф. Зад.има смисъл и за ориен-тиран граф, но там алг.е по-труден. За да-ден граф G,
мин.обхващащо дърво е дърво-то, изградено от дъги на графа,
които свър-зват върховете му на мин.цена. Мин.обхва-щащо
дърво съществува само,ако графа е свързан. Ще работим при това ограниче-ние. Пр. окабеляване на жилища.

минималното обхващащо дърво има │V│-1 ребра. За всяко мин.обхващащо дърво T, ако ребро (v,w), което не съществува в T се добави, се създава цикъл. Изтриването на всяко ребро от цикъла, възстановява мин. обхващащо дърво. Цената на мин.обхва-щащо дърво е толкова по-ниска, колкото по по-ниска е цената на изграждащите го ребра, следователно при изграждането на мин.обхващащо дърво трябва да добавяме ребро с мин.стойност. Ще разгледаме два алг.,които се различават по избора на ребро с минимална стойност

Алгоритъм на Прим (Prim)

Работим на етапи. На всеки етап взимаме един връх v от дървото за корен, добавяме друг w от невключените до момента и

асо-циираме ребро в дървото. Измежду всички ребра (v,w), за които v е от дървото, а w не е, избираме това, което има мин.цена. На фиг.е показано как работи алг.с начало v1. В нач.момент v1 е дървото и на всеки етап добавяме по един връх и едно ребро Алг.е подобен на този на Дейкстра.Както и преди ще поддържаме d_v, p_v и Known. d_v е мин.тегло на реброто (v,w), където w е
пре-дшественика на v с Known=T. p_v съдържа последния връх
w,който е променил d_v.Ос-таналата част от алг.е същата. Единствено се променя актуализацията на d_v: след избор на връх v, за всички съседи w с Known=F на v, d_w=min(d_w,c_v,w).
Нач.на алг. е показано на фиг. 30.На фиг. 31 е избран върха v1, а за v2, v3 и v4 са актуализирани d_v и p_v. Следващият избран връх е v4. Всички останали върхове са му съседи. V1 се изключва от разглеждането, защото има Known=T, информацията за v2 не се променя, защото d_v =2, а стойността на реброто (v4, v2) е 3. Всички останали върхове се актуализират (фиг. 32).
Следващият избран връх е v2. Неговият избор не води до промяна на d_v. По-нататък избираме v3. При това се променя d_v на v6, както е показано на фиг. 33. Фиг. 34 показва резултата след избор на v7, при което се променя d_v за v6 и v5. След избор на v6 и v5, алг.приключва своята работа. Крайният резултат е показан на фиг. 35. Ребрата на мин. обхващащо дърво се получават от таблицата и са както следва: (v2, v1), (v3, v4), (v4, v1), (v5, v7), (v6, v7), (v7, v4). Общата цена е 16

Изтегляне 1.47 Mb.

Сподели с приятели: