[计算机]一些经典的图论算法C++描述

[计算机]一些经典的图论算法C++描述 一些经典的图论算法，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 < 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; } } 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 *输出:父节点st[]，与其父之边的权重wt[] */ 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; } } } } } /**/ /**/ 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]) { 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 ;} } return 0 ; } void tenshi() { int i; for (i = 0 ;i < xv;i ++ ) if (xm[i] ==- 1 ) { memset(sy, 0 , sizeof (sy)); cnt += _path(i); } } } 图论算法的程序实现 求最小生成树 问题: 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网, 该问题等价于: 构造网的一棵最小生成树，即:在 e 条带权的边中选取 n-1 条边(不构成回路)，使“权值之和”为最小。 1.1克鲁斯卡尔(Kruskal)算法 考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。 具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。 1.1.1算法描述: 构造非连通图 ST=( V,{ } ); k = i = 0; // k 计选中的边数 while (k #define VERTEX_NUM 6 #define EDGE_NUM 10 #define MAX 100 //这个值要比最大的权值(weight)大 typedef struct { int data; //顶点信息 int jihe; }VEX;typedef struct { int vexh, vext; //边依附的两顶点 int weight; //边的权值 int flag; //标志域 }EDGE; void main() { int i,min,k,j; VEX t[VERTEX_NUM]; EDGE e[EDGE_NUM]; //初始化 for(i=0;i using namespace std; struct node { int weight; int point; node() { weight = 0; point = 0; } node(int out_weight, int out_point) { weight = out_weight; point = out_point; } }; int main() { int i; int m; //边数 int n; //点数 int u; //顶点 int v; //最小值点点 int dist[100]; int path[100]; node x; node graph[100][100]; int count[100]; //记录neighbour个数 bool flag[100]; //记录进最小路径的点数 bool isrefresh; //判断是否更新 int total; //记录一共有多少点进入集合 //initial memset(count,0,sizeof(count)); memset(flag,true,sizeof(flag)); memset(dist,1000000,sizeof(dist)); memset(path,-1,sizeof(path)); //input & build graph[][] scanf("%d",&n,&m); for(i = 0; i < m; i++) { int temp_weight; int temp_point1; int temp_point2; cin>>temp_point1>>temp_point2>>temp_weight; count[temp_point1]++; count[temp_point2]++; graph[temp_point1][count[temp_point1]].weight = temp_weight; graph[temp_point1][count[temp_point1]].point = temp_point2; graph[temp_point2][count[temp_point2]].weight = temp_weight; graph[temp_point2][count[temp_point2]].point = temp_point1; } //pretreatment cin>>u; flag[u] = false; dist[u] = 0; total = 1; for (i = 1; i <= count[u]; i++) { dist[graph[u][i].point] = graph[u][i].weight; path[graph[u][i].point] = u; } isrefresh = true; //dijkstra while( total < n && isrefresh) { isrefresh = false; //寻找当前最小边 int min=1000000; for(i = 1; i <= n; i++) { if ( flag[i] && dist[i] dist[v]+ext_weight)) { dist[ext_point] = dist[v]+ext_weight; path[ext_point] = v; isrefresh = true; } } } for (i = 1; i<= n; i++) cout<map[mj,v[mj,j]]) then lowcost[v[mj,j]]:=map[mj,v[mj,j]]; end; end; Kruskal——以边为基础读入: procedure kruskal; var set1,set2,vetex_pointer,last_set_num:longint; function find(x:longint):longint; begin if father[x]=x then find:=father[x] else begin father[x]:=find(father[x]);find:=father[x];end; end; begin qsort(1,e);——对vetex以w为关键字从小到大排序 for i:=1 to n do father[i]:=i; vetex_pointer:=1;last_set_num:=n; while (last_set_num>1)and(vetex_pointer<=e) do begin set1:=find(vetex[vetex_pointer].u); set2:=find(vetex[vetex_pointer].v); if set1<>set2 then begin inc(totallen,vetex[vetex_pointer].w); dec(last_set_num); father[set1]:=set2; end; inc(vetex_pointer); end; writeln(totallen); end; 7( 最短路径 Dijktra: procedure Dijkstra(s:longint); var i,j,min,mi:longint; begin fillchar(shortest,sizeof(shortest),$5F); shortest[s]:=0; for i:=1 to n do begin min:=max; for j:=1 to n do if (not flag[j])and(shortest[j]min+map[mi,vetex[mi,j]]) then shortest[vetex[mi,j]]:=min+map[mi,vetex[mi,j]]; end; end; Floyd: procedure Floyd; var i,j,k:longint; begin fillchar(len,sizeof(len),$5F); for i:=1 to n do begin len[i,i]:=0; for j:=1 to vetex[i,0] do len[i,vetex[i,j]]:=map[i,vetex[i,j]]; end; for k:=1 to n do for i:=1 to n do for j:=1 to n do if len[i,k]+len[k,j]shortest[vetex[j].u]+vetex[j].w then begin shortest[vetex[j].v]:=shortest[vetex[j].u]+vetex[j].w; bool:=true; end; end; for j:=1 to e do if shortest[vetex[j].v]>shortest[vetex[j].u]+vetex[j].w then exit(flase); exit(true); end; SPFA: procedure SPFA(s:longint); var u,i:longint; x0:array[1..maxn]of longint; begin fillchar(shortest,sizeof(shortest),$5f); fillchar(flag,sizeof(flag),0); open:=0;closed:=1;x0[1]:=s;shortest[s]:=0;flag[s]:=true; repeat inc(open);u:=x0[open]; for i:=1 to vetex[u,0] do if shortest[vetex[u,i]]=closed; end; 2008哈尔滨现场赛的一个很好的图论题目～用到了Havel 算法～2009-03-15 22:06/* 网上有人说用一个图论的算法叫 Havel 算法，感觉挺有用的，就分享一下。 对于一个给定的度序列，看能不能形成一个简单无向图。 Havel算法的思想简单的说如下: (1)对序列从大到小进行排序。 (2)设最大的度数为 t ，把最大的度数置0，然后把最大度数后(不包括自己)的t 个度数分别 减1(意思就是把度数最大的点与后几个点进行连接) (3)如果序列中出现了负数，证明无法构成。如果序列全部变为0，证明能构成，跳出循环。 前两点不出现，就跳回第一步～ 举例说明: 4 4 3 3 2 2 第二步后0 3 2 2 1 2 排完续后3 2 2 2 1 0 第二步后0 1 1 1 1 0 排完续后1 1 1 1 0 0 第二步后0 0 1 1 0 0 排完续后1 1 0 0 0 0 第二步后0 0 0 0 0 0 全为0，能构成图，跳出～ 2 1 1 1 第二步后0 0 0 1 排完续后1 0 0 0 第二步后0 -1 0 0 出现负数，直接退出～ */ #include #include using namespace std; const int MAX=1005; bool cmp(int a,int b) { return a>b; } int graph[MAX]; bool IsWuXiangTu(int n) { int i,j,k,t,sum; for(i=1;i<=n;i++) { sort(graph+1,graph+n+1,cmp); t=graph[1],graph[1]=0; for(j=2;j<=t+1&&j<=n;j++)//把t个度数分别减1 graph[j]--; sum=0; for(k=1;k<=n;k++) if(graph[k]<0) return false; else if(graph[k]==0) ++sum; if(sum==n) return true; } return false; } int main() { int T; int i,n; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&graph[i]); if(IsWuXiangTu(n)) printf("yes\n"); else printf("no\n"); } return 0; } /* 2 6 4 4 3 3 2 2 4 2 1 1 1 yes no */ 图论-最短路径之ford算法2008年09月12日 星期五 09:30 Ford算法: 迭代算法(ford算法) Dijkstra 算法只能适合权为正值的情况,但当权为负值时，是Dijkstra 算法爱莫能助，这时只要图中不存在负权回路可用迭代算法。 迭代算法的思想:不停地调整图中的顶点值(源点到该点的最短路径值)，直到没有点的值调整了为止。 program ford; const maxn=100000000; var n,m,i,j,y,min:longint; cost:array[1..100,1..100]of longint; dist:array[1..100] of longint; path,p:array[1..100] of longint; first,tail,u:longint; s:array[1..100]of longint; flag:boolean; begin read(n); for i:=1 to n do for j:=1 to n do begin read(cost[i,j]); if (i<>j)and(cost[i,j]=0) then cost[i,j]:=maxn; end; read(first); for i:=1 to n do dist[i]:=maxn; dist[first]:=0; repeat flag:=true; for i:=1 to n do if dist[i]first)and(dist[i]<>maxn) then begin writeln(i,'=',dist[i]:4:2); y:=i;m:=0; while (y<>first) do begin inc(m);p[m]:=y;y:=path[y] end; write('path:',first); for j:=m downto 1 do write('->',p[j]); writeln; end else writeln(i,' No answer'); end. Ford优化: Spfa: 基本思路:先建立一个邻接链表或邻接矩阵(用邻接链表使用的内存更少)。再建立一个队列数组，队头从起始点开始工作，每次找可以更新它于源点的距离的点，更新它把它加入队尾，怎样做完所有于它相连的点以后对头退出队列，等待其他点更新它于源点的距离。就怎样不断的做直到没有可以更新的点，spfa操作完成。 我们用数组d记录每个结点的最短路径估计值,而且用邻接表来存储图G.我们采取的

