首页 > 代码库 > Prime算法求最小生成树 (邻接矩阵)

Prime算法求最小生成树 (邻接矩阵)

/*
Name: Prime算法求最小生成树 (邻接矩阵)
Copyright: 
Author: 巧若拙 
Date: 25/11/14 13:38

Description: 

实现了 Prime算法求最小生成树 (邻接矩阵)的普通算法和最小堆优化算法。 

*/
#include<stdio.h>
#include<stdlib.h>


#define MAX 2000   //最大顶点数量 
#define INFINITY 999999   //无穷大 


typedef struct MinHeap{  
    int num;//存储顶点序号 
int w;  //存储顶点到最小生成树的距离
} MinHeap; //最小堆结构体  


int map[MAX][MAX] = {0};//邻接矩阵存储图信息 


void CreatGraph(int m, int n);//创建邻接矩阵图 
void CreatGraph_2(int m, int n);//创建邻接矩阵图(随机图) 
void PrintGraph(int n);//输出图
void Prime(int n, int v0);//Prime算法求最小生成树(原始版本) 
void Prime_MinHeap(int n, int v0);//Prime算法求最小生成树(优先队列版本) 
void BuildMinHeap(MinHeap que[], int n);
void MinHeapSiftDown(MinHeap que[], int n, int pos);
void MinHeapSiftUp(MinHeap que[], int n, int pos);
void ChangeKey(MinHeap que[], int pos, int weight);//将第pos个元素的关键字值改为weight 
int SearchKey(MinHeap que[], int pos, int weight);//查找最小堆中关键字值为k的元素下标,未找到则返回-1(非递归) 
int ExtractMin(MinHeap que[]);//删除并返回最小堆中具有最小关键字的元素


int main()
{
int i, j, m, n, v0 = 0;

printf("请输入顶点数量:"); 
scanf("%d", &n);
printf("\n请输入边数量:"); 
scanf("%d", &m);

CreatGraph_2(m, n);//创建邻接矩阵图 
// PrintGraph(n);//输出图
    Prime(n, v0);//Prime算法求最小生成树(原始版本) 
    Prime_MinHeap(n, v0);//Prime算法求最小生成树(优先队列版本) 


    return 0;
}


