求最短路程（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;
}
