Разлика између Крускала и Прим

Крускал вс Прим

У рачунарској науци, Примов и Крускалов алгоритам су похлепни алгоритам који проналази минимално распон стабла за повезани непондерирани граф. Стабло које се распоређује је подграф графикона тако да је сваки чвор графикона повезан стазом, која је стабло. Свако стабло има расположиву тежину, а најмања могућа тежина / трошак свих опружних стабала је минимално распорено дрво (МСТ).

Више о Примову алгоритму

Алгоритам је развио чешки математичар Војтецх Јарник 1930. године, а касније самостално рачунарски рачунар Роберт Ц. Прим 1957. године открио га је Едсгер Дијкстра 1959. Алгоритам се може навести у три кључна корака;

С обзиром на повезани графикон с н чворова и одговарајућом тежином сваке ивице,

1. Изаберите произвољни чвор из графикона и додајте га у стабло Т (које ће бити први чвор)

2. Размотрите тежину сваке ивице спојене на чворове на дрвету и изаберите минимум. Додајте ивицу и чвор на другом крају стабла Т и уклоните ивицу с графикона. (Изаберите било који уколико постоје два или више минимума)

3. Поновите корак 2 док се н-1 ивице не додају у дрво.

У овој методи, стабло започиње једним произвољним чвором и шири се од тог чвора надаље са сваким циклусом. Дакле, да би алгоритам правилно радио, граф мора бити повезан графикон. Основни облик алгоритма Прим има временску сложеност од О (В²).

Више о Крускал-овом алгоритму

Алгоритам који је развио Јосепх Крускал појавио се у зборницима Америчког математичког друштва 1956. Крускал алгоритам се такође може изразити у три једноставна корака.

С обзиром на графикон с н чворова и тежином сваке ивице,

1. Изаберите лук са најмањом тежином целог графикона и додајте га у стабло и избришите из графа.

2. Од преосталог одаберите најмање пондерисану ивицу, на начин који не формира циклус. Додајте ивицу дрвету и избришите са графа. (Изаберите било који уколико постоје два или више минимума)

3. Поновите поступак у кораку 2.

У овој методи алгоритам започиње са најмање пондерисаном ивицом и наставља са одабиром сваке ивице током сваког циклуса. Према томе, у алгоритму граф не мора бити повезан. Крускал-ов алгоритам има временску сложеност О (логВ)

Која је разлика између Крускаловог и Примовог алгоритма?

• Примов алгоритам иницијализира се чвором, док се Крускалов алгоритам покреће ивицом.

• Примови алгоритми распону од једног чвора до другог, док Крускалов алгоритам бира ивице на начин да положај ивице није заснован на последњем кораку.

• У Примовом алгоритму граф мора бити повезан графикон, док Крускал-ови могу функционирати и на неповезаним графовима.

• Примов алгоритам има временску сложеност од О (В²), а Крускалова временска сложеност је О (логВ).