这里默认了结点值为数组下标+1
#include<iostream>using namespace std;#define MVnum 100typedef int ElemType;typedef struct AFGraph{ElemType vexs[MVnum];int vexNum,arcNum;int arcs[MVnum][MVnum];bool visited[MVnum];}AFGraph;struct Closedge{int adjvex;ElemType lowcost;}closedge[MVnum];bool U[MVnum] = {false}; //有无放入最小生成树void Create_Graph(AFGraph &G) //创建{cout << "请输入节点数 和 边数:\n";cin >> G.vexNum >> G.arcNum;for(int i=0;i<G.vexNum;i++)for(int j=0;j<G.vexNum;j++){G.arcs[i][j] = 0;}// printf("请依次输入各结点的值:\n");for(int i=0;i<G.vexNum;i++){// cin >> G.vexs[i];G.vexs[i] = i+1;G.visited[i]= false;}int v1,v2;for(int i=0;i<G.arcNum;i++){cout << "请输入 边的依附结点 以及 边的权值：\n";cin >> v1 >> v2 >> G.arcs[v1-1][v2-1];v1--;v2--;G.arcs[v2][v1] = G.arcs[v1][v2]; }}int Min(AFGraph &G) //选出可以加入最小生成树的顶点{int n;bool sign = true;for(int i=0;i<G.vexNum;i++){if(sign && closedge[i].lowcost!=0) //选出第一个变量，但是要避免为 0{n = i;sign = false;}if(!sign && closedge[i].lowcost!=0)if(closedge[i].lowcost < closedge[n].lowcost ){n = i;}}return n;}int Loacte(AFGraph &G,int v) //定位，给结点值出数组下标，此处默认为节点值 = 下标 + 1，所有这里不需要{int i=0;for(i=0;i<G.vexNum;i++){if(v == G.vexs[i])return i;}return -1;}void MiniSpanTree_Prim(AFGraph G,int u/*下标*/) //主要问题是closedg的更新，要保证原来是0的也要更新{for(int i=0;i<G.vexNum;i++){closedge[i] = {u , G.arcs[u][i]};}U[u] = true; //放入for(int i=1;i<G.vexNum;i++){int k = Min(G),u0,v0;u0 = closedge[k].adjvex + 1;v0 = k+1;printf("(%d , %d)",u0,v0);U[k] = true;closedge[k].lowcost = 0 ;for(int j=0;j<G.vexNum;j++){if(U[j] ==false)if((closedge[j].lowcost > G.arcs[k][j] && (G.arcs[k][j])!=0)/*原来不为0*/ ||(closedge[j].lowcost==0)/*原来为0*/){closedge[j]= {k,G.arcs[k][j]};}}}}void DFS_AM(AFGraph &G,int v) //v从1开始{cout << v;G.visited[v-1] = true;for (int w = 0;w<G.vexNum; w++) //邻接矩阵，寻找下一个邻接点，数组遍历即可if((!G.visited[w]&&(G.arcs[v-1][w]!=0)))DFS_AM(G,w+1);}void ShowCost(AFGraph G){for(int i=0;i<G.vexNum;i++)for(int j=0;j<G.vexNum;j++){if(G.arcs[i][j]!=0){cout << "("<<i+1<<","<<j+1<<") = "<<G.arcs[i][j];}}}int main(int argc, char const *argv[]){AFGraph G;Create_Graph(G);MiniSpanTree_Prim(G,0); //要保证U数组全是falsereturn 0;}
精简版：（直接定义好图）
#include
using namespace std;
const int MAX = 100;
struct Graph
{
int vexNum,edgNum;
int edg[MAX][MAX];//权值，默认为正无穷大
};
bool isSelected[MAX] = {false};
int Path[MAX];//存储当前点到选好的点集的最小距离
int main()
{
Graph G;
G.vexNum = 9;
G.edgNum = 16;
for (int i = 1; i <= G.vexNum;i++)
{
for (int j = 1; j <= G.vexNum;j++)
{
G.edg[i][j] = INT_MAX;
}
}
{G.edg[1][2] = 5; G.edg[2][1] = 5;G.edg[1][9] = 5; G.edg[9][1] = 5;G.edg[1][8] = 2; G.edg[8][1] = 2;G.edg[1][7] = 6; G.edg[7][1] = 6;G.edg[1][6] = 8; G.edg[6][1] = 8;G.edg[1][5] = 10;G.edg[5][1] = 10;G.edg[1][4] = 12;G.edg[4][1] = 12;G.edg[1][3] = 13;G.edg[3][1] = 13;G.edg[2][9] = 1; G.edg[9][2] = 1;G.edg[9][8] = 4; G.edg[8][9] = 4;G.edg[8][7] = 7; G.edg[7][8] = 7;G.edg[7][6] = 6; G.edg[6][7] = 6;G.edg[6][5] = 9; G.edg[5][6] = 9;G.edg[5][4] = 11;G.edg[4][5] = 11;G.edg[4][3] = 9; G.edg[3][4] = 9;G.edg[3][2] = 3; G.edg[2][3] = 3;}isSelected[1] = true;int selectNum = 1;for (int i = 2; i <= G.vexNum;i++){Path[i] = G.edg[1][i];}while (selectNum < G.vexNum) //每次加一当前权值最小点{int Min_Path = INT_MAX,nextPoint = 0;for (int i = 2; i <= G.vexNum; i++) //后面的点找和当前连通并且权值最小的点{if (!isSelected[i] && Path[i] < Min_Path)//找下一个点{nextPoint = i;Min_Path = Path[i];}}printf("选择点%d\n",nextPoint);//更新点集isSelected[nextPoint] = true;//更新边数组for (int i = 2; i <= G.vexNum;i++){if( !isSelected[i] /*未加入点集*/ && G.edg[i][nextPoint] /*如果直接到点nextPoint更近*/< Path[i]){Path[i] = G.edg[i][nextPoint];}}selectNum++;//选好一个点}return 0;
}
