首页 > 求最短路程(Prim算法)求C语言代码的解题
头像
offer找我
编辑于 2021-04-21 17:49
+ 关注

求最短路程(Prim算法)求C语言代码的解题

胜利乡有7个村庄(A, B, C, D, E, F, G) ,现在需要修路把7个村庄连通
各个村庄的距离用边线表示(权) ,比如 A–B 距离 5公里

问:如何修路保证各个村庄都能连通,并且总的修建公路总里程最短?

#include <iostream>
#define max 10000
using namespace std;

int main()
{
   int sum=0;//总路程
   int min, min_f , min_t, min_s;  //分别为最小值,最小值开始的值,最小值到达的值,顶点之间的边的最小权值 
   int v[7][7]={{-1,5,7,-1,-1,-1,2},{5,-1,-1,9,-1,-1,3},{7,-1,-1,-1,8,-1,-1},{-1,9,-1,-1,-1,4,-1},{-1,-1,8,-1,-1,5,4},{-1,-1,-1,4,5,-1,6},{2,3,-1,-1,4,6,-1}};
   char ch[7] = {'A','B','C','D','E','F','G'};        //-1表示两个点之间没有连线 
   bool V_[7];   //判断村庄是否路过,标记
   
   for(int i= 0;i<7;i++)   //边邻接关系的初始化
   {  
    	for(int j = 0; j< 7 ;j++)
		{
        	if(v[i][j]==-1)
			{
           		v[i][j]=max;
        	}
        	else if(i==j)
			{
        		v[i][j]=0;
			} 
    	}
   }
   V_[0] = true;//从A出发
   for(int n = 0;n < 6; n++)  //开始遍历7个点
   {               
        //  数据初始化
        min_f = 0;
        min_t = 0;
        min = max;
		int i,j;
		
        for(int i= 0;i<7;i++) //找出发点
		{               
        	if(!V_[i])  //如果i不是已访问过的结点,则寻找下一个节点
			{
        		continue;
			} 
        	for(int i=1;i<=7;i++)    //寻找未被收录顶点中的最小值 
			{
        		if((v[i][j]<min)&&(v[i][j]!=0))
				{
        			min_s=v[i][j];
        			j=i;
				}
			}
			int j; 
			v[i][j]=0;               
        	for(int j = 0; j< 7 ;j++)   //找到最小边, j表示未访问过的结点
			{          
            	if(v[i][j] == max)
				{
            		continue;
				}  
            	
           		if(v[i][j]<min)   //如果当前min大于当前两个结点(这两个结点一个为已访问,一个为未访问)的最小路径,则替换当前的最小路径为当前两个结点的路径
				{
                	if(V_[j]!=0)
					{
                		continue;  //如果被标记了,跳过。
					}
					   
                	min = v[i][j];
                	min_t = i;
                	min_f = j;//记录下标
           		}
        	}
       }
       cout<<ch[min_t]<<" -> "<<ch[min_f]<<" "<<v[min_t][min_f]<<endl;
       V_[min_f] = true;
       sum += v[min_t][min_f];
   }
    cout<<"总路程:"<<sum<<endl;
    return 0;
}


全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期精华帖

热门推荐