方法

快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载

是动态逼近法:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短 路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾.这样不断从队列中取出结点来进行松弛操作,直至队列空为止. ? 定理 在平均情况下,SPFA算法的期望时间复杂度为Θ(E). 此代码的题目Usaco Sweet Butter 3.2.6 program ford_spfa; var n,p,c,i,ans,maxn:longint; cow:array[1..800]of longint; //那几个点 cost:array[1..800,0..800]of longint; //邻接矩阵 l:array[1..800]of longint; //统计i点有多少条边与它相连 lw:array[1..800,1..100]of longint; //记录那几个点相连 procedure init; var i,j,x,y,k:longint; begin read(n,p,c); for i:=1 to p do for j:=1 to p do cost[i,j]:=maxn; for i:=1 to n do read(cow[i]); for i:=1 to p do l[i]:=0; for i:=1 to c do begin read(x,y,k); cost[x,y]:=k; cost[y,x]:=k; inc(l[x]);lw[x,l[x]]:=y; inc(l[y]);lw[y,l[y]]:=x; end; end; procedure spfa(frist:longint); var i,j,head,tail,x,y,k:longint; list:array[1..800]of longint; //队列集合 dist:array[1..800]of longint; hash:array[1..800]of boolean; //用于判断点是否用过 begin for i:=1 to p do begin dist[i]:=maxn;hash[i]:=false;end; dist[frist]:=0;hash[frist]:=true; list[1]:=frist; head:=1;tail:=1; while head<=tail do begin x:=list[(head-1)mod p+1]; for i:=1 to l[x] do begin y:=lw[x,i]; if dist[x]+cost[x,y]maxn then k:=k+dist[cow[i]]; if ans>k then ans:=k; end; begin maxn:=1000000000; init; ans:=maxn; for i:=1 to p do spfa(i); writeln(ans); end. 用Kosaraju算法求强连通分量2009-05-06 01:41最近看了不少图论方面的

