ACM培训——图论(一)课件.ppt

《ACM培训——图论(一)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论（一）四川大学ACM/ICPC集训队李冠一2013.7百度百科：图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。何为图论个人理解：图论是ACM/ICPC中经常出现的一类题目。多见于中档题，当然也有神题神模型。图论相对好入门，图的BFS/DFS遍历几乎一个没有算法基础的人也可以掌握。但是，当研究深入之后，实际上图论包含着许多艰深而复杂的理论。当然，对于大多数普

2、通的ACMer来说，我们首先要做的就是熟悉基本算法、掌握常见模型、提高建模思维。Part1图的遍历一、图的BFS遍历算法步骤：1、用dis[]数组表示各点距离起点S的距离。dis[i]=-1表示i点还未被访问。用map[i][j]表示i点和j点之间是否有边。2、将dis[s]初始化为0，将其它点的dis初始化为-1。将S点入队3、while（队列非空）{从队首出队一个元素u{对于所有跟u有边相连的点v:if(dis[v]==-1){dis[v]=dis[u]+1;v入队}}}每个节点只会入队一次，也只会出队一次。

3、时间复杂度O(V+E)。基本性质：如果遍历的是0-1边权图呢？队列中的节点距起点的最短距离单调递增。且队首与队尾的最短距离差值不超过1如果遍历的是1-2边权图呢？1-2边权图的BFS：把每条长度为2的边中间加一个点，拆成两条边例题1.1HDOJ1180:诡异的楼梯题意：在一个地图上，有一些位置是空地，有些位置有障碍。还有一些位置有梯子，不过梯子的方向有的是横向，有的是竖向，且方向每分钟变化一次。求从起点到终点的最短时间。解法：每次最多有五种状态可以选择：上、下、左、右、停留原地等待。设计状态时除了要保存距离以外，

4、还要保存当前的时间是奇数还是偶数这样才能在BFS时进行状态的转移二、图的DFS遍历算法步骤（以0-1边权图为例）：1、从某个节点开始，每次任选一个与它相邻的未访问节点访问下去2、直到当前节点的所有相邻节点都已经被访问过。3、回溯到第一个未被访问过的节点三、拓扑排序概念引入：一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为

5、拓扑排序。算法步骤1.从有向图中选取一个没有前驱的顶点，并输出；2.从有向图中删去此顶点以及所有以它为尾的边；3.重复上述两步，直至图空。*如果图不空，但找不到无前驱的顶点，说明图中有环。拓扑序列：v6,v1,v4,v3,v2,v5注意：拓扑序列可能不唯一拓扑排序的应用判断一个有向图中是否有环。无环的图所有点都能进行拓扑排序。求DAG图最长路类似于课程安排问题的题目Part2生成树与最短路最小生成树定义bchifaedg48812414791067211生成树：对于一个无向图，生成树是它的一个无回路的联通子图最小

6、生成树：各边权值和最小的生成树有向图的最小有向生成树？——最小树形图最小生成树prim算法(复杂度O(n^2))kruskal算法(复杂度O(m*lg(m))Prim算法贪心准则加入后仍形成树，且耗费最小始终保持树的结构——Kruskal算法是森林算法过程从单一顶点的树T开始不断加入耗费最小的边(u,v)，使T∪{(u,v)}仍为树——u、v中有一个已经在T中，另一个不在T中Prim算法过程bchifaedg488414791067211aidcbhgfe12Krustal算法kruskal算法思想：贪心选取最短

7、的边来组成一棵最小的生成树。具体做法：先将所有的边做排序，然后利用并查集作判断来优先选择较小的边，直到建成一棵生成树。intkruskal(){intans=0;sort(edge.begin(),edge.end());for(inti=0;i

8、n(intx,inty){intpx=findp(x);intpy=findp(y);if(px==py){returnfalse;}p[px]=py;returntrue;}Prim和Kruskal的区别Prim和Kruskal的贪心策略是一样的，都是选取耗费最小的边：对于Prim，其选取的边(u,v)必有一个顶点已经被覆盖，另一个顶点未被覆盖。而对于Kruskal,其