使用二进制最小堆实现 PRIM 算法

一、实验名称：Implementation of PRIM Algorithm Using binary min-Heap

二、实验目的：

1. 熟练掌握堆的数据结构,结构的特点；
2. 能够实现堆和队列的基本操作：如构造，插入，删除,初始化，回收内存等
3. 熟练掌握图的数据结构表线形式：用邻接表表示图
4. 学习实现PRIM算法找到图的最小生成树
5. 能够灵活的使用数据结构来实现算法如使用最小堆实现 PRIM算法

三、实验内容：

Refer to the lecture in Prim’s algorithm - Algorithm Analysis - An improvement using binary min-heap.

1. Represent the graph with an Adjacency List
2. Determine data structures for the binary min-heap of improved Prim’s algorithm
3. Implement the improved Prim’s algorithm using binary min-heap in C language.

四. 算法实现：

在数学上该算法可以简单地描述为执行以下步骤：

1. 从图上任意选择一个具有单个顶点的树。
2. 通过一条边使树生长：将树连接到树中尚未存在的顶点的边中，找到最小权重的边，然后将其转移到树上。
3. 重复步骤2（直到所有顶点在树中）。

伪代码

1. 将图的每个顶点v关联一个数字dis [ v ]（连接到最小生成树的最短边权和）。将dis [ v ]的所有值初始化设置为+∞。

2. 初始化一个空的森林MST，收入任意顶点（此处收入0号顶点：dis[k]=0表示k号顶点已经被收入），更新dis的值，设更新的节点的parent为0

3. 更新dis的值，设更新的节点的parent为0:具体步骤为

   遍历连接0的其它顶点w 。对于每个这样的点，如果

   仍属于Q且0w的权重小于dis [w ]，则执行以下步骤：

   1. 将dis [ w ]设置为边0w的权重
   2. 将parent [ w ]设置为指向边0。