内容

财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容

，复习了一下旧的知识，又学了一些新的知识 ---------------------------------------------------------------------------------------------------------------------- -- 强连通分量 Strongly connected components: 在一个有向图中，满足点集中的任意两点互相可达的最大点集。 Kosaraju算法实现步骤: 1.深搜后序遍历有向图，记录每个点的访问顺序(order); 2.按照1中的顺序(order)的逆顺序，再次深搜遍历原先有向图的转置图(原先的边反向); 3.步骤2中，能在一次dfs中遍历到的点，在同一个强连通分量中; 实现代码: vector adj[ MAXN ] ; //正向邻接表 vector radj[ MAXN ] ; //反向邻接表 vector ord; //后序访问顺序 void dfs1 ( int v ) { int i,u; for ( i=0 , vis[v]=true; i=0 ; i-- ) if ( !vis[ord[i]] ) { dfs2(ord[i]); cnt++; } } 求强连通分量是图论中的一个基本技巧，可以将一个有向图中的若干个强连通分量看做是一个点(缩点)，从而方便求解问题。 百度空间 | 百度首页 | 登录 故纸堆这样吧 主页博客相册|个人

档案

肢体残疾康复训练教师个人成长档案教师师德档案表人事档案装订标准员工三级安全教育档案

|好友 查看文章 一个图论问题的作用于邻接矩阵实现的O(V)算法2008-06-18 16:32 对于用邻接矩阵存储的图，除非有什么特殊说明，我们几乎总得将这个矩阵看完方能得到对很多问题来说必要的信息，于是大多数图算法当采用邻接矩阵表示时都要用Ω(V^2)的时间。不过，有一些问题恰恰可以不必遍历整个矩阵即可得到结果。 今天在翻CLRS时看到上面的一道习题，大意是:给出一个作用于邻接矩阵表示的有向图的找到其一个通用汇点(即入度为|V|-1,出度为0的顶点)，要求这个算法以O(V)运行。 于是略想一下，得出这样一个算法。大家看程序吧，因为用自然语言描述多少有些费劲。 { 输入一个顶点数为n的有向邻接矩阵 输出其是否存在一个通用的(若存在则返回之,不存在返回0)及其驱动例程 } program project1; const maxn=100; type graph=array[1..maxn,1..maxn] of boolean; function universal_sink(var g:graph;n:integer):integer; var i,j,k:integer; begin i:=1; j:=1; while true do begin inc(j); while (j<=n) and not(g[i,j]) do j:=j+1; if j>n then begin for k:=1 to n do if ((i<>k) and not(g[k,i])) or g[i,k] then exit(0); exit(i); end else i:=j; end; end; var g:graph; n,i,j,r:integer; c:char; Begin readln(n); for i:=1 to n do begin for j:=1 to n do begin read(c); g[i,j]:=c='1'; end; readln; end; r:=universal_sink(g,n); if r>0 then writeln('There is a universal sink in this graph,it is vertex ',r,' .') else writeln('There isn',char(39),'t a universal sink in this graph.'); End. POJ 1496 C++ (图论) //匈牙利算法实现二分图的最大匹配，较最大流实现来的简单些 //特点不需要建模，原理还是朴素最大流原理，寻找增广路径用DFS,如找到一条增广路径，沿路边取反 #include using namespace std; int n,m,res; int l[300],r[300],map[300][300],used[300]; bool path(int u) {int v; for(v=0;v6->2->5->1->4。我们借由它来描述一下二分图中的增广路径的性质: (1)有奇数条边。 (2)起点在二分图的左半边，终点在右半边。 (3)路径上的点一定是一个在左半边，一个在右半边，交替出现。(其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦。) (4)整条路径上没有重复的点。 (5)起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。(如图1、图2所示，,1，5,和,2，6,在图1中是两对已经配好对的点;而起点3和终点4目前还没有 与其它点配对。) (6)路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。(如图1、图2所示，原有的匹配是,1，5,和,2，6,，这两条配匹的边在图2给出的增广路径中分边是第2和第4条边。而增广路径的第1、3、5条边都没有出现在图1给出的匹配中。) (7)最后，也是最重要的一条，把增广路径上的所有第奇数条边加入到原匹配中去，并把增广路径中的所有第偶数条边从原匹配中删除(这个操作称为增广路径的取反)，则新的匹配数就比原匹配数增加了1个。(如图2所示，新的匹配就是所有蓝色的边，而所有红色的边则从原匹配中删除。则新的匹配数为3。) 不难想通，在最初始时，还没有任何匹配时，图1中的两条灰色的边本身也是增广路径。因此在这张二分图中寻找最大配匹的过程可能如下: (1)找到增广路径1->5，把它取反，则匹配数增加到1。 (2)找到增广路径2->6，把它取反，则匹配数增加到2。 (3)找到增广路径3->6->2->5->1->4，把它取反，则匹配数增加到3。 (4)再也找不到增广路径，结束。 当然，这只是一种可能的流程。也可能有别的找增广路径的顺序，或者找到不同的增广路径，最终的匹配

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

