[分享]基于启发式的度约束最小生成树的算法研究

sll1223 · 发表于 2006-4-20 21:32

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？我要加入

x

如题，我正在做毕设，课题是：基于启发式的度约束最小生成树的算法研究，倘若哪位仁兄见到过c/c++的源代码，请帮帮忙。谢了先~~~[em05]

[此贴子已经被风花雪月于2006-5-15 10:26:27编辑过]

HEROII · 发表于 2006-4-22 21:38

最小生成树我知道。有什么prim 算法等。但那时给予网络拓扑数据的。我不晓得你这个和那个有什么关系。

风花雪月 · 发表于 2006-5-15 10:30

最小生成树prim算法 const int CNST_NumGrphNodes = 101 ; // 最小生成树元素 struct TTreeEdge { int v1, v2; double w; } ; // 候选集元素 struct TCloseRec { double lowCost; int vec; } ; int MST_prim( int g[][CNST_NumGrphNodes], int n, TTreeEdge * minTree) { int i, j, k; TCloseRec * close = new TCloseRec[n]; for (i = 1 ; i < n; i ++ ) { close.vec = 0 ; close.lowCost = g[ 0 ]; } close[ 0 ].lowCost = - 1 ; for (i = 0 ; i < n - 1 ; i ++ ) { // 找图点 for (k = 1 ; k < n; k ++ ) { if (close[k].lowCost != - 1 ) { break ; } } for (j = k + 1 ; j < n; j ++ ) { if (close[j].lowCost != - 1 ) { if (close[j].lowCost < close[k].lowCost) { k = j; } } } // 加入树中 minTree.v1 = k; minTree.v2 = close[k].vec; minTree.w = close[k].lowCost; close[k].lowCost = - 1 ; // 调整候选集 for (j = 1 ; j < n; j ++ ) { if (close[j].lowCost > g[j][k]) { close[j].lowCost = g[j][k]; close[j].vec = k; } } } delete []close; return 0 ; }

风花雪月 · 发表于 2006-5-15 10:30

另一个程序 #include<IOSTREAM.H> #include<CONIO.H> #include"graph.h" const int MAX_VERTEX_NUM=100; typedef char VertexType; typedef int ARType; typedef struct { VertexType adjvex;//定义顶点的类型； ARTypelowcost;//定义该边上的权； }minside[MAX_VERTEX_NUM];//村顶点和权 int Locatevex(Graph G,VertexType u) {//为U的顶点在邻接矩阵表示中的数组的下标 for(int n=1;n<=G.vexnum;n++) { if(u==G.vex[n]) return n; } return -1; } int minimum(minside SZ,Graph G) { int i=1,j,k,min; while(!SZ.lowcost) ++i; min=SZ.lowcost; k=i; for(j=i+1;j<=G.vexnum;j++) { if(SZ[j].lowcost>0) { if(min>SZ[j].lowcost) { min=SZ[j].lowcost;k=j; } } } return k; } void MiniSpanTree_PRIM(Graph G,VertexType u)//用普里姆算法从第u个顶点出发构造最小生成树T，输出T的各边。 { int i,j,k; minside closedge; k=Locatevex(G,u); for(j=1;j<=G.vexnum;j++) {//closedge数组初始化 if(j!=k) {closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j];} } closedge[k].lowcost=0; cout<<"最小代价生成树的各边："<<ENDL; for(i=2;i<=G.vexnum;i++) { k=minimum(closedge,G); cout<<"("<<CLOSEDGE[K].ADJVEX<<"_"<<G.VEX[K]<<")"; closedge[k].lowcost=0; for(int m=1;m<=G.vexnum;++m) { if(G.arcs[k][m]<CLOSEDGE[M].LOWCOST) {closedge[m].adjvex=G.vex[k];closedge[m].lowcost=G.arcs[k][m];} } } } int main() { Graph p; VertexType u='a'; int n,e; cout<<"以邻接矩阵存储图的相关操作"<<ENDL; cout<<"顶点数："; cin>>n; cout<<"边数："; cin>>e; Creat(p,n,e); cout<<"打印邻接矩阵："<<ENDL; print(p); MiniSpanTree_PRIM(p,u); return 1; getch(); }

风花雪月 · 发表于 2006-5-15 10:31

你还可以参考<a href="http://course.cug.edu.cn/cugFirst/discrete_mathe/netClass/tree/contents/06-02-guid.htm" target="_blank" >http://course.cug.edu.cn/cugFirst/discrete_mathe/netClass/tree/contents/06-02-guid.htm</A>

账号		自动登录	找回密码
密码			我要加入

[经典算法] [分享]基于启发式的度约束最小生成树的算法研究

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

回复：（sll1223）[分享]基于启发式的度约束最小生成树...

回复：（sll1223）[分享]基于启发式的度约束最小生成树...

回复：（sll1223）[分享]基于启发式的度约束最小生成树...