Prim 算法
求解方法:
首先将所指定的起点作为已选顶点,然后反复在满足如下条件下的边中选择一条最小边,直到
所有顶点已成为已选顶点为止(选择n-1条边)。
1 #include "iostream" 2 using namespace std; 3 4 typedef char Vertextype;//顶点类型 5 typedef int Edgetype;//边的权值类型 6 7 const int maxvex = 100;//最大顶点数目 8 const int infinity = 65535;//无穷大 9 10 typedef struct 11 { 12 Vertextype vexs[maxvex];//图的定点存储 13 Edgetype edge[maxvex][maxvex];//图的边 14 int numVerTex,numEdge;//图的顶点数和边数 15 }graph; 16 17 typedef struct{//候选边存储结构 18 Vertextype vertex;//未选定点对应候选边的另一顶点 19 int weight;//未选顶点对应候选边的权值 20 }MinEdgeType; 21 22 typedef MinEdgeType MinEdgeArray[maxvex];//候选边的结构 23 24 /* 25 *图G中是否存在边(v,u) 26 */ 27 bool have_edge( graph *&g,int v,int u) 28 { 29 if(g->edge[v][u]!=infinity)return true; 30 else return false; 31 } 32 33 /* 34 *初始化顶点v0候选边集 35 */ 36 int Init_MinEdges(graph *&g,MinEdgeArray &MinEdges,int v0) 37 { 38 int i; 39 for(i=0;i<g->numVerTex;i++)//初始化每个未选顶点随影的候选边的相关信息 40 { 41 if(have_edge(g,v0,i))//若G中存在边(v0,i),设置顶点i到起点v0的候选信息,内容包括 42 { 43 MinEdges[i].vertex = g->vexs[v0]; 44 MinEdges[i].weight = g->edge[v0][i];//另一短点以及相应的权值 45 }else MinEdges[i].weight = infinity;//否则,(v0,i)边不存在 46 } 47 return 0; 48 } 49 50 /* 51 *判断顶点v是否被选择 52 */ 53 bool judge(Vertextype v,Vertextype select[],int n) 54 { 55 int i; 56 bool flags = true; 57 for(i=0;i<n;i++) 58 { 59 if(select[i]==v) 60 { 61 flags = false; 62 break; 63 } 64 } 65 return flags; 66 } 67 68 /* 69 *从候选边集中选出最短的顶点 70 */ 71 int Get_MinEdge(graph *&g,MinEdgeArray &MinEdges,Vertextype select[],int n) 72 { 73 int MMin,i,k; 74 MMin = infinity; 75 for(i=0;i<g->numVerTex;i++) 76 { 77 if((judge(g->vexs[i],select,n))&&(MinEdges[i].weight<=MMin)) 78 { 79 k = i; 80 MMin = MinEdges[i].weight; 81 } 82 } 83 return k; 84 } 85 86 /* 87 *对新选出的候选顶点k调整当前候选边集 88 */ 89 int change_MinEdge_with(graph *&g,MinEdgeArray &MinEdges,int k,Vertextype select[],int n) 90 { 91 int i; 92 for(i=0;i<g->numVerTex;i++) 93 { 94 if(judge(g->vexs[i],select,n))//i是未选定点 95 { 96 if(have_edge(g,k,i)&&(g->edge[k][i]<MinEdges[i].weight))//若i到k有更小的边 97 { 98 MinEdges[i].vertex = g->vexs[k]; 99 MinEdges[i].weight = g->edge[k][i]; 100 } 101 } 102 } 103 return 0; 104 } 105 106 /* 107 *prim 108 */ 109 int prim(graph *&g,int v0) 110 { 111 int count = 0; 112 Vertextype select_vertex[maxvex]; 113 MinEdgeArray MinEdges; 114 int i,j,k; 115 select_vertex[count++] = g->vexs[v0]; 116 Init_MinEdges(g,MinEdges,v0); 117 for(i=0;i<g->numVerTex-1;i++) 118 { 119 k = Get_MinEdge(g,MinEdges,select_vertex,count); 120 select_vertex[count++] = g->vexs[k]; 121 change_MinEdge_with(g,MinEdges,k,select_vertex,count); 122 } 123 cout<<"Prim:"; 124 for(i=0;i<count;i++){ 125 if(i!=count-1)cout<<select_vertex[i]<<"->"; 126 else cout<<select_vertex[i]<<endl; 127 } 128 cout<<endl; 129 return 0; 130 } 131 int create(graph *&g) 132 { 133 int i,j,k,weight; 134 cout<<"input numVerTex(顶点数):"; 135 cin>>g->numVerTex; 136 cout<<"input numEdge(边数):"; 137 cin>>g->numEdge; 138 cout<<"input(各顶点):"<<endl; 139 for(i=0;i<g->numVerTex;i++) 140 { 141 cin>>g->vexs[i]; 142 } 143 for(i=0;i<g->numVerTex;i++) 144 { 145 for(j=0;j<g->numEdge;j++) 146 { 147 g->edge[i][j] = infinity; 148 } 149 } 150 cout<<"input(各边两个顶点对应的下标和权值i,j,weight,edge[i][j]=weight):"<<endl; 151 for(k=0;k<g->numEdge;k++) 152 { 153 cout<<"i,j,weight:"; 154 cin>>i>>j>>weight; 155 g->edge[i][j] = weight; 156 g->edge[j][i] = weight; 157 158 } 159 cout<<endl; 160 return 0; 161 } 162 163 int main() 164 { 165 graph *g = new graph; 166 create(g); 167 Vertextype invertex; 168 int start; 169 cout<<"input start invertex:"; 170 cin>>invertex; 171 172 for(int i=0;i<g->numVerTex;i++) 173 { 174 if(g->vexs[i]==invertex){ 175 start = i; 176 } 177 } 178 prim(g,start); 179 return 0; 180 }