プリムアルゴリズム最小生成ツリー(MST-Prim algorithm)を求める
最小生成ツリー:重み付き生成ツリーの各エッジの重み値の和をこのツリーの代価と呼びます.最小コスト生成ツリーは、各エッジの重み値の合計が最小の生成ツリーです.
プリムアルゴリズム(Prim)ステップ:
1、最小生成ツリーのノードとしてソースポイントを選択し、生成ツリーに現在接続されている最良の状況、すなわち重み値が最小のエッジを初期化する
2、ウェイト値が最も小さいエッジを選択して生成ツリーに追加し、各頂点の最適状況を更新します.
3、すべての頂点が生成ツリーに追加されるまで手順2を繰り返します.
コードは次のとおりです.
#include#include#include#define MAX 100#define INF 1000000 typedef struct{int adjvex;//格納されているこの重みの最小エッジの別の頂点int lowcost;//格納されているこの重みの最小エッジの重み値}Path;typedef struct { int arc[MAX][MAX]; int arcnum, vexnum; }AGraph; AGraph T; int minclosedge(Path closedge[]) { int min, j, k; min = INF; k = -1; for (j = 0; j < T.vexnum; j++) { if (closedge[j].lowcost != 0 && closedge[j].lowcost < min) { min = closedge[j].lowcost; k = j; } } return k; } void prim(AGraph T,int u)/始点u{int i,j,k;Path closedge[MAX];for(j=0;jコンパイル環境:Visual Studio
プリムアルゴリズム(Prim)ステップ:
1、最小生成ツリーのノードとしてソースポイントを選択し、生成ツリーに現在接続されている最良の状況、すなわち重み値が最小のエッジを初期化する
2、ウェイト値が最も小さいエッジを選択して生成ツリーに追加し、各頂点の最適状況を更新します.
3、すべての頂点が生成ツリーに追加されるまで手順2を繰り返します.
コードは次のとおりです.
#include#include#include#define MAX 100#define INF 1000000 typedef struct{int adjvex;//格納されているこの重みの最小エッジの別の頂点int lowcost;//格納されているこの重みの最小エッジの重み値}Path;typedef struct { int arc[MAX][MAX]; int arcnum, vexnum; }AGraph; AGraph T; int minclosedge(Path closedge[]) { int min, j, k; min = INF; k = -1; for (j = 0; j < T.vexnum; j++) { if (closedge[j].lowcost != 0 && closedge[j].lowcost < min) { min = closedge[j].lowcost; k = j; } } return k; } void prim(AGraph T,int u)/始点u{int i,j,k;Path closedge[MAX];for(j=0;j