经典图算法的方法分析
本标程介绍了一些经典的图论算法，C++描述。
#include < cstring > // 常量定义： const int maxV = 100 ; const double Inf = 1e100; // constintInf=2000000000; // Graph类定义： template < class T >
struct GraphMatrix {
int v; // 顶点数 int e; // 边数 Ta[maxV][maxV]; // 邻接矩阵
void init() {memset(a, 0 , sizeof (a));
} void clear() { int i,j; for (i = 0 ;i < v; ++ i) { for (j = 0 ;j < v; ++ j)a[i][j] = Inf;} } 
} ;#include < list > using std::list;template < class T > struct GraphList { int v; int e;list < T > a[maxV]; // 邻接表 void clear() { // clear()应在更改v之前进行 int i; for (i = 0 ;i < v;i ++ )a[i].clear();} ~ GraphList() {v = maxV;clear();} } ; namespace bridgeNS { /* 解决：查找、打印桥*算法：DFS——O(E)*输入：连通图(表)：g*输出：屏幕 */ GraphList < int > g; int cnt; int pre[maxV]; // DFS顺序 int low[maxV]; // 最低前序编号：儿子low值的最小值 void _bridge( int prnt, int w) { int v; // son low[w] = pre[w] = cnt ++ ;std::list < int > ::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])low[w] = low[v]; if (low[v] == pre[v])printf( " %d-%d/n " ,w,v); // 找到桥 } else if (v != prnt && low[w] > pre[v])low[w] = pre[v];} } void bridge() {cnt = 0 ;memset(pre, - 1 , sizeof (pre));_bridge( - 1 , 0 );} } namespace GabowNS { /* 解决：强分量*算法：Gabow——O(E)*输入：图(表)：g*输出：分量编号sc[] */ GraphList < int > g; int cnt0,cnt1; int sc[maxV]; // 分量编号 int pre[maxV]; // DFS顺序 int path[maxV],pp; // path栈 int stack[maxV],sp; // 栈 void _SCdfsR( int w) {pre[w] = cnt0 ++ ;stack[sp ++ ] = w;path[pp ++ ] = w; int v;std::list < int > ::iteratorli; for (li = g.a[w].begin();li != g.a[w].end(); ++ li) {v =* li; if (pre[v] ==- 1 )_SCdfsR(v); else if (sc[v] ==- 1 ) { 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;} 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 (sc[i] ==- 1 )_SCdfsR(i);} } bool isStrongReach( int s, int t) { return sc[s] == sc[t];} } namespace PrimNS { /* 解决：最小生成树MST*算法：Prim——O(V^2)*输入：加权连通图(矩阵)：g*输出：父节点st[]，与其父之边的权重wt[] */ GraphMatrix < double > g; int st[maxV]; // MST节点之父——用以保存MST double wt[maxV + 1 ]; // 与其父的边的权重 int fr[maxV]; // 非树顶点的最近树顶点 void mst() { int v,w,min; for (v = 0 ;v < g.v; ++ v) {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 < g.v; ++ w) { if (st[w] ==- 1 ) { if (g.a[v][w] < wt[w])wt[w] = g.a[v][w],fr[w] = v; if (wt[w] < wt[min])min = w;} } } } } namespace DijkstraNS { /* 解决：非负权图单源最短路径树SPT*算法：Dijkstra——O(V^2)*输入：加权连通图(矩阵)：g*输本文地址：http://www.45fan.com/a/question/70260.html