Хафта: 6 Мавзу: Графларга доир алгоритмлар

Алгоритмни баҳолаш

 ,

Ёмон ҳолатда -  .

Краскал алгоритми.

Ушбу алгоритм 1956 йили Краскал томонидан ишлаб чикилган.

Фараз қиламиз, V = {1, 2, .... n} бўғимлар тўпламидан иборат ва Е қирралар тўпламида аниқланган с нарх функцияси билан берилган G=(V, Е) боғланган граф бўлсин. Крускал алгоритмида G граф учун минимал нархли дарахтлар склетини қуриш G графнинг фақат n та бўғимларидан ташкил топган ва қирралари бўлмаган Т=(V, ø) графдан бошланади. Шундай қилиб, ҳар бир бўғим боғланган (ўзи-ўзи билан) компонент ҳисобланади. Алгоритм бажарилиши вақтида боғланган компонентлар наборига эга бўламиз, аста-секин бирлаштириб дарахтлар склетини ташкиллаштирамиз.

Аста-секин ўсувчи боғланган компонентларни қуришда Е тўпламдан қирралар уларнинг нархи ўсиши тартибида навбатма-навбат текширилади. Агар навбатдаги қирра турли компонентлардаги иккита бўғимни бирлаштирса, у ҳолда бу қирра Т графга қўшилади. Агар бу қирра битта компонентнинг иккита бўғимини бирлаштирса, у ташлаб юборилади, чунки унинг боғланган компонентга қўшилиши цикл ҳосил бўлишига олиб келади. G графнинг барча бўғимлари битта компонентга тегишли бўлса, Т минимал нархли дарахтлар склетини қуриш бу граф учун тугайди.

Мисол

С боғланган компонентлар тўплами керак, бу учун қуйидаги операторлар ишлатилади:

1. MERGE(A, В, С) оператори С набордан А ва В боғланган компонентларни бирлаштиради ва натижани А ёки В га жойлаштиради.

2. FIND(v, С) функцияси С набордан v бўғимни ўз ичига олган компонентнинг номини қайтаради.

3. INITIAL(A, v, С) оператори наборда фақат v бўғимдан иборат А номли компонентни яратади.

Ушбу алгоритм O (M log N + N²) вақтда бажарилади. Қирраларни саралаш учун О(M logN) та операция керак булади. Тугун у ёки бу қисм дарахтга тегишли бўлса, tree_id массив ёрдамида сақланади, бу массивда ҳар бир тугун учун у тегишли бўлган дарахт номери сақланади. Ҳар бир қирра учун О(1) вақтда унинг тугунлари турли дарахтларга тегишли эканлигини аниқланади. Ниҳоят, иккита дарахтни бирлаштириш O (N) вақтда бажарилади. Бирлаштириш оператори O(N) ўтишда бажарилишини ҳисобга олсак, O (M log N + N²) келиб чикади.

Дастур кўриниши қуйидагича булади:

int n, m;

cin >> n >> m;

vector > edges(m, vector(3));

for (int i = 0; i < m; ++i)

cin >> edges[i][1] >> edges[i][2] >> edges[i][0];

sort(edges.begin(), edges.end());

vector comp(n);

for (int i = 0; i < n; ++i)

comp[i] = i;

int ans = 0;

for (auto & edge: edges)

{

int weight = edge[0];

int start = edge[1];

int end = edge[2];

if (comp[start] != comp[end])

{

ans += weight;

int a = comp[start];

int b = comp[end];

for (int i = 0; i < n; ++i)

if (comp[i] == b)

comp[i] = a;

}

}