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 int VertexType; //顶点类型由用户自定义
typedef int EdgeType; //边上的权值类型由用户自定义


typedef struct EdgeNode{ //边表结点
int adjvex;  //邻接点域，存储该顶点对应的下标
EdgeType weight; //权值，对于非网图可以不需要 
struct EdgeNode *next; //链域，指向下一个邻接点 
} EdgeNode;


typedef struct VertexNode{ //顶点表结点
VertexType data; //顶点域，存储顶点信息
EdgeNode *firstEdge; //边表头指针
} VertexNode;


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




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


int Locate(VertexNode *GL, int u, int v);//判断u，v是否是邻接点 
void CreateGraph(VertexNode *GL, int n, int m);//创建邻接表图（人工图） 
void CreateGraph_2(VertexNode *GL, int n, int m);//创建邻接表图（随机图） 
void PrintGraph(VertexNode *GL, int n);//输出图
void DestroyGL(VertexNode *GL, int n);//销毁图并释放空间 
void Prime(VertexNode *GL, int n, int v0);//Prime算法求最小生成树（原始版本） 
void Prime_MinHeap(VertexNode *GL, 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;
VertexNode GL[MAX];

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

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


    return 0;
}


void CreateGraph(VertexNode *GL, int n, int m)//创建一个图
{
    int i, u, v, w;
    EdgeNode *e;
    
    for (i=0; i<n; i++)//初始化图 
    {
        GL[i].data = i;
        GL[i].firstEdge = NULL;
    }
    
    for (i=0; i<m; i++) //读入边信息（注意是无向图） 
    {
        scanf("%d%d%d", &u, &v, &w);
        
        e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
        if (!e)
        {
            puts("Error"); 
            exit(1);
        }
        e->next = GL[u].firstEdge;
        GL[u].firstEdge = e;
        e->adjvex = v;
        e->weight = w;
        
        e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
        if (!e)
        {
            puts("Error"); 
            exit(1);
        }
        e->next = GL[v].firstEdge;
        GL[v].firstEdge = e;
        e->adjvex = u;
        e->weight = w;
    }
} 


void PrintGraph(VertexNode *GL, int n)//输出图
{
    int i, j;
    EdgeNode *e;
    
    for (i=0; i<n; i++)
    {
        printf("%d: ", i);
        e = GL[i].firstEdge;
        while (e)
        {
            printf("<%d, %d> = %d  ", i, e->adjvex, e->weight);
            e = e->next;
        }
        printf("\n");
    }
    printf("\n");
} 


void CreateGraph_2(VertexNode *GL, int n, int m)//创建邻接表图（随机图） 
{
int i, j, u, v, w;
    EdgeNode *e;
    
    for (i=0; i<n; i++)//初始化图 
    {
        GL[i].data = i;
        GL[i].firstEdge = NULL;
    }
    
    for (i=1; i<n; i++)//确保是连通图
{
w =  rand() % 100 + 1;
e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
        if (!e)
        {
            puts("Error"); 
            exit(1);
        }
        e->next = GL[0].firstEdge;
        GL[0].firstEdge = e;
        e->adjvex = i;
        e->weight = w;
        
        e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
        if (!e)
        {
            puts("Error"); 
            exit(1);
        }
        e->next = GL[i].firstEdge;
        GL[i].firstEdge = e;
        e->adjvex = 0;
        e->weight = w;
} 

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 (!Locate(GL, i, j))
    {
    w =  rand() % 100 + 1;
e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
       if (!e)
       {
           puts("Error"); 
           exit(1);
       }
       e->next = GL[i].firstEdge;
       GL[i].firstEdge = e;
       e->adjvex = j;
       e->weight = w;
       
       e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
       if (!e)
       {
           puts("Error"); 
           exit(1);
       }
       e->next = GL[j].firstEdge;
       GL[j].firstEdge = e;
       e->adjvex = i;
       e->weight = w;
       
    m--;
    if (m == 0)
    return;
    }
} 
    }
    }
    }
} 


int Locate(VertexNode *GL, int u, int v)//判断u，v是否是邻接点 
{
EdgeNode *e = GL[u].firstEdge;


    while (e)
    {
        if (e->adjvex == v)
        return 1;
        e = e->next;
    }
    return 0;
}


void DestroyGL(VertexNode *GL, int n)
{
int i;
    EdgeNode *e, *q;
    
    for (i=0; i<n; i++)
    {
        e = GL[i].firstEdge;
        do
        {
        q = e->next;
            free(e);
            e = q;
        } while (e);
        GL[i].firstEdge = NULL;
    }
}


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

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

for (i=0; i<n; i++) //每趟确定一个新顶点，共n趟 
{
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 (e=GL[k].firstEdge; e; e=e->next)//更新与顶点k的邻接点的dic[]值 
        {
        j = e->adjvex;
            if (book[j] == 0 && dic[j] > e->weight)
{
dic[j] = e->weight;
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(VertexNode *GL, 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;
EdgeNode *e;

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


for (i=0; i<n; i++) //每趟确定一个新顶点，共n趟 
{
k = ExtractMin(que);//删除并返回最小堆中具有最小关键字的元素
book[k] = 1;   printf("<%d, %d> = %d   ", adj[k], k, dic[k]);

for (e=GL[k].firstEdge; e; e=e->next)//更新与顶点k的邻接点的dic[]值 
        {
        j = e->adjvex;
            if (book[j] == 0 && dic[j] > e->weight)
{
pos = SearchKey(que, j, dic[j]);    
dic[j] = e->weight;
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);
}
}