求解决一道c++ prim算法的题
输出说明 :
第一行：图的类型
第二行：顶点集
空行
第三行：邻接矩阵（列与列之间用格式控制符'\t'分隔）
第四行：各条边以及它们的权值，输出格式为：
(c,b,5),(d,c,3),(e,d,8),(a,e,14),(d,f,21),(e,g,16)
其中，每个括号内的信息为一条边，格式为（邻接点, 自己, 权值），边的输出顺序为按照（自己这个）点的编号顺序输出。“自己这个”不包括起始点，比如范例中输出的边不包括起始点a，也就是没有(,a,)。
输入范例
UDN
7
a b c d e f g
9999
11
0 1
0 4
0 6
1 2
1 3
1 4
2 3
3 4
3 5
4 6
5 6
19 14 18 5 7 12 3 8 21 16 27
0
输出范例
UDN
a b c d e f g
9999 19 9999 9999 14 9999 18
19 9999 5 7 12 9999 9999
9999 5 9999 3 9999 9999 9999
9999 7 3 9999 8 21 9999
14 12 9999 8 9999 9999 16
9999 9999 9999 21 9999 9999 27
18 9999 9999 9999 16 27 9999
(c,b,5),(d,c,3),(e,d,8),(a,e,14),(d,f,21),(e,g,16)
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
bool vis[1000];
template <class TypeOfVer, class TypeOfEdge>
class adjmatrix_graph {
private:
int Vers; //顶点数
int Edges; //边数
TypeOfEdge **edge; //存放邻接矩阵（TypeOfEdge表示顶点关系类型。对于无权图，用1或0，表示相邻否；对于带权图，则为权值类型）
TypeOfVer *ver; //存放结点值
TypeOfEdge noEdge; //邻接矩阵中的∞的表示值
string GraphKind; //图的种类标志
bool DFS(int u, int &num, int visited[]); // DFS遍历（递归部分）
bool CheckRoute(int u, int v, int visited[]);
public:
adjmatrix_graph(const string &kd, int vSize, const TypeOfVer d[], const TypeOfEdge noEdgeFlag); //构造函数构造一个只有结点没有边的图。4个参数的含义：图的类型、结点数、结点值和邻接矩阵中表示结点间没有边的标记（无权图：0，有权图：输入参数定）
adjmatrix_graph(const string &kd, int vSize, int eSize, const TypeOfVer d[], int **e); //构造函数构造一个无权图。5个参数的含义：图的类型、结点数、边数、结点集和边集
adjmatrix_graph(const string &kd, int vSize, int eSize, const TypeOfEdge noEdgeFlag, const TypeOfVer d[], int e[][2], const TypeOfEdge w[]); //构造函数构造一个有权图。7个参数的含义：图的类型、结点数、边数、无边标记、结点集、边集、权集
bool GraphisEmpty() {
return Vers == 0;
} //判断图空否
string GetGraphKind() {
return GraphKind;
}
bool GetVer(int u, TypeOfVer &data); //取得G中指定顶点的值
int GetFirstAdjVex(int u, int &v); //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1
int GetNextAdjVex(int u, int v, int &w); //返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1
bool PutVer(int u, TypeOfVer data); //对G中指定顶点赋值
bool InsertVer(const TypeOfVer &data); //往G中添加一个顶点
bool Printvers(); //输出顶点集
int LocateVer(TypeOfVer data); //返回G中指定顶点的位置
bool PrintMatrix(); //输出邻接矩阵
bool CheckRoute(int u, int v);
int Get_InDegree(int u);
int Get_Degree(int u);
bool ExistEdge(int u, int v);
bool TopSort();
bool U_Judge_Cir();
int GetVerNum() {
return Vers;
} //取得当前顶点数
int GetEdgeNum() {
return Edges;
} //取得当前边数
bool Insert_Edge(int u, int v); //无权图插入一条边
bool Insert_Edge(int u, int v, TypeOfEdge w); //有权图插入一条边
bool DeleteVer(const TypeOfVer &data); //往G中删除一个顶点
bool Delete_Edge(int u, int v); //无权图删除一条边
bool Delete_Edge(int u, int v, TypeOfEdge w); //有权图删除一条边
void DFS_Traverse(int u); // DFS遍历（外壳部分）
void BFS_Traverse(int u); // BFS遍历
bool Prim(int u, int adjvex[], TypeOfEdge lowcost[]); // Prim算法求最小生成树
~adjmatrix_graph(){}; //析构函数
};
template <class TypeOfVer, class TypeOfEdge>
adjmatrix_graph<TypeOfVer, TypeOfEdge>::adjmatrix_graph(const string &kd, int vSize, int eSize, const TypeOfEdge noEdgeFlag, const TypeOfVer d[], int e[][2], const TypeOfEdge w[]) {
//构造函数构造一个有权图。7个参数的含义：图的类型、结点数、边数、无边标记、结点集、边集、权集
GraphKind = kd;
Vers = vSize;
Edges = eSize;
noEdge = noEdgeFlag;
ver = new TypeOfVer[vSize];
edge = new TypeOfEdge *[eSize];
for (int i = 0; i < vSize; i++) ver[i] = d[i];
for (int i = 0; i < vSize; i++) {
edge[i] = new TypeOfEdge[vSize];
for (int j = 0; j < vSize; j++) {
edge[i][j] = noEdge;
}
}
for (int i = 0; i < eSize; i++) {
edge[e[i][0]][e[i][1]] = w[i];
if (GraphKind == "UDN")
edge[e[i][1]][e[i][0]] = w[i];
}
}
template <class TypeOfVer, class TypeOfEdge>
bool adjmatrix_graph<TypeOfVer, TypeOfEdge>::Printvers() {
for (int i = 0; i < Vers; i++) {
if (i) cout << ' ';
cout << ver[i];
}
cout << endl;
return 0;
}
template <class TypeOfVer, class TypeOfEdge>
bool adjmatrix_graph<TypeOfVer, TypeOfEdge>::PrintMatrix() {
for (int i = 0; i < Vers; i++) {
for (int j = 0; j < Vers; j++) {
cout << edge[i][j] << '\t';
}
cout << endl;
}
return true;
}
template <class TypeOfVer, class TypeOfEdge>
bool adjmatrix_graph<TypeOfVer, TypeOfEdge>::Prim(int u, int adjvex[], TypeOfEdge lowcost[]) {
bool flag[Vers] = {false};
int dist[Vers];
for (int i = 0; i < Vers; i++) dist[i] = noEdge;
dist[u] = 0;
for (int i = 0; i < Vers; i++) {
int minidx = -1;
for (int j = 0; j < Vers; j++) {
if (!flag[j] && (minidx == -1 || dist[minidx] > dist[j])) {
minidx = j;
}
}
lowcost[minidx] = dist[minidx];
flag[minidx] = true;
for (int j = 0; j < Vers; j++) {
if (dist[j] > edge[minidx][j]) {
dist[j] = edge[minidx][j];
adjvex[j] = minidx;
}
}
}
return 1;
}
int main() {
string kind;
int vSize, eSize, start, noEdgeFlag;
cin >> kind; //输入类型
cin >> vSize; //结点数
char d[vSize];
for (int i = 0; i < vSize; i++) {
cin >> d[i]; //结点集
}
cin >> noEdgeFlag; // 无边标记
cin >> eSize; //边数
int edgs[eSize][2], w[eSize];
for (int i = 0; i < eSize; i++) { //输入边集
cin >> edgs[i][0] >> edgs[i][1];
}
for (int i = 0; i < eSize; i++) { //输入边集
cin >> w[i];
}
cin >> start;
adjmatrix_graph<char, int> T(kind, vSize, eSize, noEdgeFlag, d, edgs, w); //构造图
cout << T.GetGraphKind() << endl;
T.Printvers(); //打印顶点集
cout << endl;
T.PrintMatrix(); //打印邻接表
int adjvex[vSize], lowcost[vSize];
T.Prim(start, adjvex, lowcost);
for (int i = 0; i < vSize - 1; i++) {
if (i != start) {
// （邻接点, 自己, 权值）
cout << '(' << d[adjvex[i]] << ',' << d[i] << ',' << lowcost[i] << ')' << ',';
}
}
if (vSize - 1 != start)
cout << '(' << d[adjvex[vSize - 1]] << ',' << d[vSize - 1] << ',' << lowcost[vSize - 1] << ')';
return 0;
}
#include <iostream>
using namespace std;
#define INFINE 99999999//假装自己是无穷大
const int N = 1010;
int graph[N][N];
int vertexnum, arcnum;
//lowcost[i]:表示以i为终点的边的最小权值,
//当lowcost[i]=0说明以i为终点的边的最小权值=0,
//也就是表示i点加入了MST
//mst[i]:表示对应lowcost[i]的起点，
//即说明边<mst[i],i>是MST的一条边
void Prim(int v, int n) {
int sum = 0;
int locatest[N];
int mst[N];
for (int i = 1; i <= n; i++) {
locatest[i] = graph[v][i];
mst[i] = v;
}
mst[v] = 0;
locatest[v] = 0;
for (int i = 2; i <= n; i++) {
int minx = INFINE;
int minid = 0;
for (int k = 1; k <= n; k++) {
if (locatest[k] != 0 && locatest[k] < minx) {
minx = locatest[k];
minid = k;
}
}
cout << "V" << mst[minid] << "-" << "V" << minid << " = " << minx << endl;
locatest[minid] = 0;
sum += minx;
for (int i = 1; i <= n; i++) {
if ( graph[minid][i] < locatest[i]) {
locatest[i] = graph[minid][i];
mst[i] = minid;
}
}
}
cout << sum << endl;
return;
}
void CreateGraph() {
cin >> vertexnum >> arcnum;//输入点的个数，边的条数
for (int i = 1; i <= vertexnum; i++)
for (int j = 1; j <= vertexnum; j++)
graph[i][j] = INFINE;
for (int i = 1; i <= arcnum; i++) {
int a, b, w;
cin >> a >> b >> w;
graph[a][b] = w;//无向图,故两边都要赋值
graph[b][a] = w;
}
}
int main() {
CreateGraph();
Prim(1, vertexnum);//以点1为最小生成树的起点
return 0;
}