一些经典的图论算法，C++描述。 #include < cstring > // 常量定义： const int maxV = 100 ; const double Inf = 1e100; // const int Inf=2000000000; // Graph 类定义： template < class T > struct GraphMatrix { int v; // 顶点数 int e; // 边数 T a[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 > ::iterator li; 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...
