ola26729784最小生成树2020.12.01

ola26729784最小生成树2020.12.01

#include<stdio.h>
#define MAX_VERTEX_NUM 50//椤剁偣涓暟
#define INF 100000000int U[MAX_VERTEX_NUM] = {1,1,1,2,2,2,3,3,4,4,5,5,5,6,6,6,7,8,9};
int V[MAX_VERTEX_NUM] = {2,4,5,3,5,6,6,7,5,8,6,8,9,7,9,10,10,9,10};
int C[MAX_VERTEX_NUM] = {3,4,4,10,2,3,6,1,5,6,11,2,1,2,3,11,8,4,7};
int adj[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int dis[MAX_VERTEX_NUM];
int vis[MAX_VERTEX_NUM];
int pre[MAX_VERTEX_NUM];void build_Graph(int x, int y, int v){for(int i=1;i<=10;i++){for(int j=1;j<=10;j++){if(i==j)adj[i][j]=0;else adj[i][j] = INF;}}for(int i=0;i<19;i++){if(U[i] == x && V[i] == y || U[i] == y && V[i] == x ){adj[U[i]][V[i]] = adj[V[i]][U[i]] = v;}else{adj[U[i]][V[i]] = adj[V[i]][U[i]] = C[i];}}
}void prim(int v)
{int i, j, u , min, idx = 0;for(i=1;i<=10;i++){dis[i]=adj[v][i];vis[i]=0;}vis[v]=1;for(i=2;i<=10;i++){min = INF;for(j=1;j<=10;j++){if(!vis[j]&&min > dis[j]){min = dis[j];u = j;}}vis[u]=1;pre[idx++] = min;for(j=1;j<=10;j++){if(!vis[j]&&dis[j] > adj[u][j]){dis[j] = adj[u][j];}}}for(int i=1;i<idx-1;i++){for(int j = 0;j<idx-1-i;j++){if(pre[j+1]<pre[j]){int temp = pre[j+1];pre[j+1] = pre[j];pre[j] = temp;}}}for(int i=0;i<idx;i++){printf("%d,", pre[i]);}
}int main(){char n,m;int value;scanf("%c,%c,%d",&n,&m,&value);int x = n - 'A' + 1;int y = m - 'A' + 1;build_Graph(x,y,value);prim(1);printf("n");return 0;
}