也可能不一样。但是最大匹配数一定都是相同的。 对于增广路径还可以用一个递归的方法来描述。这个描述不一定最准确，但是它揭示了寻找增广路径的一般方法: “从点A出发的增广路径”一定首先连向一个在原匹配中没有与点A配对的点B。如果点B在原匹配中没有与任何点配对，则它就是这条增广路径的终点;反之，如果点B已与点C配对，那么这条增广路径就是从A到B，再从B到C，再加上“从点C出发的增广路径”。并且，这条从C出发的增广路径中不能与前半部分的增广路径有重复的点。 比如图2中，我们要寻找一条从3出发的增广路径，要做以下3步: (1)首先从3出发，它能连到的点只有6，而6在图1中已经与2配对，所以目前的增广路径就是3->6->2再加上从2出发的增广路径。 (2)从2出发，它能连到的不与前半部分路径重复的点只有5，而且5确实在原匹配中没有与2配对。所以从2连到5。但5在图1中已经与1配对，所以目前的增广路径为3->6->2->5->1再加上从1出发的增广路径。 (3)从1出发，能连到的不与自已配对并且不与前半部分路径重复的点只有4。因为4在图1中没有与任何点配对，所以它就是终点。所以最终的增广路径是3->6->2->5->1->4。 但是严格地说，以上过程中从2出发的增广路径(2->5->1->4)和从1出发的增广路径(1->4)并不是真正的增广路径。因为它们不符合前面讲过的增广路径的第5条性质，它们的起点都是已经配过对的点。我们在这里称它们为“增广路径”只是为了方便说明整个搜寻的过程。而这两条路径本身只能算是两个不为外界所知的子过程的返回结果。 显然，从上面的例子可以看出，搜寻增广路径的方法就是DFS，可以写成一个递归函数。当然，用BFS也完全可以实现。 至此，理论基础部份讲完了。但是要完成匈牙利算法，还需要一个重要的定理: 如果从一个点A出发，没有找到增广路径，那么无论再从别的点出发找到多少增广路径来改变现在的匹配，从A出发都永远找不到增广路径。 要用文字来证明这个定理很繁，话很难说，要么我还得多画一张图，我在此就省了。其实你自己画几个图，试图举两个反例，这个定理不难想通的。(给个提示。如果你试图举个反例来说明在找到了别的增广路径并改变了现有的匹配后，从A出发就能找到增广路径。那么，在这种情况下，肯定在找到别的增广路径之前，就能从A出发找到增广路径。这就与假设矛盾了。) 有了这个定理，匈牙利算法就成形了。如下: 初始时最大匹配为空 for 二分图左半边的每个点i do 从点i出发寻找增广路径。如果找到，则把它取反(即增加了总了匹配数)。 如果二分图的左半边一共有n个点，那么最多找n条增广路径。如果图中共有m条边，那么每找一条增广路径(DFS或BFS)时最多把所有边遍历一遍，所花时间也就是m。所以总的时间大概就是O(n * m)。 图论->欧拉迹 c++代码实现(转载) 一醉一陶然 收录于2009-05-30 阅读数: 公众公开 原文来源 tags: 图论 欧拉迹 C 题目类型:图论->欧拉迹 算法:看c++图算法 (Robert Sedgewick著)上的算法，大体上就是深搜(上边用栈讲解的) 时间复杂度:O(E) 题意很赤裸裸，开始要判断没有欧拉迹情况(顶点出入度)，如果有欧拉回路要确定开始顶点， 因为需要考虑字典序，这个就需要对边按字符串排序，之后深搜按字符串由小到大即可保证; 从看题，看

