最小生成树(MST)算法 Prim

/*--------------------------------------
* 最小生成树(MST)算法 Prim 和 Kruskal
* 所谓最小生成树（MST)就是构造连通网的最小代价的生成树。
* 举个例子：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。
* 这就需要考虑一个问题，如何在最节省经费的前提下建立这个通信网。即在n(n-1)/2条线路中选出n-1条线路且网络连通，代价最小。
* 这便是最小生成树的经典应用实例。
* -------------------------------------*/

#include <iostream>
using namespace std;

#define MAX_VERTEX_NUM 100
#define VexType int
#define EdgeType int
#define MAXNUM 65535

// 采用邻接矩阵的方法表示图

typedef struct MGraph {
VexType vex[MAX_VERTEX_NUM];
EdgeType edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum, edgenum;
}MGraph;

// 图的创建
void CreateGraph(MGraph &G, int n, int e) {
G.vexnum = n;
G.edgenum = e;
cout << "请输入你的顶点：" << endl;
VexType v;
for (int i = 0; i < G.vexnum; i++) {
  cin >> v;
  G.vex[i] = v;
}
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
   G.edge[i][j] = MAXNUM;
  }
}

cout << "请输入你的边的信息：（例如顶点1与2之间有边权值为6，输入1 2 6）" << endl;
int a, b, c;
for (int i = 0; i < e; i++) {
cin >> a >> b >> c;
G.edge[a][b] = G.edge[b][a] = c;
}
}

// 深度优先搜索
int visited[MAX_VERTEX_NUM];
void DFS(MGraph &G, int i) {
visited[i] = 1;
cout << G.vex[i] << "    ";
for (int ii = 0; ii < G.vexnum; ii++) {
  if (G.edge[i][ii]!= MAXNUM && visited[ii] == 0) {
   DFS(G, ii);
  }
}
}

void DFS_Traverse(MGraph &G) {
for (int i = 0; i < G.vexnum; i++) {
  visited[i] = 0;
}
for (int i = 0; i < G.vexnum; i++)
{
  if (!visited[i]) {
   DFS(G, i);
  }
}
}

// Prim:从图G的第start个顶点出发的最小生成树
void MinSpanTree_Prim(MGraph &G,int start) {
int index = 0; // prim最小树顶点的索引
VexType *primTree = new VexType[G.vexnum];// primTree的结果数组
int *weight = new int[G.vexnum]; // 顶点间边的信息
int min; // 最小权值
int minflag = 0;

primTree[index] = G.vex[start];
index++; // 初始化从顶点start开始

for (int i = 0; i < G.vexnum; i++) {
weight[i] = G.edge[start][i];
}

weight[start] = 0; // weight[i] = 0 表示顶点i已经加入到生成树中

for (int i = 0; i < G.vexnum; i++) {
  if (i == start)
   continue;
  min = MAXNUM;
  for (int j = 0; j < G.vexnum; j++) {
   if (weight[j] != 0 && weight[j] < min) {
    min = weight[j];
    minflag = j;
   }
  }
  primTree[index] = G.vex[minflag];
  index++;

  weight[minflag] = 0;

  for (int j = 0; j < G.vexnum; j++) {
   // 当第j个节点没有被处理，并且需要更新时才更新
   if (weight[j] != 0 && G.edge[minflag][j] < weight[j]) {
    weight[j] = G.edge[minflag][j];
   }
  }
}

// 计算最小生成树的权值
int sum = 0;
for (int i = 0; i < index; i++) {
cout << primTree[i] << endl;
}
}

int main() {
MGraph G;
int n, e;
cout << "输入顶点数和边数：" << endl;
cin >> n >> e;
CreateGraph(G, n, e);
DFS_Traverse(G);
cout << endl;
MinSpanTree_Prim(G, 0);
system("pause");
return 0;
}