图论基础教学资料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的度或次数 图的矩阵表示 对无向图 其邻接矩阵 其中 对有向赋权图 其邻接矩阵 图的邻接表表示 如图g2的邻接表为 邻接表实现 链表 没有必要 vector 可行 动态花销较大 数组模拟 灵活 效率高 邻接表 vector vector e n 初始化 for inti 0 ib 权值为ce a push back make pair b c 优点 方便 数组模拟 typedefstruct intv next val edge edgee maxm intp maxn eid voidinit memset p 1 sizeof p eid 0 voidinsert intfrom intto intval e eid v to e eid val val e eid next p from p from 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 map i k map k j map i j map i j map i k map k j map i j min map i k map k j map i j 熟悉的式子 floyd是一种动态规划算法 c i j k 表示从i到j的最短路径的长度 其中k表示该路径中的最大顶点中间顶点不超过k的i到j的最短路径有两种可能 该路径含或不含中间顶点k 若不含 则该路径长度应为c i j k 1 否则长度为c i k k 1 c k j k 1 c i j k 可取两者中的最小值 状态转移 c i j k min c i j k 1 c i k k 1 c k j k 1 zoj1082 要在n个人中传播谣言 每个人传播谣言给他可以联系的人都有个时间 求从哪个人开始传播谣言并使谣言传遍所有人的时间最短 单源最短路 单源最短路 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为最小生成树 从小到大选取排序 判断形成回路并查集 hdu1233 某省调查乡村交通状况 得到的统计表中列出了任意两村庄间的距离 省政府 畅通工程 的目标是使全省任何两个村庄间都可以实现公路交通 但不一定有直接的公路相连 只要能间接通过公路可达即可 并要求铺设的公路总长度为最小 请计算最小的公路总长度 prim 假设g v e 是一个具有n个顶点的连通网 t u te 是g的最小生成树 u te初值均为空集 首先从v中任取一个顶点 假定取v1 将它并入u中 此时u v1 然后只要u是v的真子集 u v 就从那些一个端点已在t中 另一个端点仍在t外的所有边中 找一条最短边 设为 vi vj 其中vi u vj v u