书

关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf

，到过了这个题用了2.5小时...我的形式语言作业啊，还没有写...抓紧了 #include #include #include #include #include using namespace std; const int Max = 1024; struct T{ char str[32]; int v; bool operator<(const T&a)const { if(strcmp(str, a.str) < 0)return true; return false; } }; vector lis[Max], mis[Max]; int in[32], out[32], mark[32], matrix[32][32], x[Max], xnum; void dfs(int op, int &sum); void search(int op); void solve(int op); int main() { int t, n; scanf("%d", &t); while(t--){ scanf("%d", &n); for(int i = 0; i < 26; i++) lis[i].clear(); memset(in , 0, sizeof in); memset(out, 0, sizeof out); memset(mark, 0, sizeof mark); memset(matrix, 0, sizeof matrix); int u; char str[32]; for(int i = 0; i < n; i++){ T ans; scanf("%s", str); u = str[0] - 'a'; ans.v = str[strlen(str) - 1] - 'a'; strcpy(ans.str,str); lis[u].push_back(ans); in[ans.v]++, out[u]++; mark[u] = mark[ans.v] = 1; matrix[u][ans.v] = matrix[ans.v][u] = 1; } int sum = 0, tn = 0; for(int i = 0; i < 26; i++)if(mark[i]){tn++;} memset(mark, 0, sizeof mark); dfs(u, sum); if(sum != tn){ printf("***\n"); continue; } else { int v, vflag = -1, vn = 0, vm = 0, vx = 0; for(int i = 0; i < 26; i++){ if(in[i] - out[i] == -1)vflag = i, vn++; if(in[i] - out[i] == 1)v = i, vm++; if(abs(in[i] - out[i]) > 1)vx = -1; } if(vx == -1 || !((vn == 0 && vm == 0) || (vn == vm == 1))){ printf("***\n"); continue; } for(int i = 0; i < 26; i++) if(lis[i].size()) sort(lis[i].begin(), lis[i].end()), mis[i] = lis[i]; if(vflag > -1) solve(vflag); else { int i = 0; for(i = 0; i < 26; i++) if(out[i])break; solve(i); } } } } void solve(int op) { xnum = 0; search(op); for(int i = xnum-1; i > 0; i--){ for(int j = 0; j < (int)mis[x[i]].size(); j++) if(mis[x[i]][j].v == x[i-1]){ mis[x[i]][j].v = -1; cout<= 0) { int tmp = lis[op][i].v; lis[op][i].v = -1; search(tmp); } x[xnum++] = op; } void dfs(int op, int &sum) { mark[op] = 1; sum++; for(int i = 0; i < 26; i++) if(mark[i] == 0 && matrix[op][i])dfs(i, sum); }