圖算法
一 PRIM算法與DIJKSTRA算法
兩個(gè)算法之間都有相似性，都用到了堆結(jié)構(gòu)，都是使用了貪心性質(zhì)，所以容易混淆。
二 PRIM算法
該算法定義一個(gè)數(shù)組key[] ,key[i]表示i節(jié)點(diǎn)到樹(shù)中某一節(jié)點(diǎn)最小的距離。
思想：初始時(shí)生成樹(shù)為一個(gè)空樹(shù)，而堆Q為一個(gè)滿(mǎn)堆，所有的節(jié)點(diǎn)均在堆中。
首先置key[r]=0,然后執(zhí)行EXTRACT_MIN(Q) 函數(shù)，從堆中取出key[j]最小的元素。
然后對(duì)所有與節(jié)點(diǎn)j相鄰的節(jié)點(diǎn)i，判斷w[i][j] < key[i] ，若小于則更新key[i]。
注意更新完之后需要對(duì)key[i]重新執(zhí)行siftup()操作，對(duì)堆進(jìn)行調(diào)整。
重復(fù)執(zhí)行上述過(guò)程，知道堆Q為空。則結(jié)束執(zhí)行
整個(gè)算法的復(fù)雜度為O(v * logv)
代碼如下：
#include<iostream>
using namespace std ;
const int N = 9 ;
const int SIZE = 14 ;
int key[N] ; //表示路徑
int par[N] ;
int visit[N] ;
int matrix[N][N] ;
void primIni() //prim初始化函數(shù)
{
int i ;
for(i = 0 ; i < N ; i++)
{
key[i] = 66536 ;
par[i] = -1 ; //父節(jié)點(diǎn)
visit[i] = 0 ; //表示是否在Q中，在Q中則為1
}
key[0] = 0 ;
//visit[0] = 1;
}
//在Q堆中查找最小值 返回下標(biāo)
int findMin()
{
int min = 65536 ;
int k = -1 ;
for(int i = 0 ; i < N ;i++)
{
if(visit[i] == 0 )
{
if(min > key[i])
{
min = key[i] ;
k = i ;
}
}
}
return k ;
}
int prim()
{
primIni() ;
int u ;
int x ;
while(1)
{
u = findMin() ;
if(u == -1 ) //在Q中沒(méi)有找到
break ;
x = u ;
printf("%c\n" , u + 'a');
visit[u] = 1 ;//做標(biāo)記
for(int i = 0 ; i < N ;i++ ) //在u的鄰接邊中找出最小值
{
if(visit[i] == 0 && matrix[u][i] > 0 && matrix[u][i] < key[i])
{
key[i] = matrix[u][i] ; //當(dāng)把一個(gè)新的節(jié)點(diǎn)加入樹(shù)中時(shí)，需要改變與其直接相鄰的節(jié)點(diǎn)
par[i] = u ;
}
}
}
return x ;
}
void print(int u)
{
if(u!= -1)
{
print(par[u]);
printf("%c ---->%c\n" ,par[u] + 'a' , u+'a');
}
}
int main()
{
int i ;
char c1 ,c2 ;
int w ;
memset(matrix , 0 , sizeof(matrix)) ;
for(i = 0 ; i < SIZE ;i++)
{
cin>>c1>>c2>>w ;
matrix[c1-'a'][c2-'a'] = w ; //無(wú)向圖 所以每個(gè)節(jié)點(diǎn)均賦值
matrix[c2-'a'][c1-'a'] = w ;
}
int u = prim();
//print(u) ;
system("pause") ;
return 0 ;
}
三 Dijkstra算法
該算法使用了一個(gè)中間數(shù)據(jù)結(jié)構(gòu)d[i] ，用來(lái)存儲(chǔ)節(jié)點(diǎn)i到源點(diǎn)的距離，初始時(shí)都設(shè)置為無(wú)窮大。
構(gòu)建一個(gè)堆，將所有的節(jié)點(diǎn)均存儲(chǔ)進(jìn)堆中。堆中各個(gè)元素的大小關(guān)系，通過(guò)d[] 數(shù)組來(lái)確定。
算法的步驟：
(1) 首先置d[r]=0，然后將所有的頂點(diǎn)均插入進(jìn)堆中。
(2) 執(zhí)行EXTRACT_MIN(Q) ，從堆中取d[i]值最小的節(jié)點(diǎn)i。 // v * LOGv
(3) 判斷所有與i節(jié)點(diǎn)相鄰的節(jié)點(diǎn)v ，判斷d[v] > d[i] + w[i][v] ，若成立則更新d[v] = d[i] + w[i][v]，更新完成之后，需要對(duì)堆中的d[v]元素執(zhí)行siftup()操作。e*LOGv
(4) 重復(fù)2，3直到堆Q為空。
算法時(shí)間復(fù)雜度O(v * LOGv + e * LOG v )
代碼如下：
/**//*
初始S集合中，為空集合，從Q集合中選取最小的d的節(jié)點(diǎn)u，并將其加入到集合S中。
然后更改與u相鄰的所有節(jié)點(diǎn)，調(diào)用relax。
重復(fù)以上操作。
這個(gè)算法本身是使用了談心策略
*/
#include <iostream>
using namespace std ;
struct Node //使用鄰接表存儲(chǔ)圖
{
int col ; //下一個(gè)節(jié)點(diǎn)
Node * link ;
int w ;
} ;
const int N = 5 ;
int d[N] ;
int par[N] ;
const int MAX = 66536 ;
const int SIZE = 10 ;
Node list[N] ;
int heap[N + 1] ;
int top ; //標(biāo)記堆中的元素個(gè)數(shù)
//將元素插入堆中
void siftup(int u)
{
heap[++top] = u ; //將該元素插入進(jìn)堆中的最后一個(gè)位置
//然后向上移動(dòng)，直到到達(dá)頂部
int i = top ;
int j = i / 2 ;
while(j > 0)
{
if(d[heap[j]] > d[heap[i]])
{
swap(heap[i] , heap[j]) ;
i = j ;
j = j / 2 ;
}
else
{
break ;
}
}
}
//將元素從堆中取出之后，將最后一個(gè)元素插入堆頭，然后向下移動(dòng)
int minHeap()
{
if(top <= 0 )
return -1 ;
int u = heap[1] ;
heap[1] = heap[top--] ; //將最末的一個(gè)節(jié)點(diǎn)移到堆的頭部
//然后執(zhí)行下移操作
int i = 1 ;
int j = i * 2 ;
while(j <= top)
{
if(d[heap[i]] > d[heap[j]])
{
swap(heap[i] , heap[j]) ;
i = j ;
j = j * 2 ;
}
else
{
break;
}
}
return u ; //返回堆中的第一個(gè)元素
}
void iniDijkstra()
{
int i ;
top = 0 ;
for(i = 0 ; i < N ;i++)
{
d[i] = MAX ;
par[i] = -1 ;
list[i].col = -1 ;
list[i].link = 0 ;
}
d[0] = 0 ; //對(duì)源點(diǎn)進(jìn)行初始化
for(i = 0 ; i < N ;i++) //初始化堆操作s
siftup(i) ;
}
void relax(int u , int v , int w)
{
if(d[v] > d[u] + w)
{
d[v] = d[u] + w ;
siftup(v) ;
par[v] = u ;
}
}
void Dijkstra()
{
while(top > 0)
{
int u = minHeap() ; //從集合Q中取出最小的d[u]。
Node * p = list[u].link ;
while(p)
{
relax(u , p->col , p->w) ;
p = p ->link ;
}
}
}
int main()
{
int i , j , e1 , e2 , w;
iniDijkstra() ;
for(i = 0 ; i < SIZE ; i++ ) //創(chuàng)建每一個(gè)鄰接表的節(jié)點(diǎn)
{
cin>>e1>>e2>>w ;
Node * p = (Node *) malloc(sizeof(Node)) ;
p->col = e2 ;
p->w = w ;
p->link = list[e1].link ;
list[e1].link = p ;
}
Dijkstra();
for(i = 0 ; i < N ;i++ )
{
printf("%d " , d[i]) ;
}
system("pause") ;
return 0 ;
}