一些经典的图论算法(c++描述)

《一些经典的图论算法(c++描述)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一些经典的图论算法，C++描述。#include//常量定义：constintmaxV=100;constdoubleInf=1e100;//constintInf=2000000000;//Graph类定义：templatestructGraphMatrix{intv;//顶点数inte;//边数Ta[maxV][maxV];//邻接矩阵voidinit(){memset(a,0,sizeof(a));}voidclear(){inti,j;for(i=0;i

2、jusingstd::list;templatestructGraphList{intv;inte;lista[maxV];//邻接表voidclear(){//clear()应在更改v之前进行inti;for(i=0;i

3、)：g*输出：屏幕*/GraphListg;intcnt;intpre[maxV];//DFS顺序intlow[maxV];//最低前序编号：儿子low值的最小值void_bridge(intprnt,intw){intv;//sonlow[w]=pre[w]=cnt++;std::list::iteratorli;for(li=g.a[w].begin();li!=g.a[w].end();++li){v=*li;if(pre[v]==-1){_bridge(w,v);if(low[w]>low[v])l

4、ow[w]=low[v];if(low[v]==pre[v])printf("%d-%d",w,v);//找到桥}elseif(v!=prnt&&low[w]>pre[v])low[w]=pre[v];}}voidbridge(){cnt=0;memset(pre,-1,sizeof(pre));_bridge(-1,0);}}namespaceGabowNS{/**//*解决：强分量*算法：Gabow——O(E)*输入：图(表)：g*输出：分量编号sc[]*/GraphListg;intcnt0,cnt1;in

5、tsc[maxV];//分量编号intpre[maxV];//DFS顺序intpath[maxV],pp;//path栈intstack[maxV],sp;//栈void_SCdfsR(intw){pre[w]=cnt0++;stack[sp++]=w;path[pp++]=w;intv;std::list::iteratorli;for(li=g.a[w].begin();li!=g.a[w].end();++li){v=*li;if(pre[v]==-1)_SCdfsR(v);elseif(sc[v]==-1){

6、while(pre[path[pp-1]]>pre[v])--pp;}}if(path[pp-1]!=w)return;--pp;do{sc[stack[--sp]]=cnt1;}while(stack[sp]!=w);++cnt1;}voidinit(){memset(pre,-1,sizeof(pre));memset(sc,-1,sizeof(sc));cnt0=cnt1=0;sp=pp=0;inti;for(i=0;i

7、ch(ints,intt){returnsc[s]==sc[t];}}namespacePrimNS{/**//*解决：最小生成树MST*算法：Prim——O(V^2)*输入：加权连通图(矩阵)：g*输出：父节点st[]，与其父之边的权重wt[]*/GraphMatrixg;intst[maxV];//MST节点之父——用以保存MSTdoublewt[maxV+1];//与其父的边的权重intfr[maxV];//非树顶点的最近树顶点voidmst(){intv,w,min;for(v=0;v

8、{st[v]=-1;fr[v]=v;wt[v]=Inf;}st[0]=0;wt[g.v]=Inf;for(min=0;min!=g.v;){v=min;st[v]=fr[v];for(w=0,min=g.v;w