/*最小生成树（Prim算法）
思路：
首先，定义一个shortedge的结构体，每个点的最小权值边为与0 的权值
其次，先求出最小权值边输出，改变其他各点的最小权值与边
*/
#include<iostream>
#include<stdlib.h>
#include<string.h>
const int Max_Size = 100;
using namespace std;
struct ShortEdge
{
int lowcost;//最短边的权值
int adjvex;//最短边的邻接点
};
int minedge(ShortEdge str[], int n)
{
int min = 10000, t = 0;
for(int i = 1; i < n; i++)
{
if(str[i].lowcost < min && str[i].lowcost != 0)
{
min = str[i].lowcost;
t = i;
}
}
return t;
}
class Prim
{
private:
int spot, vertex;
int index;
int node[Max_Size][Max_Size];
ShortEdge shortedge[Max_Size];
public:
Prim()
{
spot = vertex = 0;
index = -1;
}
~Prim() {}
void creat(int n, int m)
{
spot = n;
vertex = m;
for(int i = 0; i < spot; i++)
{
for(int j = 0; j < spot; j++)
{
node[i][j] = 10000;
}
}
while(++index < vertex)
{
int i, j, a;
cin >> i >> j >> a;
node[i][j] = node[j][i] = a;
}
for(int i = 1; i < spot; i++)
{
shortedge[i].lowcost = node[0][i];
shortedge[i].adjvex = 0;
}
shortedge[0].lowcost = shortedge[0].adjvex = 0;
}
void pop()
{
cout << 0 << " ";
for(int i = 1; i < spot; i++)
{
int k = minedge(shortedge, spot); //找到最小权值的边
cout << k << " ";
shortedge[k].lowcost = 0;
for(int j = 1; j < spot; j++) //改变其他各点的最先权值
{
if(node[k][j] < shortedge[j].lowcost)
{
shortedge[j].lowcost = node[k][j];
shortedge[j].adjvex = k;
}
}
}
}
};
int main()
{
Prim p;
p.creat(6, 9);
p.pop();
} |
|
转播