4. 重复以下步骤，直到未收入顶点(最小堆）为空：

   1. 利用最小堆的结构从为收入MST的集合中Q中找出具有最小可能值dis [ v ]的顶点v并将其删除(若dis=0则需要重新从最小堆中弹出元素因为不能是已经收入过的元素)

   2. 将v添加到MST，即向MST插入parent[v]到v的边

   3. 遍历连接v的其它顶点w 。对于每个这样的点，如果

      w仍属于Q且vw的权重小于dis [w ]，则执行以下步骤：

      1. 将dis [ w ]设置为边vw的权重
      2. 将parent [ w ]设置为指向边v。

5. 返回MST

通过优先级队列将以最低的时间代价更快地找到顶点v，但是当C [ w ]的值更改时，更新队列将需要比较高的时间代价。

核心算法代码：

void Prim(PtrToGraph G,PtrToGraph MST){
    
    int dis[VNUM];//每个点距离GResult的最小距离；
    int parent[VNUM];//每个点在最小生成树MST中的父节点
    for(int i=0;i<VNUM;i++){
    
        dis[i]=INFINITY;
    }
    //构造最小堆
    //依次插入节点下标，并按照dis进行最小堆的排序
    MinHeap h=CreateMinHeap(G->Vnum,dis);
    //收录第一个点；
    dis[0]=0;//收录进来的点距离GResult的最小距离为0；
    //更新距离
    PtrToContactPoint temp=G->AdjacencyList[0].head;
    while(temp!=NULL){
    
        dis[temp->Subscript]=temp->weight;
        parent[temp->Subscript]=0;//由0衍生到达，故父节点为0
        temp=temp->next;
        
    }
    ReBuildMinHeap(h,dis);
    while(1){
    
        //采用最小堆的方法找到未收入端点到MST的最小距离
        int index=PopMinHeap(h,dis);
        if(dis[index]==0)index=PopMinHeap(h,dis);//需为未收入端点
        if(index==error)break;//此时所有可找的表都已经找完
        PtrToedge e=(PtrToedge)malloc(sizeof(struct edge));
        e->v1=index;
        e->v2=parent[index];
        e->val=dis[index];
        InsertEdge(MST,e);
        //收入点index，并更新各个点的dis值
        dis[index]=0;
        PtrToContactPoint tmp=G->AdjacencyList[index].head;
        while(tmp!=NULL){
    
            if( dis[tmp->Subscript]>tmp->weight){
    
                dis[tmp->Subscript]=tmp->weight;
                parent[tmp->Subscript]=index;//由index衍生到达，故父节点为index
                }
            tmp=tmp->next;
        }
        ReBuildMinHeap(h,dis);
    }
}

四. 全部程序清单（较为详细的注释）：

#include <stdio.h>
#include <stdlib.h>
#define INFINITY 11111111
#define VNUM 8
#define error -1
typedef struct Hnode* MinHeap;
struct Hnode{
    
    int* data;
    int size;
    int Capacity;
};
typedef struct edge* PtrToedge;
struct edge{
    
    int val;
    int v1;
    int v2;//用下标表示顶点
};
typedef struct AdjacencyPoint* PtrToContactPoint;
struct AdjacencyPoint{
    
    int Subscript;
    int weight;
    PtrToContactPoint next;
};
struct Vnode{
    
    PtrToContactPoint head;
    int data;
};
typedef struct Graph* PtrToGraph;
struct Graph{
    
    int ENum;
    int Vnum;
    struct Vnode *AdjacencyList; 
};
/*Filter down and find the proper position of the node on the premise that all subtrees are the smallest heap. The tree with this node as the root node is a smallest heap*/
void FixDown(MinHeap h,int index,int*dis){
    
    int parent;
    int child;
    int temp=h->data[index];
    for(parent=index;parent*2<=h->size;parent=child){
    
        child=parent*2;
        if(child+1<=h->size&&dis[h->data[child+1]]<dis[h->data[child]])
            child++;
        if(dis[h->data[child]]<dis[temp]){
    
            h->data[parent]=h->data[child];
        }
        else break;
    }
    h->data[parent]=temp;
}
/*The idea of recursion is adopted to establish the minimum heap from bottom to top, which ensures that the subtrees currently established are all the smallest heaps.*/
void ReBuildMinHeap(MinHeap h,int*dis){
    
    int i;
    for(i=h->size/2;i>=1;i--){
    
        FixDown(h,i,dis);
    }
}
//Determine whether the MinHeap is empty
int Empty(MinHeap h){
    
    return h->size==0;
}
//Return and delete the minimum value of the minimum heap (that is, the head node), and keep the tree as the minimum heap
/*Move the last node to the head node, and size--, Because the subtrees are all the smallest heap at this time, filtering directly down can ensure that the tree is still the smallest heap*/
int PopMinHeap(MinHeap h,int*dis){
    
    if(Empty(h)){
    
        //printf("The minimum heap is empty, and the popped -11111 is an invalid value\n");
        return error;
    }
    int result=h->data[1];
    h->data[1]=h->data[(h->size)--];
    //向下过滤
    FixDown(h,1,dis);
    return result;
}
/*Insert node, keep minimum heap*/
void PushMinHeap(MinHeap h,int val,int*dis){
    
    if(h->size==h->Capacity){
    
        printf("The minimum heap is full and element insertion is invalid\n");
        return;
    }
    h->data[++(h->size)]=val;
    //向上过滤
    int child=h->size;
    int parent;
    for(;child>1;child=parent){
    
        parent=child/2;
        if(dis[h->data[parent]]>dis[val]){
    
            h->data[child]=h->data[parent];
        }
        else
        {
    
            break;
        }
        
    }
    h->data[child]=val;
}
/*Request space for the MinHeap*/
MinHeap CreateMinHeap(int MinHeapSize,int*dis){
    
    MinHeap h=(MinHeap)malloc(sizeof(MinHeap));
    h->data=(int*)malloc((MinHeapSize+1)*sizeof(int));
    h->size=0;
    h->Capacity=MinHeapSize;
    for(int i=0;i<MinHeapSize;i++){
    
        PushMinHeap(h,i,dis);
    }
    return h;
}
/*Free up space for MinHeap*/
void CleanMinHeap(MinHeap h){
    
    free(h->data);
    free(h);
}
PtrToGraph InitGraph(int Vnum){
    
    PtrToGraph G=(PtrToGraph)malloc(sizeof(struct Graph));
    G->Vnum=Vnum;
    G->ENum=0;
    G->AdjacencyList=(struct Vnode *)malloc(sizeof(struct Vnode)*Vnum);
    // 初始化邻接表头指针 
    for (int i=0; i<G->Vnum; i++)
        G->AdjacencyList[i].head= NULL;
        return G;
}    
void InsertEdge( PtrToGraph G, PtrToedge e )
{
    
    PtrToContactPoint NewNode1=(PtrToContactPoint)malloc(sizeof(struct AdjacencyPoint));
    //将V2插入V1的表头 
    NewNode1->Subscript = e->v2;
    NewNode1->next=G->AdjacencyList[e->v1].head;
    NewNode1->weight = e->val;
    G->AdjacencyList[e->v1].head = NewNode1;
        
    //图为无向图，还要将V1插入V2的表头 
    PtrToContactPoint NewNode2=(PtrToContactPoint)malloc(sizeof(struct AdjacencyPoint));
    //将V2插入V1的表头 
    NewNode2->Subscript = e->v1;
    NewNode2->next=G->AdjacencyList[e->v2].head;
    NewNode2->weight = e->val;
    G->AdjacencyList[e->v2].head = NewNode2;
}

int BuildGraph(PtrToGraph G)
{
    
    printf("Enter the number of edges\n");
    scanf("%d", &(G->ENum));//输入边数
    if ( G->ENum != 0 ) {
     //如果有边
        PtrToedge e=(PtrToedge)malloc(sizeof(struct edge));
        //分别输入边的两个起点下标，终点下标和权重
        for (int i=0; i<G->ENum; i++) {
    
        scanf("%d%d%d",&e->v1,&e->v2,&e->val);
        InsertEdge(G,e);
        }
        free(e);
    } 
    if(G->ENum<G->Vnum-1){
    
        printf("Too few edges to generate minimum spanning tree");
        return 0;
    }//无法生成最小生成树
    return 1;

    // /* 如果顶点有数据的话，读入数据 */
    // for (int i=0; i<G->Vnum; i++) 
    // scanf(" %c", &(G->AdjacencyList[i].data));
}
void CleanGraph(PtrToGraph G){
    
    free(G->AdjacencyList);
    free(G);
}
void Prim(PtrToGraph G,PtrToGraph MST){
    
    int dis[VNUM];//每个点距离GResult的最小距离；
    int parent[VNUM];//每个点在最小生成树MST中的父节点
    for(int i=0;i<VNUM;i++){
    
        dis[i]=INFINITY;
    }
    //构造最小堆
    //依次插入节点下标，并按照dis进行最小堆的排序
    MinHeap h=CreateMinHeap(G->Vnum,dis);
    //收录第一个点；
    dis[0]=0;//收录进来的点距离GResult的最小距离为0；
    //更新距离
    PtrToContactPoint temp=G->AdjacencyList[0].head;
    while(temp!=NULL){
    
        dis[temp->Subscript]=temp->weight;
        parent[temp->Subscript]=0;//由0衍生到达，故父节点为0
        temp=temp->next;
        
    }
    ReBuildMinHeap(h,dis);
    while(1){
    
        //采用最小堆的方法找到未收入端点到MST的最小距离
        int index=PopMinHeap(h,dis);
        if(dis[index]==0)index=PopMinHeap(h,dis);//需为未收入端点
        if(index==error)break;//此时所有可找的表都已经找完
        PtrToedge e=(PtrToedge)malloc(sizeof(struct edge));
        e->v1=index;
        e->v2=parent[index];
        e->val=dis[index];
        InsertEdge(MST,e);
        //收入点index，并更新各个点的dis值
        dis[index]=0;
        PtrToContactPoint tmp=G->AdjacencyList[index].head;
        while(tmp!=NULL){
    
            if( dis[tmp->Subscript]>tmp->weight){
    
                dis[tmp->Subscript]=tmp->weight;
                parent[tmp->Subscript]=index;//由index衍生到达，故父节点为index
                }
            tmp=tmp->next;
        }
        ReBuildMinHeap(h,dis);
    }
}
void Print(PtrToGraph MST){
    
    for(int i=0;i<MST->Vnum;i++){
    
        PtrToContactPoint temp=MST->AdjacencyList[i].head;
        printf("%d",i);
        while(temp!=NULL){
    
            printf("->%d",temp->Subscript);
            temp=temp->next;
        }
        printf("\n");
    }
}
int main()
{
       
    int n;//节点数
    printf("Enter the number of nodes\n");
    scanf("%d",&n);
    if(n==0)return 0;
    PtrToGraph G=InitGraph(n);
    int IfBuildGraph=BuildGraph(G);
    if(IfBuildGraph==0){
    
        CleanGraph(G);
        return 0;
    }//无法生成最小生成树
    PtrToGraph GResult=InitGraph(n);
    printf("Print the graph as an adjacency list:\n");
    Print(G);
    Prim(G,GResult);
    printf("Print the minimum spanning tree in the form of adjacency list:\n");
    Print(GResult);//以邻接表的形式打印最小生成树；
    CleanGraph(G);
    CleanGraph(GResult);
    return 0;
}

五、测试结果：

输入输出格式说明：

• 输入格式：
  先输入节点个数n；

  在输入边条数m；

  依次输入第k条边的第一个连接点，第二个连接点，边的权重。（此处为无向边）

• 输出格式：
  先用邻接表的形式输出原图；

  再用邻接表的形式输出该图的最小生成树

• 测试样例1：

  输入：

  3
  3
  0 1 1
  1 2 2
  2 0 1
  

  输出：

  Enter the number of nodes
  3
  Enter the number of edges
  3
  0 1 1
  1 2 2
  2 0 1
  Print the graph as an adjacency list:
  0->2->1
  1->2->0
  2->0->1
  Print the minimum spanning tree in the form of adjacency list:
  0->1->2
  1->0
  0->2->1
  1->2->0
  2->0->1
  Print the minimum spanning tree in the form of adjacency list:
  0->1->2
  1->0
  2->0
  

• 测试样例2：

  输入：

  ​

  8
  8
  0 1 1
  1 2 1 
  2 3 1
  3 4 1
  4 5 1
  5 6 1
  6 7 1
  7 0 1
  

  输出：

  Enter the number of nodes
  8
  Enter the number of edges
  8
  0 1 1 
  1 2 1 
  2 3 1 
  3 4 1 
  4 5 1 
  5 6 1 
  6 7 1 
  7 0 1
  Print the graph as an adjacency list:
  0->7->1
  1->2->0
  2->3->1
  3->4->2
  4->5->3
  5->6->4
  6->7->5
  7->0->6
  Print the minimum spanning tree in the form of adjacency list:
  0->7->1
  1->2->0
  2->3->1
  3->4->2
  4->3
  5->6
  6->5->7
  7->6->0
  

• 测试样例3：

  输入：

  5
  14
  0 1 1
  1 2 1
  2 3 1
  3 4 1
  4 5 1
  5 0 2
  5 1 3
  5 2 3
  5 3 3
  4 0 4
  4 1 4
  4 2 4
  3 1 3
  3 0 3
  

  输出：

  Enter the number of nodes
  5
  Enter the number of edges
  14
  0 1 1
  1 2 1
  2 3 1
  3 4 1
  4 5 1
  5 0 2
  5 1 3
  5 2 3
  5 3 3
  4 0 4
  4 1 4
  4 2 4
  3 1 3
  3 0 3
  Print the graph as an adjacency list:
  0->3->4->5->1
  1->3->4->5->2->0
  2->4->5->3->1
  3->0->1->5->4->2
  4->2->1->0->5->3
  Print the minimum spanning tree in the form of adjacency list:
  0->1
  1->2->0
  2->3->1
  3->4->2
  4->3
  

• 测试样例4：

  输入：

  ​

  0
  

  输出：

  Enter the number of nodes
  0
  

• 测试样例5：

  输入：

  ​

  4
  2
  

  输出：

  Enter the number of nodes
  4
  Enter the number of edges
  2
  1 2 1
  1 3 1
  Too few edges to generate minimum spanning tree
  

六、算法分析：

Prim算法的时间复杂度取决于用于图形和按权重排序边缘的数据结构，这里选择了堆和邻接表的数据结构完成该算法的设计

其时间复杂度为O（（| V | + | E |）\ log | V |）= O（| E | \ log | V |）}

堆按最小的边缘权重对顶点进行排序，以将它们连接到部分构造的MST中的任何顶点（如果不存在这样的边缘，则为无穷大）。每次选择一个顶点v并将其添加到MST时，都会对部分MST之外的所有顶点w进行更新操作，以使v连接到w。

使用简单的二进制堆数据结构，现在可以显示Prim算法在时间``O（| E | log | V |）中运行，其中| E | 是边的数量和| V | 是顶点数。