《一些经典的图论算法(C++描述).doc》由会员分享，可在线阅读，更多相关《一些经典的图论算法(C++描述).doc（37页珍藏版）》请在金锄头文库上搜索。
1、一些经典的图论算法，C+描述。 #include / 常量定义： const int maxV = 100 ; const double Inf = 1e100; / const int Inf=2000000000; / Graph类定义： template struct GraphMatrix int v; / 顶点数 int e; / 边数 T amaxVmaxV; / 邻接矩阵 void init() memset(a, 0 , sizeof (a); void clear() int i,j; for (i = 0 ; i v; + i) for (j = 0 ; j v; + j)
2、 aij = Inf; ;#include using std:list;template struct GraphList int v; int e; list amaxV; / 邻接表 void clear() / clear()应在更改v之前进行 int i; for (i = 0 ; i v; i + ) ai.clear(); GraphList() v = maxV; clear(); ; namespace bridgeNS /*/ /* 解决：查找、打印桥 *算法：DFSO(E) *输入：连通图(表)：g *输出：屏幕 */ GraphList g; int cnt; int
3、premaxV; / DFS顺序 int lowmaxV; / 最低前序编号：儿子low值的最小值 void _bridge( int prnt, int w) int v; / son loww = prew = cnt + ; std:list :iterator li; for (li = g.aw.begin(); li != g.aw.end(); + li) v =* li; if (prev =- 1 ) _bridge(w,v); if (loww lowv) loww = lowv; if (lowv = prev) printf( %d-%dn ,w,v); / 找到桥 e
4、lse if (v != prnt & loww prev) loww = prev; void bridge() cnt = 0 ; memset(pre, - 1 , sizeof (pre); _bridge( - 1 , 0 ); namespace GabowNS /*/ /* 解决：强分量 *算法：GabowO(E) *输入：图(表)：g *输出：分量编号sc */ GraphList g; int cnt0, cnt1; int scmaxV; / 分量编号 int premaxV; / DFS顺序 int pathmaxV,pp; / path栈 int stackmaxV,s
5、p; / 栈 void _SCdfsR( int w) prew = cnt0 + ; stacksp + = w; pathpp + = w; int v; std:list :iterator li; for (li = g.aw.begin(); li != g.aw.end(); + li) v =* li; if (prev =- 1 ) _SCdfsR(v); else if (scv =- 1 ) while (prepathpp - 1 prev) - pp; if (pathpp - 1 != w) return ; - pp; do scstack - sp = cnt1;
6、 while (stacksp != w); + cnt1; void init() memset(pre, - 1 , sizeof (pre); memset(sc, - 1 , sizeof (sc); cnt0 = cnt1 = 0 ; sp = pp = 0 ; int i; for (i = 0 ; i g.v; + i) if (sci =- 1 ) _SCdfsR(i); bool isStrongReach( int s, int t) return scs = sct; namespace PrimNS /*/ /* 解决：最小生成树MST *算法：PrimO(V2) *输
7、入：加权连通图(矩阵)：g *输出：父节点st，与其父之边的权重wt */ GraphMatrix g; int stmaxV; / MST节点之父用以保存MST double wtmaxV + 1 ; / 与其父的边的权重 int frmaxV; / 非树顶点的最近树顶点 void mst() int v, w, min; for (v = 0 ; v g.v; + v) stv =- 1 ; frv = v; wtv = Inf; st 0 = 0 ; wtg.v = Inf; for (min = 0 ; min != g.v;) v = min; stv = frv; for (w =
8、 0 , min = g.v; w g.v; + w) if (stw =- 1 ) if (g.avw wtw) wtw = g.avw, frw = v; if (wtw wtmin) min = w; namespace DijkstraNS /*/ /* 解决：非负权图单源最短路径树SPT *算法：DijkstraO(V2) *输入：加权连通图(矩阵)：g *输出：父节点st，与其父之边的权重wt */ GraphMatrix g; int stmaxV; double wtmaxV + 1 ; int frmaxV; / 非树顶点的最近树顶点 void spt( int s) int
9、 v, w, min; for (v = 0 ; v g.v; + v) stv =- 1 ; frv = v; wtv = Inf; sts = s; wtg.v = Inf; wts = 0 ; for (min = s; min != g.v;) v = min; stv = frv; for (w = 0 , min = g.v; w g.v; + w) if (stw =- 1 ) if (g.avw != Inf & wtv + g.avw wtw) wtw = wtv + g.avw, frw = v; if (wtw wtmin) min = w; /*/ /*/ namespace FloydNS /