void CreatGraph(int m, int n)//创建邻接矩阵图 
{
int i, j, a, b, c;

for (i=0; i<n; i++) //初始化顶点数据 
{
for (j=0; j<n; j++)
{
map[i][j] = (i == j) ? 0 : INFINITY;
}
}
    printf("\n请按照a b c格式输入边信息:\n"); 
    for (i=0; i<m; i++)
    {
    scanf("%d%d%d", &a,&b,&c);
    map[a][b] = map[b][a] = c;
    }



void CreatGraph_2(int m, int n)//创建邻接矩阵图(随机图) 
{
int i, j, a, b, c;

for (i=0; i<n; i++) //初始化顶点数据 
{
for (j=0; j<n; j++)
{
map[i][j] = (i == j) ? 0 : INFINITY;
}
}
   
    for (i=1; i<n; i++)//确保是连通图
{
map[i][0] = map[0][i] =  rand() % 100 + 1;

m -= n - 1;
    while (m > 0)
    {
    for (i=0; i<n; i++) 
    {
    for (j=i+1; j<n; j++)
    {
    if (rand()%10 == 0) //有10%的概率出现边
{
    if (map[j][i] == INFINITY)
    {
    map[i][j] = map[j][i] =  rand() % 100 + 1;
    m--;
    if (m == 0)
    return;
    }

    }
    }
    }



void PrintGraph(int n)//输出图
{
    int i, j;
    
    for (i=0; i<n; i++)
    {
        printf("G[%d] = %d: ", i, i);
        for (j=0; j<n; j++)
        {
        if (map[i][j] != 0 && map[i][j] != INFINITY)
            printf("<%d, %d> = %d", i, j, map[i][j]);
        }
        printf("\n");
    }
    printf("\n");



void Prime(int n, int v0)//Prime算法求最小生成树(原始版本) 
{
int book[MAX] = {0}; //标记该顶点是否已经在路径中 
int dic[MAX] = {0}; //存储顶点到最小生成树的距离 
int adj[MAX] = {0}; //存储顶点在最小生成树树中的邻接点序号 
int min, i, j, k;

for (i=0; i<n; i++) //初始化工作 
{
dic[i] = map[v0][i];
adj[i] = v0;
}
book[v0] = 1;

for (i=1; i<n; i++) //每趟确定一个新顶点,共n-1趟 
{
min = INFINITY;
k = v0;
for (j=0; j<n; j++)//找出离最小生成树最近的顶点k 
{
if (book[j] == 0 && dic[j] < min)
{
min = dic[j];
k = j;
}
}

book[k] = 1;   printf("<%d, %d> = %d   ", adj[k], k, dic[k]);
for (j=0; j<n; j++)//更新与顶点k的邻接点的dic[]值 
{
if (book[j] == 0 && dic[j] > map[k][j])
{
dic[j] = map[k][j];
adj[j] = k;
}
}
}

min = 0;
for (i=0; i<n; i++) //输出各顶点在最小生成树中的邻接点及边的长度 
{
// printf("<%d, %d> = %d\n", adj[i], i, dic[i]);
min += dic[i];
}
printf("最小生成树总长度(权值)为 %d\n", min); 
}


void Prime_MinHeap(int n, int v0)//Prime算法求最小生成树(优先队列版本) 
{
int book[MAX] = {0}; //标记该城市是否已经在路径中 
int dic[MAX] = {0}; //存储顶点到最小生成树的距离 
int adj[MAX] = {0}; //存储顶点在最小生成树树中的邻接点序号 
MinHeap que[MAX+1];//最小堆用来存储顶点序号和到最小生成树的距离 
int min, i, j, k, pos, K;

que[0].num = n; //存储最小堆中的顶点数量 
for (i=0; i<n; i++) //初始化工作 
{
dic[i] = map[v0][i];
adj[i] = v0;
que[i+1].num = i;
que[i+1].w = dic[i];
}
book[v0] = 1;
BuildMinHeap(que, n);//构造一个最小堆 
ExtractMin(que);//删除顶点v0 


for (i=1; i<n; i++) //每趟确定一个新顶点,共n-1趟 
{
k = ExtractMin(que);//删除并返回最小堆中具有最小关键字的元素
book[k] = 1;   printf("<%d, %d> = %d   ", adj[k], k, dic[k]);
for (j=0; j<n; j++)//更新与顶点k的邻接点的dic[]值,同时更新最小堆 
{
if (book[j] == 0 && dic[j] > map[k][j])
{
pos = SearchKey(que, j, dic[j]);    
dic[j] = map[k][j];                  
adj[j] = k;                  
ChangeKey(que, pos, dic[j]);//将第pos个元素的关键字值改为weight  
}
}
}

min = 0;
for (i=0; i<n; i++) //输出各顶点在最小生成树中的邻接点及边的长度 
{
// printf("<%d, %d> = %d\n", adj[i], i, dic[i]);
min += dic[i];
}
printf("最小生成树总长度(权值)为 %d\n", min); 
}


int ExtractMin(MinHeap que[])//删除并返回最小堆中具有最小关键字的元素
{  
    int pos = que[1].num;  
    
    que[1] = que[que[0].num--];
    MinHeapSiftDown(que, que[0].num, 1);  
      
    return pos;  
}  


int SearchKey(MinHeap que[], int pos, int weight)//查找最小堆中关键字值为k的元素下标,未找到则返回-1(非递归) 
{
int Stack[MAX] = {0};
int i = 1, top = -1;

while ((i <= que[0].num && que[i].w <= weight) || top >= 0)//类似先序遍历二叉树的方式查找 
{
if (i <= que[0].num && que[i].w <= weight)
{
if (que[i].w == weight && que[i].num == pos)//权值与顶点序号都必须对应 
return i;
Stack[++top] = i;//该结点入栈 
i *= 2; //搜索左孩子 
}
else
{
i = Stack[top--] * 2 + 1; //结点退栈并搜索右孩子 
}
}

return -1;
}


void ChangeKey(MinHeap que[], int pos, int weight)//将第pos个元素的关键字值改为weight  
{  
    if (weight < que[pos].w) //关键字值变小,向上调整最小堆   
    {  
        que[pos].w = weight;  
        MinHeapSiftUp(que, que[0].num, pos);    
    }  
    else if (weight > que[pos].w)  //关键字值变大,向下调整最小堆   
    {  
        que[pos].w = weight;   
        MinHeapSiftDown(que, que[0].num, pos);      
    }     



void MinHeapSiftDown(MinHeap que[], int n, int pos)  //向下调整结点 
{  
    MinHeap temp = que[pos];  
    int child = pos * 2; //指向左孩子   
      
    while (child <= n)  
    {  
        if (child < n && que[child].w > que[child+1].w) //有右孩子,且右孩子更小些,定位其右孩子   
            child += 1;  
          
        if (que[child].w < temp.w) //通过向上移动孩子结点值的方式,确保双亲小于孩子   
        {  
            que[pos] = que[child];   
            pos = child;  
            child = pos * 2;  
        }  
        else  
            break;  
    }  
    que[pos] = temp; //将temp向下调整到适当位置   
}  


void MinHeapSiftUp(MinHeap que[], int n, int pos)  //向上调整结点 
{  
    MinHeap temp = que[pos];  
    int parent = pos / 2; //指向双亲结点  
      
    if (pos > n) //不满足条件的元素下标   
        return;  
      
    while (parent > 0)  
    {  
        if (que[parent].w > temp.w) //通过向下移动双亲结点值的方式,确保双亲小于孩子   
        {  
            que[pos] = que[parent];   
            pos = parent;  
            parent = pos / 2;     
        }  
        else  
            break;  
    }  
    que[pos] = temp; //将temp向上调整到适当位置   
}  




void BuildMinHeap(MinHeap que[], int n)//构造一个最小堆 
{
int i;

for (i=n/2; i>0; i--)
{
MinHeapSiftDown(que, n, i);
}
}

Prime算法求最小生成树 (邻接矩阵)