Prim算法的优化：邻接表、优先级队列 (堆) 优化(C语言实现)

小咪咪 2023-03-01 05:36 4阅读 0赞

在上一节中，我们给出了Dijkstra算法的邻接表、优先级队列 (堆) 优化方式。由于Prim算法与Dijkstra算法极其相似，也可以用邻接表、优先级队列优化，优化之后的代码也非常相似。这里直接给出最终的优化代码，这些代码其实就是在上述Dijkstra算法上稍稍修改后得到的。完整的代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    int size = 6; //一共6个点的地图 
    int size2 = 6; //一共6个点的地图 
    int inf = 999; //无穷大
    int distance[6]; //一维数组，记录距离 
    int book[6]; //标记每一个点是否是确定值 
    int sum = 0;//总距离
    
    //LinkNode是用于邻接表中，一个结点连接的其它结点 
    //LinkNode只需要有结点的编号、权重即可。 
    struct LinkNode{
        
    	int index = 0;
    	int weight = 0;
    	struct LinkNode * next = NULL; //指向下一个结点 
    };
    
    //声明结构体ArrayNode，用于邻接表中的数组 
    struct ArrayNode{
        
    	struct LinkNode * next = NULL; //指向链表的头结点
    };
    
    //用一个数组存放首元素。每个首元素后面用指针连接各个结点 
    struct ArrayNode arrNode[6]; //这是地图 
    int heap[6]; //优先级队列，这里就叫堆吧。里面的内容是在arrNode中的index 
    int position[6];//记录每个顶点在最小堆中的位置
    
    void showDistance()
    {
        
    	//同上一节Dijkstra算法
    }
    
    //头插法，得到的结果的次序是反的
    void addNode(int parentIndex, int nodeIndex, int weight)
    {
        
    	//同上一节Dijkstra算法
    }
    
    //用map对distance数组进行初始化 
    void initDistance(int startIndex)
    {
        
    	//同上一节Dijkstra算法
    }
    
    //Heap数组进行初始化 
    void initHeap()
    {
        
    	//同上一节Dijkstra算法
    }
    
    //求优先级队列heap中的三个元素的最小值的编号
    //三个参数分别是是father和两个儿子的编号。
    //father一定存在，但两个儿子不一定存在。  
    int getMinIndex(int father, int leftSon, int rightSon)
    {
        
    	//同上一节Dijkstra算法
    }
    
    //交换优先级队列中的元素。这里要注意，一定要同步更新HeapNode中的indexInHeap 
    void swap(int a, int b) 
    {
        
    	//同上一节Dijkstra算法
    }
    
    //shiftDown()是部分维护堆，时间复杂度为O(logN)
    //删除元素时用shiftDown(),把数据从上往下调整 
    int shiftDown(int i) //调整以编号为i的元素以下的大顶堆 
    {
        
    	//同上一节Dijkstra算法
    }
    
    //shiftUp()是部分维护堆，时间复杂度为O(logN)
    //添加元素时用siftUp()，把最底下的元素往上调整 
    int shiftUp(int i)  
    {
        
    	//同上一节Dijkstra算法
    }
    
    //建堆：建堆是最彻底的维护堆。但是时间复杂度较高，为O(N) 
    void createHeap()  
    {
        
    	//同上一节Dijkstra算法
    } 
    
    //优先级队列出列，得到最小值。
    //出列后要重新维护堆，这样才能保证堆顶元素是最小值 
    int dequeue()  
    {
        
    	//同上一节Dijkstra算法
    } 
    
    //Prim算法 
    void Prim(int startIndex)
    {
        
    	printf("加入的顶点：%d，边长：%d\r\n", 1, 0);
    	int count = 0; //确定了最小距离的点的数量
    	book[startIndex] = 1; //起始位置要先标记为已经访问过了 
    	createHeap(); //建堆 
    	dequeue(); // 出列
    		
    	while(count < size2) 	
    	{
        
    		int minDistance = distance[heap[0]];//堆顶元素的distance最小 
    		int minIndex = dequeue(); // 出列
    		if(minIndex < 0)
    		{
        
    			break;
    		}
    		
    		book[minIndex] = 1; //估计值变成确定值，标记有最小值的那个点被访问过 
    		count++;
    		sum += minDistance; //成树的所有边长的和 
    		printf("加入的顶点：%d，边长：%d\r\n", minIndex + 1, minDistance);
    		
    		//更新distance数组 
    		struct ArrayNode * nodeInArray = &arrNode[minIndex];
    		struct LinkNode * linkNode = nodeInArray->next; //获得与最小距离的点连接的点 
    		while(linkNode != NULL)
    		{
        
    			int index = linkNode->index;
    			
    			//更新距离的两个条件：没有被标记过，且距离可以变小
    			if(book[index] == 0 && distance[index] > linkNode->weight) 
    			{
        
    				distance[index] = linkNode->weight;
    				
    				//更新一个结点的值，由于更新后的值一定比原先的值小
    				//所以对于小顶堆而言，一定是向上更新 
    				shiftUp(index);
    			}
    			linkNode = linkNode->next; //下一个结点 
    		}
    	}	
    }
    
    //释放资源 
    void releaseResource()
    {
        
    	//同上一节Dijkstra算法
    }
    
    //遍历一个结点，和它的所有相连的结点 
    void traverse(int parentIndex)
    {
        
    	//同上一节Dijkstra算法
    }
    
    void traverseAll()
    {
        
    	//同上一节Dijkstra算法
    }
    
    int main()
    {
        
    	int startIndex = 0; //计算0号点到其它点的最短距离 
    	
    	//插入数据 
    	addNode(0, 1, 10); addNode(0, 2, 16); addNode(0, 3, 14); addNode(1, 0, 10); 
    	addNode(1, 3, 15); addNode(1, 4, 24); addNode(2, 0, 16); addNode(2, 3, 14); 
    	addNode(2, 5, 16); addNode(3, 0, 14); addNode(3, 1, 15); addNode(3, 2, 14);
    	addNode(3, 4, 23); addNode(3, 5, 8);  addNode(4, 1, 24); addNode(4, 3, 23); 
    	addNode(4, 5, 22); addNode(5, 2, 16); addNode(5, 3, 8);  addNode(5, 4, 22);
    	
    	printf("初始状态：\r\n");
    	traverseAll(); //全部遍历 
    	
    	initDistance(startIndex); //初始化distance数组 
    	initHeap(); //初始化堆
    	
    	Prim(startIndex);
    	printf("用邻接表、优先级队列优化之后，Prim算法的结果：\r\n");
    	printf("sum = %d\r\n", sum);
    	
    	releaseResource(); //释放内存 
    	printf("Hello\r\n"); //释放内存之后，再访问就会出错。具体表现为无法打印Hello
    	return 0;
    }

计算结果如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/0cab9c6ed48f41bd8719d9e6e4e2ad54.png