์ฐ์ ์์ ํ
์ ๋ฐฉ๋ฒ์ ์ด์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
vertex๋ฅผ ํ๊ฐ์ฉ ์ ํํ๋ฉฐ ์ต์ ๋น์ฉ์ edge๋ฅผ ์ฐพ๋ ๋ฐฉ๋ฒ.
decrease-key
์ ๊ฐ๋
์ ์ด์ฉํ๋ฉฐ decrease-key๋ ํ์ฌ ๊ณ์ฐ๋ v๋
ธ๋๊น์ง์ ๊ฑฐ๋ฆฌ๋ณด๋ค ํ์ฌ ๋
ธ๋ u๋ถํฐ v๊น์ง์ ๊ฒฝ๋ก๊ฐ ๋ ์๋ค๋ฉด ๊ฐ์ ๊ฐฑ์ ํด์ฃผ๋ ๊ฒ.
ํน์ง
์์ ์ ์ ๋ถํฐ ์ถ๋ฐํ์ฌ ํด๋น ๋
ธ๋๊น์ง์ ์ต์ ๋น์ฉ์ ๊ธฐ๋กํ๋ ๋ฐฐ์ด์ ์ด์ฉํ์ฌ ๊ตฌํ๋ ๋ฐฉ์
์๋ฃ๊ตฌ์กฐ์ค ํ๋์ธ ์ฐ์ ์์ ํ
๋ฅผ ์ด์ฉํ๋ฉฐ, ์ฐ์ ์์ ํ๋ฅผ ์ด๋ป๊ฒ ๊ตฌํํ๋๊ฐ๊ฐ ์๊ฐ๋ณต์ก๋์ ์ํฅ
Pesudo Code
Copy MST-Prim(G, w, r)
Q = V[G];
for each u โ Q
key[u] = INFINITY;
key[r] = 0;
p[r] = NULL;
while (Q not empty)
u = ExtractMin(Q);
for each v โ Adj[u]
if (v โ Q and w(u,v) < key[v]) //Decrease-key
p[v] = u;
key[v] = w(u,v);
๊ตฌํ ๋ฐฉ๋ฒ
vertex๋ค์ key๊ฐ์ Infinity๋ก ์ด๊ธฐํํ๋ค.
start vertex์ key๊ฐ์ 0์ผ๋ก ์ด๊ธฐํํ๋ค. (์ด๋ค vertex๋ฅผ ์ ํํ๋๋ผ๊ณ MST๊ฐ ๋์จ๋ค.)
ํ์ฌ vertex์ ์ธ์ ํ vertex๋ค ์ค ์ ํํ์ง ์์๊ณ , ๊ฐ์ฅ vertex์ key๊ฐ์ด ์์ vertex์ ์ฐพ๋๋ค. (exract-min = ์ต์๊ฐ ์ถ์ถ
)
ํ์ฌ vertex๋ฅผ ์ ํํ๋ค.
์ธ์ ํ vertex์ค vertex์ key๊ฐ๋ณด๋ค ๊ฐ์ ์ ๊ฐ์ค์น๊ฐ ๋ ์๋ค๋ฉด key๊ฐ์ ๊ฐ์ค์น๋ก ๊ฐฑ์ ํ๋ค. (decrease -key
)
์ธ์ ํ vertex์ค ์ ํํ์ง ์์๊ณ , ๊ฐ์ฅ vertex์ key๊ฐ์ด ์์ vertex๋ฅผ ๊ธฐ์ค์ผ๋ก 3๋ฒ
๋ถํฐ ๋ค์ ๋ฐ๋ณตํ๋ค.
๋ชจ๋ vertex๊ฐ ์ ํ๋์๋ค๋ฉด ๋๋๋ค.
์ธ์ ํ๋ ฌ
์์ ์ค๋ช
ํ 3๋ฒ ๋ฐฉ๋ฒ
์ extract-min์ ์๋์ ๊ฐ์ด ๋ฐฐ์ด๋ก ๊ตฌํํ๋ฉฐ, ๋งค๋ฒ Vํ ๋ฐ๋ณตํ๋ค.
Copy int v = - 1 ; //์ธ์ vertex์ค ๊ฐ์ฅ ์์ ๊ฐ์ค์น๋ฅผ ๊ฐ๋ vertex
int min_key = INFINITY; //์ธ์ vertex์ค ๊ฐ์ฅ ์์ ๊ฐ์ค์น
/* ์ธ์ vertex์ค ๊ฐ์ฅ ์์ ๊ฐ์ค์น๋ฅผ ๊ฐ๋ vertex ์ฐพ๊ธฐ*/
for ( int j = 0 ; j < V; j ++ ) {
if ( ! selected [j] && (min_key > vertex_key [j])) {
v = j;
min_key = vertex_key [j];
}
}
์๋๋ 5๋ฒ ๋ฐฉ๋ฒ
์ผ๋ก ์ธ์ ํ vertex์ค vertex์ key๊ฐ๋ณด๋ค ๊ฐ์ ์ ๊ฐ์ค์น๊ฐ ๋ ์๋ค๋ฉด key๊ฐ์ ๊ฐ์ค์น๋ก ๊ฐฑ์ ํ๋ค.
Copy for ( int j = 0 ; j < V; j ++ ) {
if ( vertex_key [j] > adjMatrix [v][j]) {
vertex_key [j] = adjMatrix [v][j];
}
}
์ธ์ ๋ฆฌ์คํธ
์ธ์ ๋ฆฌ์คํธ๋ ์ธ์ ํ vertex์ ๊ฐ์ค์น๋ฅผ priority queue๋ฅผ ํตํด ์ ์ฅํ๋ค.
๋๋ฌธ์, 3๋ฒ ๋ฐฉ๋ฒ์
exract-min์ ๋งจ์์์ pop์ ์์ผ ์ฐพ์์ฃผ๋ฉด ๋๋ค.
Copy std :: set < II > q; //์ด์งํ์ผ๋ก queue ๋ง๋ค๊ธฐ ( set์ red-black tree๋ก ๋ง๋ค์ด์ง )
auto u = q . begin (); // extract-min
5๋ฒ ๋ฐฉ๋ฒ
์ผ๋ก ์ธ์ ํ vertex์ค vertex์ key๊ฐ๋ณด๋ค ๊ฐ์ ์ ๊ฐ์ค์น๊ฐ ๋ ์๋ค๋ฉด key๊ฐ์ ๊ฐ์ค์น๋ก ๊ฐฑ์ ํ๋ ๋ฐฉ๋ฒ์ ์๋์ ๊ฐ์ด ์ธ์ ํ ๊ฐ์ ์ ๊ฐ์๋งํผ ์ํํ๋ค.
Copy /*selectํ vertex์ ์ธ์ ํ ๊ฐ์ ์ธ e*/
for ( auto e : adjList [ํ์ฌ vertex]) {
/* ์ ํ๋์ง ์์ vertex์ด๊ณ ํด๋น vertex์ key๊ฐ๊ณผ edge์ cost๋ฅผ ๋น๊ตํด cost๊ฐ ๋ ์๋ค๋ฉด*/
if ( ! selected [์ธ์ ํ vertex] && vertex_key [์ธ์ ํ vertex] > ๊ฐ์ค์น) {
q . erase ({ vertex_key [์ธ์ ํ vertex] , e . second}); //๊ฐ์ vertex๋ก ํฅํ๋ ๊ฐ์ ์ค weight๊ฐ ๋ ์์ ๊ฐ์ ์ด ์๋ค๋ฉด ๊ทธ ์ ๊ฐ์ ์ ์ญ์
vertex_key [์ธ์ ํ vertex] = ๊ฐ์ค์น; // vertex key๊ฐ ๊ฐฑ์
q . insert ({๊ฐ์ค์น , ์ธ์ ํ vertex}); //ํ์ ์ฝ์
}
}
์๊ฐ ๋ณต์ก๋
์๊ฐ๋ณต์ก๋๋ ์ด๊ธฐํํ๋๋ฐ O(|V|), MST๊ณ์ฐํ๋๋ฐ O(|V|) * T(extract-min) (๊ฐ์ฅ ์ ์ ๊ฐ ์ถ์ถํ๋๋ฐ ๊ฑธ๋ฆฐ์๊ฐ) + O(|E|) * T(decrease-key) ( key๊ฐ ๋ณ๊ฒฝํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ )์ ๊ฐ๋ค.
๋ฐ๋ผ์, priority-queue๋ฅผ ์ด๋ป๊ฒ ๊ตฌํํ๋์ง์ ๋ฐ๋ผ ์๊ฐ๋ณต์ก๋๊ฐ ๋ฌ๋ผ์ง๋ค.
์ผ๋ฐ ๋ฐฐ์ด๋ก ๊ตฌํํ์ ๊ฒฝ์ฐ T(extract)๊ฐ O(|V|), T(decrease)๋ O(1)๋งํผ ๊ฑธ๋ ค ์ด O(|V^2|)์ด ๊ฑธ๋ฆฐ๋ค.
binary heap(์ด์ง ํ)์ผ๋ก ๊ตฌํํ๋ฉด T(extract)๊ฐ O(lgV), T(decrease)๋ O(lgV)๋งํผ ๊ฑธ๋ ค ์ด O(VlgV) + O(ElgV) ์ด๊ธฐ ๋๋ฌธ์ O((E+V)lgV)๋งํผ ๊ฑธ๋ฆฐ๋ค.
๋ฌด๋ฐฉํฅ ๊ทธ๋ํ์ผ๋ E์ ์ต์๊ฐ์ V-1๋ก ๊ฑฐ์ ๋๋ถ๋ถ์ด |E| > |V| ์ด๋ฏ๋ก O(|E|lg|V|)๋ผ๊ณ ํ ์ ์๋ค.
priority queue๋ฅผ ์ด์ง ํ์ด ์๋ fibonacci heap์ผ๋ก ๊ตฌํํ๋ฉด decrease-key์ ์๊ฐ์ ์ข๋ ์ค์ผ ์ ์๋ค.
decrease-key์๊ฐ์ด O(1)๋งํผ ๊ฑธ๋ฆฌ๊ธฐ ๋๋ฌธ์ O(E+VlgV)๋ผ๊ณ ํ ์ ์๋ค.
O(E) or O(VlgV) ์ธ ์ด์ ๋ ์ต์
์ ๊ฒฝ์ฐ์ E๋ O(V^2)์ด๊ธฐ ๋๋ฌธ์ด๋ค.
๊ตฌํ ์ฝ๋
์๋ ์ฝ๋๋ ์ฌ์ดํด์ด์๋ ๋ฌด๋ฐฉํฅ์ ๊ทธ๋ํ์ด๊ณ , ๊ฐ์ค์น๋ฅผ ๋ฌด์์๋ก ์์ฑํ ๊ทธ๋ํ์ด๋ค.
์์ค์ฝ๋ c++ ( ์ ๊ธฐ / ํผ์น๊ธฐ )
Copy #include <time.h> //์๊ฐ ์ธก์
#include <algorithm> //for_each
#include <cstdlib> //rand
#include <ctime> //time
#include <iostream>
#include <set>
#include <vector>
#define INFINITY 2147483647
#define II std :: pair <int , int> // first = weight, second = dest
typedef struct edge {
int src; //์ถ๋ฐ vertex
int dest; //๋์ฐฉ vertex
int weight; //๊ฐ์ค์น(๋น์ฉ)
} edge ;
class Graph {
private :
edge e;
public :
Graph ( int src = 0 , int dest = 0 , int weight = 0 ) {
this -> e . src = src;
this -> e . dest = dest;
this -> e . weight = weight;
}
int getSrc () { return this -> e . src; }
int getDest () { return this -> e . dest; }
int getWeight () { return this -> e . weight; }
};
void CalcTime ();
void randomPush (std :: vector < Graph > & ); // graph์ ์ฌ์ดํด ์๋ ์ฐ๊ฒฐ๊ทธ๋ํ cost๊ฐ ๋ฌด์์ ์์ฑ
void print_edge_info (std :: vector < Graph >); // graph ๊ฐ์ ๋ค ๋ณด๊ธฐ
int prim_adjList_heap (std :: vector < Graph > & , std :: vector <std :: vector < II >> ,
int ); // Adj list์ priority queue ์ด์ฉํด ๊ตฌํ --> set์ red-black-tree
void make_adj_list (std :: vector < Graph > , std :: vector <std :: vector < II >> & ); //์ฃผ์ด์ง ๊ทธ๋ํ๋ฅผ ์ธ์ ๋ฆฌ์คํธ๋ก ํํ
int prim_adjMatrix (std :: vector < Graph > & , std :: vector <std :: vector < int >> , int ); // Adj matrix๋ก ๊ตฌํ
void make_adj_matrix (std :: vector < Graph > , std :: vector <std :: vector < int >> & ); //์ฃผ์ด์ง ๊ทธ๋ํ๋ฅผ ์ธ์ ํ๋ ฌ๋ก ํํ
int V; // vertex ๊ฐ์
clock_t start , finish , used_time = 0 ; //์คํ ์๊ฐ ์ธก์ ์ ์ํ ๋ณ์
int main () {
std :: vector < Graph > g; // graph g
int minimum_weight = 0 ; // minimum cost
std :: vector < std :: vector < II >> adjList;
std :: vector < std :: vector <int>> adjMatrix;
randomPush (g); //๊ฐ์ random ์ฝ์
print_edge_info (g); // edge info print
make_adj_list (g , adjList); //์ฃผ์ด์ง ๊ทธ๋ํ๋ฅผ ์ธ์ ๋ฆฌ์คํธ๋ก ๋ง๋ค๊ธฐ
make_adj_matrix (g , adjMatrix); //์ฃผ์ด์ง ๊ทธ๋ํ๋ฅผ ์ธ์ ํ๋ ฌ๋ก ๋ง๋ค๊ธฐ
start = clock ();
minimum_weight = prim_adjMatrix (g , adjMatrix , 0 ); //์ธ์ ํ๋ ฌ์ ์ด์ฉํ prim's algorithm (0๋ฒ๋
ธ๋๋ฅผ ์ฒซ ๋
ธ๋๋ก ์์)
// minimum_weight = prim_adjList_heap(g, adjList, 0); //์ธ์ ๋ฆฌ์คํธ๋ฅผ ์ด์ฉํ prim's algorithm (0๋ฒ๋
ธ๋๋ฅผ ์ฒซ ๋
ธ๋๋ก ์์)
finish = clock ();
std :: cout << "\nminimum cost : " << minimum_weight << std :: endl;
CalcTime ();
return 0 ;
}
int prim_adjList_heap (std :: vector < Graph > & g , std :: vector <std :: vector < II >> adjList , int start) {
int sum = 0 ;
std :: set < II > q; //์ด์งํ์ผ๋ก queue ๋ง๋ค๊ธฐ ( set์ red-black tree๋ก ๋ง๋ค์ด์ง )
std :: vector <int> vertex_key (V , INFINITY); // vertex์ ์ต์ weight๊ฐ ๊ณ์ฐ
std :: vector <bool> selected ( g . size () , false ); //์ ํ๋ vertex์ธ๊ฐ
vertex_key [start] = 0 ;
q . insert ( II ( 0 , start)); //์์ ๋
ธ๋ ๊ฐ์ค์น 0์ผ๋ก ์์
std :: cout << "\nroute" ;
/*vertex ์๋งํผ ๋ฐ๋ณตํ๋ค
while๋์ for(int i=0; i < V ; i++)๋ก ํด๋ ๋ฌด๋ฐฉ
*/
while ( ! q . empty ()) {
/*extract min*/
int select_key = q . begin () -> second;
int min_of_key = q . begin () -> first;
q . erase ( q . begin ());
if ( selected [select_key]) {
std :: cout << " NOT MST" << std :: endl;
exit ( 1 );
}
sum += min_of_key;
selected [select_key] = true ;
std :: cout << "dest : " << select_key << " (dis : " << vertex_key [select_key] << ")" << std :: endl;
/*decrease key*/
for ( auto e : adjList [select_key]) {
if ( ! selected [ e . second] && vertex_key [ e . second] > e . first + vertex_key [select_key]) {
q . erase ({ vertex_key [ e . second] , e . second}); //๊ฐ์ ๋
ธ๋๋ก ํฅํ๋ ๊ฐ์ ์ค weight๊ฐ ๋ ์์ ๊ฐ์ ์ด ์๋ค๋ฉด ๊ทธ ์ ๊ฐ์ ์ ์ญ์
q . insert ({ e . first , e . second}); //ํ์ ์ฝ์
vertex_key [ e . second] = e . first + vertex_key [select_key];
}
}
}
std :: cout << std :: endl;
return sum;
}
void make_adj_list (std :: vector < Graph > g , std :: vector <std :: vector < II >> & adj) {
adj . resize (V);
bool isEdge;
for ( int i = 0 ; i < g . size (); i ++ ) {
isEdge = false ;
int src = g [i] . getSrc ();
int dest = g [i] . getDest ();
int weight = g [i] . getWeight ();
/*๋์ผ vertex๋ก ํฅํ๋ ๊ฐ์ ์ค ๊ฐ์ฅ ์์ ๊ฐ๋ง๊ฐ์ง๊ณ ์ธ์ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค๊ธฐ ์ํ ์ฝ๋*/
if ( adj [src] . empty ()) {
adj [src] . push_back ({weight , dest});
} else {
for ( int j = 0 ; j < adj [src] . size (); j ++ ) {
if ( adj [src][j] . second == dest) {
isEdge = true ;
if ( adj [src][j] . first > weight) {
adj [src][j] . first = weight;
}
}
}
if ( ! isEdge) adj [src] . push_back ({weight , dest});
}
isEdge = false ;
if ( adj [dest] . empty ()) {
adj [dest] . push_back ({weight , src});
} else {
for ( int j = 0 ; j < adj [dest] . size (); j ++ ) {
if ( adj [dest][j] . second == src) {
isEdge = true ;
if ( adj [dest][j] . first > weight) {
adj [dest][j] . first = weight;
}
}
}
if ( ! isEdge) adj [dest] . push_back ({weight , src});
}
}
}
int prim_adjMatrix (std :: vector < Graph > & g , std :: vector <std :: vector < int >> adjMatrix , int start) {
int sum = 0 ;
std :: vector <int> vertex_key (V , INFINITY); // vertex์ ์ต์ weight๊ฐ ๊ณ์ฐ
std :: vector <bool> selected ( g . size () , false ); //์ ํ๋ vertex์ธ๊ฐ
vertex_key [start] = 0 ; //์์๋
ธ๋ key๊ฐ 0์ผ๋ก ์์
std :: cout << "\nroute" ;
/*vertex ์๋งํผ ๋ฐ๋ณตํ๋ค*/
for ( int i = 0 ; i < V; i ++ ) {
int select_idx = - 1 ; //์ธ์ vertex์ค ๊ฐ์ฅ ์์ ๊ฐ์ค์น๋ฅผ ๊ฐ๋ vertex
int min_key = INFINITY; //์ธ์ vertex์ค ๊ฐ์ฅ ์์ ๊ฐ์ค์น
/* ์ธ์ vertex์ค ๊ฐ์ฅ ์์ ๊ฐ์ค์น๋ฅผ ๊ฐ๋ vertex ์ฐพ๊ธฐ*/
for ( int j = 0 ; j < V; j ++ ) {
if ( ! selected [j] && (min_key > vertex_key [j])) {
select_idx = j;
min_key = vertex_key [j];
}
}
/*ํ์ฌ ์ฝ๋์์๋ ์ฐ๊ฒฐ์๋ ๊ทธ๋ํ๋ ์ฃผ์ด์ง์ง ์๊ธฐ ๋๋ฌธ์
์์ด๋ ๋ฌด๋ฐฉํ์ง๋ง ๋ง์ฝ์ ์ํ ์๋ฌ์ฒ๋ฆฌ*/
if (select_idx == - 1 ) {
std :: cout << "Not MST" << std :: endl;
exit ( 1 );
}
selected [select_idx] = true ;
sum += min_key;
std :: cout << " -> " << select_idx << "(cost : " << min_key << ")" ;
/*์ธ์ vertex์ weight๊ฐ vertex_key๊ฐ๋ณด๋ค ์๋ค๋ฉด key๊ฐ ๊ฐฑ์ */
for ( int j = 0 ; j < V; j ++ ) {
if ( ! selected [j] && vertex_key [j] > adjMatrix [select_idx][j]) {
vertex_key [j] = adjMatrix [select_idx][j];
}
}
}
std :: cout << std :: endl;
return sum;
}
void make_adj_matrix (std :: vector < Graph > g , std :: vector <std :: vector < int >> & adj) {
adj . assign (V , std :: vector < int >(V , INFINITY));
for ( int i = 0 ; i < g . size (); i ++ ) {
int src = g [i] . getSrc ();
int dest = g [i] . getDest ();
int weight = g [i] . getWeight ();
if ( adj [src][dest] > weight) {
adj [src][dest] = weight;
}
if ( adj [dest][src] > weight) {
adj [dest][src] = weight;
}
}
}
/*vertex์ ์
๋ ฅ๋ฐ์ ํ ๊ทธ๋ํ ๊ฐ์ ๊ฐ์ค์น random ์ฝ์
*/
void randomPush (std :: vector < Graph > & g) {
std :: cout << "create number of Vertex : " ;
std :: cin >> V;
srand (( unsigned int ) time ( NULL ));
for ( int i = 0 ; i < V - 1 ; i ++ ) {
g . push_back ( Graph (i , i + 1 , rand () % 1000 ));
for ( int j = i + 1 ; j < V; j ++ ) {
g . push_back ( Graph (i , j , rand () % 1000 ));
}
}
for ( int i = ( rand () % 3 ); i < V - 1 ; i += ( rand () % 10 )) {
g . push_back ( Graph (i , i + 1 , rand () % 1000 ));
for ( int j = i + 1 ; j < V; j += ( rand () % 10 )) {
g . push_back ( Graph (i , j , rand () % 1000 ));
}
}
}
void print_edge_info (std :: vector < Graph > g) {
std :: cout << "edge info : \n" ;
std :: for_each ( g . begin () , g . end () , []( Graph a) {
std :: cout << "src : " << a . getSrc () << " desc : " << a . getDest () << " weight : " << a . getWeight () << std :: endl;
});
}
//์คํ ์๊ฐ์ ์ธก์ ๋ฐ ์ถ๋ ฅํ๋ ํจ์
void CalcTime () {
used_time = finish - start;
printf ( "\n*********** result **********\n time : %lf sec\n" , ( double )(used_time) / CLOCKS_PER_SEC);
}