realyanhualengluo @ 2023-03-19 11:23:40
1)对于重边选择了最小的那一个
#include<iostream>
#include<algorithm>
using namespace std;
const int maxs = 50;
const int INF = 99999;
struct AMGraph {
int vexs[maxs];//定点表
int arr[maxs][maxs];//邻接矩阵
int vexnum, arcnum;//顶点数,边数
};
void initGraph(AMGraph &G) {
cin >> G.vexnum >> G.arcnum;
for (int i = 1; i <= G.vexnum; i++) {
G.vexs[i] = i;
}
for (int i = 1; i <= G.vexnum; i++) {
for (int j = 1; j <= G.vexnum; j++) {
G.arr[i][j] = INF;
}
}
}
void createGraph(AMGraph& G) {
int i = 0, j = 0,w=0;
for (int k = 1; k <= G.arcnum; k++) {
cin >> i >> j>>w;
if (w < G.arr[i][j]) {
G.arr[i][j] = w;
}
}
}
void showGraph(AMGraph G)
{
for (int i = 1; i <= G.vexnum; i++)
{
for (int j = 1; j <= G.vexnum; j++)
{
if (G.arr[i][j] == INF) //无穷大弄得更好看点
cout << "∞" << " ";
else
cout << " " << G.arr[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
int d[maxs];//顶点与集合s的最短距离
int visit[maxs];//标志数组
int res = 0;//最小生成树的边权值
void prim(AMGraph& G) {
//把数组初始化一下,除了1之外所有点到s集合的距离都是无穷
fill(d + 1, d + G.vexnum + 1, INF);
d[1] = 0;//一开始只有1和S集合距离为0
visit[1] = 1;
//用初始点的路径更新d数组
for (int i = 2; i <= G.vexnum; i++) {
d[i] = min(d[i], G.arr[1][i]);
}
for (int i = 2; i <= G.vexnum; i++) {
int temp =INF;
int t = -1;
//找数组中距离s最小且没有加入集合s的点
for (int j = 2; j <= G.vexnum; j++) {
if (visit[j] == 0 && d[j] < temp) {
temp = d[j];
t = j;
}
}
if (t == -1) {//找不到说明不是连通图
res = INF;
return;
}
visit[t] = 1;
res += d[t];
for (int j = 2; j <= G.vexnum; j++) {
d[j] = min(d[j], G.arr[t][j]);
}
}
if (res == INF) {
cout << "orz";
}
else {
cout << res;
}
}
int main() {
AMGraph G;
initGraph(G);
createGraph(G);
showGraph(G);
prim(G);
}