Кіріспе
Минималды аралық ағашты табу әдісі
Компьютерлік ғылымда Прим алгоритмі – салмақты бағытталмаған граф үшін минималды аралық ағашты табуға арналған ашкөз алгоритм. Бұл, әр төбесін қамтитын ағаш құрайтын қабырғалардың кіші жиынтығын табуды білдіреді, мұнда ағаштағы барлық қабырғалардың жалпы салмағы ең төменгі деңгейге дейін азайтылады. Алгоритм осы ағашты кездейсоқ бастау төбесінен бірден бір төбеге дейін құрастыру арқылы жұмыс істейді, әр қадамда ағаштан басқа төбеге ең арзан байланысты қосады. Алгоритмді 1930 жылы чех математигі Войтех Ярник әзірледі, ал кейіннен 1957 жылы компьютерлік ғалым Роберт С. Прим және 1959 жылы Эдсгер В. Дейкстра қайта ашып, жариялады. Сондықтан оны кейде Ярник алгоритмі, Прим–Ярник алгоритмі, Прим–Дейкстра алгоритмі немесе DJP алгоритмі деп те атайды. Бұл мәселе үшін танымал басқа алгоритмдерге Крускал алгоритмі және Борувка алгоритмі кіреді. Бұл алгоритмдер мүмкін байланыссыз графтардағы минималды жаю орманын табады; ал Прим алгоритмінің ең қарапайым түрі тек байланысқан графтардағы минималды жаю ағаштарын табады. Дегенмен, Прим алгоритмін графтың әрбір байланысқан компоненті үшін жеке-жеке орындау арқылы, оны минималды жаю орманын табу үшін де қолдануға болады. Асимптотикалық уақыт күрделілігі тұрғысынан, бұл үш алгоритм сирек графтар үшін бірдей жылдам, бірақ басқа, күрделірек алгоритмдерге қарағанда баяу.
or the DJP algorithm. Other well known algorithms for this problem include Kruskal's algorithm and Borůvka's algorithm. These algorithms find the minimum spanning forest in a possibly disconnected graph; in contrast, the most basic form of Prim's algorithm only finds minimum spanning trees in connected graphs. However, running Prim's algorithm separately for each connected component of the graph, it can also be used to find the minimum spanning forest. In terms of their asymptotic time complexity, these three algorithms are equally fast for sparse graphs, but slower than other more sophisticated algorithms.
Дұрыс екендігін растау
P байланысқан, салмақталған граф болсын. Прим алгоритмінің әрбір итерациясында субграфтағы төбемен, субграфтың сыртындағы төбеге жалғастыратын қабырға табылуы керек. P байланысқандықтан, әр төбеге әрқашан жол болады. Прим алгоритмінің Y нәтижесі – ағаш, себебі Y ағашына қосылған қабырға мен төбе байланысқан. Y1 болсын, P графының ең кішкентай аралықтағы ағашы. Егер Y1=Y болса, онда Y – ең кішкентай аралықтағы ағаш. Әйтпесе, e болсын, Y ағашының құрылысы кезінде қосылған, бірақ Y1 ағашында жоқ алғашқы қабырға, ал V – e қабырғасына дейін қосылған қабырғалармен байланысқан төбелер жиыны. Онда e қабырғасының бір ұшы V жиынында, ал екіншісі – жоқ. Y1 ағашы P графының өріс ағашы болғандықтан, Y1 ағашында осы екі соңғы төбелерді біріктіретін жол бар. Бұл жолмен жүргенде, V жиынындағы төбеден V жиынында жоқ төбеге жалғасатын f қабырғасын кездестіруге болады. Енді, Y ағашына e қабырғасы қосылған кезде, f қабырғасы да қосылуы мүмкін еді, және егер оның салмағы e-ден кем болса, e қабырғасының орнына қосылар еді. f қабырғасы қосылмағандықтан, біз мынаны қорытындылаймыз: Y2 ағашы – f қабырғасын алып тастау және Y1 ағашына e қабырғасын қосу арқылы алынған граф. Y2 ағашы байланысқан, Y1 ағашымен бірдей қабырға санына ие, және оның қабырғаларының жалпы салмағы Y1 ағашынан артық емес екенін көрсету оңай, сондықтан ол да P графының ең кішкентай аралықтағы ағашы болып табылады және ол V жиынын құру кезінде қосылған e қабырғасын және барлық қабырғаларды қамтиды. Жоғарыдағы қадамдарды қайталасақ, ақырында Y ағашына сәйкес келетін P графының ең кішкентай аралықтағы ағашын аламыз. Бұл Y – ең кішкентай аралықтағы ағаш екенін көрсетеді. Ең кішкентай аралықтағы ағаш, субөңірдің бірінші кіші жиынының кішірек X кіші жиынына дейін кеңеюіне мүмкіндік береді, біз оны ең кішкентай деп есептейміз.
Let tree Y2 be the graph obtained by removing edge f from and adding edge e to tree Y1. It is easy to show that tree Y2 is connected, has the same number of edges as tree Y1, and the total weights of its edges is not larger than that of tree Y1, therefore it is also a minimum spanning tree of graph P and it contains edge e and all the edges added before it during the construction of set V. Repeat the steps above and we will eventually obtain a minimum spanning tree of graph P that is identical to tree Y. This shows Y is a minimum spanning tree. The minimum spanning tree allows for the first subset of the sub region to be expanded into a smaller subset X, which we assume to be the minimum.
Параллель алгоритм
Prim алгоритмінің негізгі циклы өзінен-өзі тізбекті болып келеді, демек оны параллельдеу мүмкін емес. Дегенмен, циклдарды жасамастан ең төмен салмақты келесі қабырғаны анықтайтын ішкі циклды қолдағы процессорлар арасында төбелер мен қабырғаларды бөліп параллельдеуге болады. Бұл келесі псевдокодта көрсетілген. Бұл алгоритм әдетте таратылған жүйелерде іске асырылуы мүмкін. Оның орындалу уақыты , егер азайту және тарату операцияларын тұрақты уақытта орындауға болады деп есептесек. Бірақ, таратылған ең аз қамтитын ағаш мәселесін тиімдірек шешу үшін одан да күрделі алгоритмдердің бар екенін ескеру керек.