图论基础教学资料ppt电子教案课件.ppt

图论基础 图的概念 定义 一个图g是指一个二元组(v(g),e(g) 其中: 是非空有限集，称为顶点集，其中元素称 为图g的顶点 e(g)是顶点集v(g)中的无序或有序的元素 对 组成的集合，即称为边集,其中元 素称为边 赋权图 定义 若图 的每一条边e 都赋 以一个实数w(e)，称w(e)为边e的权，g 连 同边上的权称为赋权图。 图论算法所研究的往往和权值有关 图的顶点度 定义 在无向图g中，与顶点v关联的边的数目,称 为顶点v的度或次数，记为d(v) 在有向图中，从顶点v引出的边的数目称为 顶点v的出度，记为d+(v)，从顶点v引入的边 的数目称为v的入度，记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的度或次数 图的矩阵表示 对无向图 ，其邻接矩阵 ，其中 ： 对有向赋权图 , 其邻接矩阵 图的邻接表表示图的邻接表表示 如图如图g2g2的的邻接表邻接表为：为： 2 5 3 4 1 5 4 3 5 3 3 4 1 2 2 1 2 1 2 3 4 5 g2 邻接表实现邻接表实现 链表？ 没有必要！ vector? 可行！动态花销较大！ 数组模拟？ 灵活！效率高！ 邻接表邻接表-vector-vector vector en; 初始化： for(int i=0;ib，权值为c ea.push_back(make_pair(b,c); 优点：方便 数组模拟 typedef struct int v,next,val; edge; edge emaxm; int pmaxn,eid; void init()memset(p,-1,sizeof(p);eid=0; void insert(int from,int to,int val) eeid.v=to; eeid.val=val; eeid.next=pfrom; pfrom=eid+; 最短路问题 单源点：求赋权图中从给定点到其余顶点 的最短路 多源点：求赋权图中任意两点间的最短路. 多源最短路floyd 从任意一条单边路径开始。所有两点之 间的距离是边的权，如果两点之间没有边 相连，则权为无穷大。 对于每一对顶点 u 和 v，看看是否存在一 个顶点 w 使得从 u 到 w 再到 v 比己知的路 径更短。如果是更新它。 for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if(mapik+map kjmapij) mapij=mapik+mapkj; mapi,j:=minmapi,k+mapk,j,mapi,j 熟悉的式子! floyd是一种动态规划算法! c i, j, k表示从i 到j 的最短路径的长度，其 中k 表示该路径中的最大顶点 中间顶点不超过k 的i 到j 的最短路径有两种 可能：该路径含或不含中间顶点k。若不含 ，则该路径长度应为ci, j, k-1，否则长度为 ci, k, k-1 +c k, j, k-1。ci, j, k可取两者中 的最小值。 状态转移：ci, j, k=minci, j, k-1, c i, k, k- 1+c k, j, k-1 zoj 1082 要在n个人中传播谣言，每个人传播谣言给 他可以联系的人都有个时间，求从哪个人 开始传播谣言并使谣言传遍所有人的时间 最短。 单源最短路 dijkstraspfa dijkstra+堆优 化 复杂度o(n2)o(km)o(nlgn) 处理负边不能 能 不能 适用稠密图稀疏图稠密图 单源最短路spfa 初始时将源加入队列。 每次从队列中取出一 个元素，并对所有与他相邻的点进行松弛，若 某个相邻的点松弛成功，则将其入队。 直到 队列为空时算法结束。 spfa 在形式上和宽度优先搜索非常类似，不 同的是宽度优先搜索中一个点出了队列就不可 能重新进入队列，但是spfa中一个点可能在 出队列之后再次被放入队列，也 就是一个点 改进过其它的点之后，过了一段时间可能本身 被改进，于是再次用来改进其它的点，这样反 复迭代下去。 图的生成树 在一个连通图g中，如果取它的全部顶点和 一部分边构成一个子图g，即： v(g)=v(g);e(g) e(g) 若边集e(g)中的边既将图中的所有顶点连 通又不形成回路，则称子图g是原图g的一 棵生成树。 一棵含有n个点的生成树，必含有n-1条边 。 最小生成树 对于一个连通网（连通带权图，假定每条 边上的权均为大于零的实数）来说，每棵 树的权（即树中所有边的权值总和）也可 能不同 具有权最小的生成树称为最小生成树。 kruskal 贪心思想 将图g中的边按权值从小到大依次选取，若 选取的边使生成树不形成回路，则把它并 入te中，若形成回路则将其舍弃，直到te 中包含n-1条边为止，此时t为最小生成树 。 从小到大选取 排序！ 判断形成回路 并查集！ hdu 1233 某省调查乡村交通状况，得到的统计表中列出 了任意两村庄间的距离。省政府“畅通工程”的 目标是使全省任何两个村庄间都可以实现公路 交通（但不一定有直接的公路相连，只要能间 接通过公路可达即可），并要求铺设的公路总 长度为最小。请计算最小的公路总长度。 prim. 假设g=(v,e)是一个具有n个顶点的连通网， t=(u,te)是g的最小生成树，u,te初值均为空集。 首先从v中任取一个顶点（假定取v1），将它并入 u中，此时u=v1，然后只要u是v的真子集(uv) ，就从那些一个端点已在t中，另一个端点仍在t外 的所有边中，找一条最短边，设为(vi,vj),其