图算法
一 PRIM算法与DIJKSTRA算法
两个算法之间都有相似性，都用到了堆结构，都是使用了贪心性质，所以容易混淆。
二 PRIM算法
该算法定义一个数组key[] ,key[i]表示i节点到树中某一节点最小的距离。
思想：初始时生成树为一个空树，而堆Q为一个满堆，所有的节点均在堆中。
首先置key[r]=0,然后执行EXTRACT_MIN(Q) 函数，从堆中取出key[j]最小的元素。
然后对所有与节点j相邻的节点i，判断w[i][j] < key[i] ，若小于则更新key[i]。
注意更新完之后需要对key[i]重新执行siftup()操作，对堆进行调整。
重复执行上述过程，知道堆Q为空。则结束执行
整个算法的复杂度为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初始化函数
{
int i ;
for(i = 0 ; i < N ; i++)
{
key[i] = 66536 ;
par[i] = -1 ; //父节点
visit[i] = 0 ; //表示是否在Q中，在Q中则为1
}
key[0] = 0 ;
//visit[0] = 1;
}
//在Q堆中查找最小值 返回下标
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中没有找到
break ;
x = u ;
printf("%c\n" , u + 'a');
visit[u] = 1 ;//做标记
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] ; //当把一个新的节点加入树中时，需要改变与其直接相邻的节点
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 ; //无向图 所以每个节点均赋值
matrix[c2-'a'][c1-'a'] = w ;
}
int u = prim();
//print(u) ;
system("pause") ;
return 0 ;
}
三 Dijkstra算法
该算法使用了一个中间数据结构d[i] ，用来存储节点i到源点的距离，初始时都设置为无穷大。
构建一个堆，将所有的节点均存储进堆中。堆中各个元素的大小关系，通过d[] 数组来确定。
算法的步骤：
(1) 首先置d[r]=0，然后将所有的顶点均插入进堆中。
(2) 执行EXTRACT_MIN(Q) ，从堆中取d[i]值最小的节点i。 // v * LOGv
(3) 判断所有与i节点相邻的节点v ，判断d[v] > d[i] + w[i][v] ，若成立则更新d[v] = d[i] + w[i][v]，更新完成之后，需要对堆中的d[v]元素执行siftup()操作。e*LOGv
(4) 重复2，3直到堆Q为空。
算法时间复杂度O(v * LOGv + e * LOG v )
代码如下：
/**//*
初始S集合中，为空集合，从Q集合中选取最小的d的节点u，并将其加入到集合S中。
然后更改与u相邻的所有节点，调用relax。
重复以上操作。
这个算法本身是使用了谈心策略
*/
#include <iostream>
using namespace std ;
struct Node //使用邻接表存储图
{
int col ; //下一个节点
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 ; //标记堆中的元素个数
//将元素插入堆中
void siftup(int u)
{
heap[++top] = u ; //将该元素插入进堆中的最后一个位置
//然后向上移动，直到到达顶部
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 ;
}
}
}
//将元素从堆中取出之后，将最后一个元素插入堆头，然后向下移动
int minHeap()
{
if(top <= 0 )
return -1 ;
int u = heap[1] ;
heap[1] = heap[top--] ; //将最末的一个节点移到堆的头部
//然后执行下移操作
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 ; //返回堆中的第一个元素
}
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 ; //对源点进行初始化
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++ ) //创建每一个邻接表的节点
{
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 ;
}