图论的一些算法——c语言、c++.doc

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.04M 资料格式：doc 举报版权申诉

wangmin_win-1369211-4744300845377637709.doc.pdf-第1页.png

第1页 / 共6页

wangmin_win-1369211-4744300845377637709.doc.pdf-第2页.png

第2页 / 共6页

wangmin_win-1369211-4744300845377637709.doc.pdf-第3页.png

第3页 / 共6页

wangmin_win-1369211-4744300845377637709.doc.pdf-第4页.png

第4页 / 共6页

wangmin_win-1369211-4744300845377637709.doc.pdf-第5页.png

第5页 / 共6页

wangmin_win-1369211-4744300845377637709.doc.pdf-第6页.png

第6页 / 共6页

文本预览

下面给大家介绍一些经典的图论算法，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() { [Page] 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]; } [Page] } 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 > ::iterator li; 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; } } [Page] 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]; // 非树顶点的最近树顶点 [Page]

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 *输出：父节点 st[]，与其父之边的权重 wt[] */ [Page] GraphMatrix < double > g; int st[maxV]; double wt[maxV + 1 ]; int fr[maxV]; // 非树顶点的最近树顶点 void spt( int s) { int v, w, min; for (v = 0 ; v < g.v; ++ v) { st[v] =- 1 ; fr[v] = v; wt[v] = Inf; } st[s] = s; wt[g.v] = Inf; wt[s] = 0 ; for (min = s; 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] != Inf && wt[v] + g.a[v][w] < wt[w]) wt[w] = wt[v] + g.a[v][w], fr[w] = v; if (wt[w] < wt[min]) min = w;

} [Page] } } } } /**/ /**/ namespace FloydNS { // /**/ /* 解决：所有点对最短路径 *算法：Floyd——O(V^3) *输入：加权连通图(矩阵)：g *输出：最短距离长度矩阵 d[][]，路径矩阵 p[][] */ GraphMatrix < double > g; double d[maxV][maxV]; // 最短路径长度 int p[maxV][maxV]; // 最短路径下一顶点 void floyd() { int i,s,t; for (s = 0 ; s < g.v; ++ s) { for (t = 0 ; t < g.v; ++ t) if ( (d[s][t] = g.a[s][t]) < Inf) p[s][t] = t; d[s][s] = 0 ; } for (i = 0 ; i < g.v; ++ i) for (s = 0 ; s < g.v; ++ s) if (s != i && d[s][i] < Inf) for (t = 0 ; t < g.v; ++ t) if (d[s][t] > d[s][i] + d[i][t]) { [Page] d[s][t] = d[s][i] + d[i][t]; p[s][t] = p[s][i]; } } } namespace TenshiNS { // ， /**/ /* 解决：二分图最大匹配 *算法：匈牙利匹配(by Tenshi)——O(xv * yv) *输入：邻接矩阵 g *输出：匹配数 cnt,x 匹配项 xm[]，y 匹配项 ym[] *备注：from Bug 06-07-07 */ int xv,yv; // 顶点数 int g[maxV][maxV]; // g[i][j]=1 表示 xi 与 yj 相邻 int sy[maxV]; // 辅助：当轮被搜过的 y 点都是 1 int cnt,xm[maxV],ym[maxV]; // 输出

void init() { cnt = 0 ; memset(g, 0 , sizeof (g)); memset(xm, - 1 , sizeof (xm)); memset(ym, - 1 , sizeof (ym)); } bool _path( int u) // 返回是否找到增广路 { for ( int v = 0 ;v < yv;v ++ ) if (g[u][v] && ! sy[v]) { sy[v] = 1 ; if (ym[v] ==- 1 || _path(ym[v])) { xm[u] = v; ym[v] = u; return 1 ;} [Page] } return 0 ; } void tenshi() { int i; for (i = 0 ;i < xv;i ++ ) if (xm[i] ==- 1 ) { memset(sy, 0 , sizeof (sy)); cnt += _path(i); } } }

分享到：

赞收藏

资料库

图论的一些算法——c语言、c++.doc

相关推荐

开发技术

热门标签

最新资料