算法及编程语言 - 声振论坛 - 振动,动力学,声学,信号处理,故障诊断

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

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

如题，我正在做毕设，课题是：基于启发式的度约束最小生成树的算法研究，倘若哪位仁兄见到过c/c++的源代码，请帮帮忙。谢了先~~~
[此贴子已经被风花雪月于2006-5-15 10:26:27编辑过]

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

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

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

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

最小生成树prim算法 const intCNST_NumGrphNodes= 101 ; // 最小生成树元素 structTTreeEdge { intv1, v2; doublew; } ; // 候选集元素 structTCloseRec { doublelowCost; intvec; } ; intMST_prim( intg[],intn, TTreeEdge* minTree) { inti, j, k; TCloseRec* close= newTCloseRec; 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.lowCost!= - 1 ) { break ; } } for(j = k + 1 ; j < n; j ++ ) { if(close.lowCost!= - 1 ) { if(close.lowCost<close.lowCost) { k=j; } } } // 加入树中 minTree.v1=k; minTree.v2=close.vec; minTree.w=close.lowCost; close.lowCost= - 1 ; // 调整候选集 for(j = 1 ; j < n; j ++ ) { if(close.lowCost>g) { close.lowCost=g; close.vec=k; } } } delete []close; return 0 ; }

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

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

另一个程序 #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;//村顶点和权 int Locatevex(Graph G,VertexType u) {//为U的顶点在邻接矩阵表示中的数组的下标 for(int n=1;n<=G.vexnum;n++) { if(u==G.vex) 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.lowcost>0) { if(min>SZ.lowcost) { min=SZ.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.adjvex=u;closedge.lowcost=G.arcs;} } closedge.lowcost=0; cout<<"最小代价生成树的各边："<<ENDL; for(i=2;i<=G.vexnum;i++) { k=minimum(closedge,G); cout<<"("<<CLOSEDGE.ADJVEX<<"_"<<G.VEX<<")"; closedge.lowcost=0; for(int m=1;m<=G.vexnum;++m) { if(G.arcs<CLOSEDGE.LOWCOST) {closedge.adjvex=G.vex;closedge.lowcost=G.arcs;} } } } 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

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

你还可以参考<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>

页: [1]

声振论坛's Archiver

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

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

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

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