graph_algorithm

《graph_algorithm 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、.图论算法简介.胡海星计算机科学与技术系南京大学2013年5月5日胡海星(南大计算机)图论2013年5月5日1/100提纲1.数据结构2.深度优先搜索：DFS3.广度优先搜索：BFS4.图的连通性5.最短路径差分约束系统6.最小生成树7.回路问题8.匹配9.网络流10.特殊类型的图11.参考文献胡海星(南大计算机)图论2013年5月5日2/100图的基本数据结构在竞赛中，大多数情况下应该使用邻接矩阵作为图的数据结构，因为：当题目的数据给出最大规模情况时，邻接矩阵耗费的时空复杂度和邻接表一样；邻接矩阵编程比较方便。#de

2、fineMAX_NODE100/*顶点数目*/#defineINF500000/*用一个很大的数表示无穷大*/typedefintGraph[MAX_NODE][MAX_NODE];typedefintPath[MAX_NODE];typedefstructEdge{/*定义弧*/inthead,tail;};胡海星(南大计算机)图论2013年5月5日3/100提纲1.数据结构2.深度优先搜索：DFS3.广度优先搜索：BFS4.图的连通性5.最短路径差分约束系统6.最小生成树7.回路问题8.匹配9.网络流10.特殊类型

3、的图11.参考文献胡海星(南大计算机)图论2013年5月5日4/100深度优先搜索：DFSDFS是最基本，但是却有广泛的应用的图论算法；它常被用来收集图的拓扑结构信息，例如用DFS求图的连通分支；为了收集图的拓扑信息，DFS通常需要根据访问的先后顺序对图的节点染色，并记录访问每个节点的时间戳，以及每个节点在深度优先树中的父节点；DFS算法运行时间为(V+E)。胡海星(南大计算机)图论2013年5月5日5/100DFS算法全局变量time用于记录时间戳；color[u]记录节点u的颜色；初始的时候所有节点都是白色；当节

4、点u第一次被访问时，记录下当前时间戳d[u]，并将节点u染成灰色；当结束检查从节点u发出的所有的弧后，记录当前时间戳f[u]，并将节点u染成黑色；[u]表示节点u在深度优先树中的父节点，即记录第一次是从哪个节点访问到u的。胡海星(南大计算机)图论2013年5月5日6/100DFS算法DFS(G)1foreachu2V[G]2docolor[u]WHITE3[u]nil4time05foreachu2V[G]6doifcolor[u]=WHITE7thenDFS-Visit(u)胡海星(南大计算机)图论2013年5月

5、5日7/100DFS算法DFS-Visit(u)1color[u]GRAY2timetime+13d[u]time4foreachv2Adj[u]5doifcolor[v]=WHITE6then[v]u7DFS-Visit(v)8color[u]BLACK9timetime+110f[u]time胡海星(南大计算机)图论2013年5月5日8/100DFS算法的重要性质.Theorem1(括号定理)..在对有向图或无向图G=(V;E)的深度优先搜索中，对于图中任意两个节点u;v，下述三个命题有且仅有一条成立：区间[d[

6、u];f[u]]和区间[d[v];f[v]]是完全分离的；区间[d[u];f[u]]完全包含于区间[d[v];f[v]]，且在深度优先搜索树中u是v的后裔；区间[d[v];f[v]]完全包含于区间[d[u];f[u]]，且在深度优先搜索树中v是u的后裔。.胡海星(南大计算机)图论2013年5月5日9/100DFS算法的重要性质.Theorem2(后裔区间的嵌入)..在有向图或无向图G=(V;E)的深度优先森林中，节点v是节点.u的后裔当且仅当d[u]

7、5日10/100DFS算法的重要性质.Theorem3(白色路径定理)..在有向图或无向图G=(V;E)的深度优先森林中，节点v是节点u的后裔当且仅当在搜索发现u的时刻d[u]，从节点u到节点v.之间存在一条仅由白色节点组成的路径。胡海星(南大计算机)图论2013年5月5日11/100DFS算法的应用：对有向图的边分类I树枝深度优先森林中的边。如果v是在访问边(u;v)时第一次被发现(此时v是白色的)，那么(u;v)就是一个树枝。在树枝边中，我们称u为v的父母，记作(v)=u；反向边在深度优先树中连接顶点u到它的祖先

8、的那些非树枝边。环也被认为是反向边。显然，如果第一次访问(u;v)时v为灰色，则(u;v)为反向边。若DFS过程中未发现反向边，则该有向图无回路；胡海星(南大计算机)图论2013年5月5日12/100DFS算法的应用：对有向图的边分类II正向边深度优先树中连接顶点u到它的后裔的非树枝边。当第一次访问(u;v)时，v为黑色且d[u]