图论(C++版).ppt

图论算法c 一对一和一对多的结构 在前边讲解的线性表中 每个元素之间只有一个直接前驱和一个直接后继 在树形结构中 数据元素之间是层次关系 并且每一层上的数据元素可能和下一层中多个元素相关 但只能和上一层中一个元素相关 图结构 是研究数据元素之间的多对多的关系 在这种结构中 任意两个元素之间可能存在关系 即结点之间的关系可以是任意的 图中任意元素之间都可能相关 图的应用极为广泛 已渗入到诸如语言学 逻辑学 物理 化学 电讯 计算机科学以及数学的其它分支 一 图的定义及其术语图 Graph 是由顶点的有穷非空集合和顶点之间边的集合组成 通常表示为 G V E 其中 G表示一个图 V是图G中顶点的集合 E是图G中边的集合 对于图的定义 我们需要明确几个注意的地方 线性表中我们把数据元素叫元素 树中叫结点 在图中数据元素我们则称之为顶点 Vertex 线性表可以没有数据元素 称为空表 树中可以没有结点 叫做空树 而图结构在国内大部分的教材中强调顶点集合V要有穷非空 线性表中 相邻的数据元素之间具有线性关系 树结构中 相邻两层的结点具有层次关系 而图结构中 任意两个顶点之间都可能有关系 顶点之间的逻辑关系用边来表示 边集可以是空的 图的各种定义 无向边 若顶点Vi到Vj之间的边没有方向 则称这条边为无向边 Edge 用无序偶数对 Vi Vj 来表示 无向图 图中所有顶点间的边均是无向的 上图G1是一个无向图 G1 V1 E1 其中V1 A B C D E1 A B B C C D D A A C 无序对 A B 表示A和B之间的一条边 Edge 因此 A B 和 B A 代表的是同一条边 上图G2是一个无向图 G2 V2 E2 其中V2 A B C D E2 有向边 若从顶点Vi到Vj的边有方向 则称这条边为有向边 也称为弧 Arc 用有序偶数对来表示 Vi称为弧尾 Vj称为弧头 有向图 图中所有顶点间的边均是有向的 简单图 在图结构中 若不存在顶点到其自身的边 且同一条边不重复出现 则称这样的图为简单图 以下两个则不属于简单图 稀疏图 稠密图 权有很少边或弧的图 e n n 的图称为稀疏图 反之称为稠密图 权 Weight 与图的边和弧相关的数 权可以表示从一个顶点到另一个顶点的距离或耗费 带权的图通常称为网 Network 无向完全图 在无向图中 如果任意两个顶点之间都存在边 则称该图为无向完全图 含有n个顶点的无向完全图有n n 1 2条边 有向完全图 在有向图中 如果任意两个顶点之间都存在方向互为相反的两条弧 则称该图为有向完全图 含有n个顶点的有向完全图有n n 1 条边 假设有两个图G1 V1 E1 和G2 V2 E2 如果V2 V1 E2 E1 则称G2为G1的子图 Subgraph 图的顶点与边之间的关系 对于无向图G V E 如果边 V1 V2 E 则称顶点V1和V2互为邻接点 Adjacent 即V1和V2相邻接 边 V1 V2 依附 incident 于顶点V1和V2 或者说边 V1 V2 与顶点V1和V2相关联 顶点V的度 Degree 是和V相关联的边的数目 记为TD V 如下图 顶点A与B互为邻接点 边 A B 依附于顶点A与B上 顶点A的度为3 对于有向图G V E 如果有 E 则称顶点V1邻接到顶点V2 顶点V2邻接自顶点V1 以顶点V为头的弧的数目称为V的入度 InDegree 记为ID V 以V为尾的弧的数目称为V的出度 OutDegree 记为OD V 因此顶点V的度为TD V ID V OD V 下图顶点A的入度是2 出度是1 所以顶点A的度是3 路径 Path 路径长度 回路 Cycle 对无向图G V E 若从顶点vi经过若干条边能到达vj 称顶点vi和vj是连通的 又称顶点vi到vj有路径 对有向图G V E 从顶点vi到vj有有向路径 指的是从顶点vi经过若干条有向边 弧 能到达vj 在一条路径中 若没有重复相同的顶点 该路径称为简单路径 第一个顶点和最后一个顶点相同的路径称为回路 环 在一个回路中 若除第一个与最后一个顶点外 其余顶点不重复出现的回路称为简单回路 简单环 如果G是有向图 则路径也是有向的 下图用红线列举顶点B到顶点D的两种路径 而顶点A到顶点B就不存在路径 路径的长度是路径上的边或弧的数目 第一个顶点到最后一个顶点相同的路径称为回路或环 Cycle 右图用红线列举了从顶点B到顶点D的四种不同路径 连通图在无向图G中 如果从顶点V1到顶点V2有路径 则称V1和V2是连通的 如果对于图中任意两个顶点Vi和Vj都是连通的 则称G是连通图 ConnectedGraph 下图左侧不是连通图 右侧是连通图 无向图中的极大连通子图称为连通分量 注意以下概念 首先要是子图 并且子图是要连通的 连通子图含有极大顶点数 极大 的含义 指的是对子图再增加图G中的其它顶点 子图就不再连通 具有极大顶点数的连通子图包含依附于这些顶点的所有边 在有向图G中 如果对于每一对Vi到Vj都存在路径 则称G是强连通图 有向图中的极大强连通子图称为有向图的强连通分量 下图左侧并不是强连通图 右侧是 并且右侧是左侧的极大强连通子图 也是左侧的强连通分量 二 图的存储结构图的存储结构比较复杂 其复杂性主要表现在 任意顶点之间可能存在联系 无法以数据元素在存储区中的物理位置来表示元素之间的关系 图中顶点的度不一样 有的可能相差很大 若按度数最大的顶点设计结构 则会浪费很多存储单元 反之按每个顶点自己的度设计不同的结构 又会影响操作 图的常用的存储结构有 邻接矩阵 邻接链表 十字链表 邻接多重表和边表 1 二维数组邻接矩阵存储基本思想 对于有n个顶点的图 用一维数组vexs n 存储顶点信息 用二维数组A n n 存储顶点之间关系的信息 该二维数组称为邻接矩阵 在邻接矩阵中 以顶点在vexs数组中的下标代表顶点 邻接矩阵中的元素A i j 存放的是顶点i到顶点j之间关系的信息 定义intG 101 101 G i j 的值 表示从点i到点j的边的权值 定义如下 上图中的3个图对应的邻接矩阵分别如下 0111011 58 3G A 1011G B 0015 2 61100010G C 82 1041100 10 1136411 另外有向图是有讲究的 要考虑入度和出度 顶点V1的入度为1 正好是第V1列的各数之和 顶点V1的出度为2 正好是第V1行的各数之和 下面是建立图的邻接矩阵的参考程序段 includeusingnamespacestd inti j k e n doubleg 101 101 doublew intmain inti j for i 1 i e for k 1 k i j w 读入两个顶点序号及权值g i j w 对于不带权的图g i j 1g j i w 无向图的对称性 如果是有向图则不要有这句 return0 建立邻接矩阵时 有两个小技巧 初始化数组大可不必使用两重for循环 1 如果是int数组 采用memset g 0 x7f sizeof g 可全部初始化为一个很大的数 略小于0 x7fffffff 使用memset g 0 sizeof g 全部清为0 使用memset g 0 xaf sizeof g 全部初始化为一个很小的数 2 如果是double数组 采用memset g 127 sizeof g 可全部初始化为一个很大的数1 38 10306 使用memset g 0 sizeof g 全部清为0 2 数组模拟邻接表存储邻接矩阵看上去是个不错的选择 首先是容易理解 第二是索引和编排都很舒服但是我们也发现 邻接矩阵适合于结点数较少的稠密图 如果用来表示稀疏图 则会造成很大的空间浪费 因此我们可以考虑另外一种存储结构方式 例如把数组与链表结合一起来存储 这种方式在图结构也适用 我们称为邻接表 AdjacencyList 基本思想 对图的每个顶点建立一个单链表 存储该顶点所有邻接顶点及其相关信息 每一个单链表设一个表头结点 第i个单链表表示依附于顶点Vi的边 对有向图是以顶点Vi为头或尾的弧 图的邻接表存储法 又叫链式存储法 本来是要用链表实现的 但大多数情况下只要用数组模拟即可 邻接表 有向图 邻接表的处理方法是这样 图中顶点用一个一维数组存储 当然 顶点也可以用单链表来存储 不过数组可以较容易地读取顶点信息 更加方便 图中每个顶点Vi的所有邻接点构成一个线性表 由于邻接点的个数不确定 所以我们选择用单链表来存储 若是有向图 邻接表结构就是这样定义的 有向图的邻接表 我们先来看下把顶点当弧尾建立的邻接表 这样很容易就可以得到每个顶点的出度 但也有时为了便于确定顶点的入度或以顶点为弧头的弧 我们可以建立一个有向图的逆邻接表 此时我们很容易就可以算出某个顶点的入度或出度是多少 判断两顶点是否存在弧也很容易实现 对于带权值的网图 可以在边表结点定义中再增加一个数据域来存储权值即可 邻接表 网 在进行邻接表的输入时 可以直接使用邻接表的定义方式直接输入 也可由别的输入方式进行演变 课本上的就是利用边的顶点及其权值进行输入的 以下是用数组模拟邻接表存储的参考程序段 constintN maxn maxn表示图中最大顶点数constintE maxe maxe图中最大边数structEdge intu v 边所邻接的两个顶点intw 边的权值intnext 边指针 指向下一条边的内存地址 edge E 静态内存 用于分配边inthead N 表头intnum 内存的指针voidinit for inti 0 i E i head i 1 这里为什么要设为 1num 0 voidaddedge intb inte intw edge num u b edge num v e edge num w w edge num next head b head b num intmain num edge 0 scanf d d 两种方法各有用武之地 需按具体情况 具体选用 例题 求一个有向图中指定顶点的出度 问题描述 如题 文件输入 第1行 2个空格分开的整数n 2 n 200 和m 10 m 20000 分别表示图的顶点数和边数 第2 m 1行 每行2个空格分开的整数i j i表示一条边的起点 j表示终点 第m 2行 1个整数k 2 k n 表示指定的顶点 文件输出 只有一行为1个整数 表示顶点k的出度 样例输入 5835454323544142244 样例输出 4 参考代码 方法1 邻接矩阵存储图 includeusingnamespacestd inta 201 201 n m ans 0 x voidinit inti j k cin n m for i 1 i j k a j k 1 intmain init cin k for inti 1 i n i if a k i ans cout ans endl 方法2 邻接表存储图 includeusingnamespacestd structEdge intto next w 20005 inth Maxn 0 i x y z n e k cnt ans 0 voidAddEdge intx inty cnt w cnt to y w cnt next h x h x cnt intmain cin n e 读入顶点数目和边数for i 1 i x y AddEdge x y 建图cin k for intp h k p 0 p w p next ans cout ans endl 第二节图的遍历 一 深度优先与广度优先遍历从图中某一顶点出发系统地访问图中所有顶点 使每个顶点恰好被访问一次 这种运算操作被称为图的遍历 为了避免重复访问某个顶点 可以设一个标志数组visited i 未访问时值为false 访问一次后就改为true 图的遍历分为深度优先遍历和广度优先遍历两种方法 两者的时间效率都是O n n 1 深度优先遍历深度优先搜索 DepthFirstSearch DFS 遍历类似树的先序遍历 是树的先序遍历的推广 1算法思想设初始状态时图中的所有顶点未被访问 则 从图中某个顶点vi出发 访问vi 然后找到vi的一个邻接顶点vi1 从vi1出发 深度优先搜索访问和vi1相邻接且未被访问的所有顶点 转 直到和vi相邻接的所有顶点都被访问为止 继续选取图中未被访问顶点vj作为起始顶点 转 1 直到图中所有顶点都被访问为止 例如对右边的这个无向图深度优先遍历 假定先从1出发程序以如下顺序遍历 1 2 5 然后退回到2 退回到1 从1开始再访问未被访问过的点3 3没有未访问的邻接点 退回1 再从1开始访问未被访问过的点4 再退回1 起点1的所有邻接点都已访问 遍历结束 下面给出的深度优先遍历的参考程序 假设图以邻接表存储voiddfs inti 图用数组模拟邻接表存储 访问点i visited i true 标记为已经访问过for intj 1 j num i j 遍历与i相关联的所有未访问过的顶点if visited g i j dfs g i j 主程序如下 intmain memset visited false sizeof visited for inti 1 i n i 每一个点都作为起点尝试访问 因为不是从任何 一点开始都能遍历整个图的 例如下面的两个图 if visited i dfs i return0 广度优先搜索BFS 广度优先搜索 BreadthFirstSearch BFS 遍历类似树的按层次遍历的过程 1算法思想设初始状态时图中的所有顶点未被访问 则 从图中某个顶点vi出发 访问vi 访问vi的所有相邻接且未被访问的所有顶点vi1 vi2 vim 以vi1 vi2 vim的次序 以vij 1 j m 依此作为vi 转 继续选取图中未被访问顶点vk作为起始顶点 转 直到图中所有顶点都被访问为止 下图是有向图的广度优先搜索遍历示例 浅色箭头 上述图的BFS次序是 v1 v2 v4 v3 v5 用广度优先搜索算法遍历图与深度优先搜索算法遍历图的唯一区别是邻接点搜索次序不同 因此 广度优先搜索算法遍历图的总时间复杂度为O n e 图的遍历可以系统地访问图中的每个顶点 因此 图的遍历算法是图的最基本 最重要的算法 许多有关图的操作都是在图的遍历基础之上加以变化来实现的 例题 无向图的BFS 问题描述 一个无向图 从指定顶点出发进行BFS 求遍历得到的顶点序 文件输入 第1行 2个空格分开的整数n 2 n 200 和m 10 m 20000 分别表示图的顶点数和边数 第2 m 1行 每行2个空格分开的整数i j i表示一条边的起点 j表示终点 第m 2行 1个整数k 1 k n 表示指定的顶点 文件输出 只一行顶点序 要求在同一层上 顶点序号从小到大输出 includeusingnamespacestd inta 101 101 f 101 q 101 n m i st voidinit inti j x y cin n m memset f 0 sizeof f for i 1 i x y a x y 1 a y x 1 cin st voiddfs inti 深搜DFS intj cout i f i 1 for j 1 j n j if f j 0 二 欧拉图 1 欧拉路 欧拉路径 图G中每条边经过一次且仅一次的路径称作欧拉路径 如下图中存在一条从顶点1到顶点6的欧拉路 一笔画问题其实本质上就是判断一个图是否存在欧拉路 无向图欧拉路存在的充要条件 图是连通的 图中有且仅有0个或2个度数为奇数的点 若存在2个奇点 则欧拉路一定是从一个奇点出发 以另一个奇点结束 2 欧拉回路 图G中每条边经过一次且仅一次的回路称作欧拉回路 著名的柯尼斯堡七桥问题 图论起源 本质上就是讨论一个图的欧拉回路问题 一个无向图有欧拉回路的必要条件是 图是连通的 图中所有点的度均为偶数 求欧拉路的算法很简单 使用深度优先遍历即可 根据一笔画的两个定理 如果寻找欧拉回路 对任意一个点执行深度优先遍历 找欧拉路 则对一个奇点执行DFS 时间复杂度为O m n m为边数 n是点数 以下是寻找一个图的欧拉路的算法实现 样例输入 第一行n m 有n个点 m条边 以下m行描述每条边连接的两点 551223344551样例输出 欧拉路或欧拉回路154321 参考程序 Euler cpp include includeusingnamespacestd definemaxn101intg maxn maxn 此图用邻接矩阵存储intdu maxn 记录每个点的度 就是相连的边的数目intcircuit maxn 用来记录找到的欧拉路的路径intn e circuitpos i j x y start voidfind circuit inti 这个点深度优先遍历过程寻找欧拉路 intj for j 1 j n j if g i j 1 从任意一个与它相连的点出发 g j i g i j 0 find circuit j circuit circuitpos i 记录下路径 intmain memset g 0 sizeof g cin n e for i 1 i x y g y x g x y 1 du x 统计每个点的度du y start 1 如果有奇点 就从奇点开始寻找 这样找到的就是for i 1 i n i 欧拉路 没有奇点就从任意点开始 if du i 2 1 这样找到的就是欧拉回路 因为每一个点都是偶点 start i circuitpos 0 find circuit start for i 1 i circuitpos i cout circuit i cout endl return0 注意以上程序具有一定的局限性 对于下面这种情况它不能很好地处理 上图具有多个欧拉回路 而本程序只能找到一个回路 读者在遇到具体问题时 还应对程序作出相应的修改 三 哈密尔顿环欧拉回路是指不重复地走过所有路径的回路 而哈密尔顿环是指不重复地走过所有的点 并且最后还能回到起点的回路 哈密顿通路 回路 与哈密顿图 Hamilton图 通过图G的每个结点一次 且仅一次的通路 回路 就是哈密顿通路 回路 存在哈密顿回路的图就是哈密顿图 美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件 对于顶点个数大于2的图 如果图中任意两点度的和大于或等于顶点总数 那这个图一定是哈密顿图 闭合的哈密顿路径称作哈密顿圈 含有图中所有顶点的路径称作哈密顿路径 例题1 哈密顿路问题 问题描述 邮递员在送信时 为了节省路途 自己规定 每次总是从n个村子中选择其中一个合适的村子出发 途经每个村子仅且经过一次 送完所有的信 已知各个村子的道路连通情况 请你帮邮递员选择一条合适的路线 文件输入 第1行 整数n 2 n 200 村子的个数 接下来是一个n n的0 1矩阵 每2个数之间有1个空格 表示n个村子的连通情况 如 a i j 1 表示第i和第j个村子之间有路可走 如果a i j 0 表示他们之间无路可走 文件输出 只有一行为1个整数表示可行的方案总数 include includeusingnamespacestd inta 201 201 visit 201 found n sum voidinit inti j scanf d intmain inti init found 0 sum 0 for i 1 i n i memset visit 0 sizeof visit visit i 1 dfs i 1 if found 0 printf d 0 elseprintf d sum return0 使用简单的深度优先搜索 就能求出一张图中所有的哈密尔顿环 下面给出一段参考程序 include includeusingnamespacestd intstart length x n boolvisited 101 v1 101 intans 101 num 101 intg 101 101 voidprint inti for i 1 i length i cout ans i cout endl voiddfs intlast inti 图用数组模拟邻接表存储 访问点i last表示上次访问的点 visited i true 标记为已经访问过v1 i true 标记为已在一张图中出现过ans length i 记录下答案for intj 1 j num i j if g i j x 这里是回溯过程 注意v1的值不恢复 intmain memset visited false sizeof visited memset v1 false sizeof v1 for x 1 x n x 每一个点都作为起点尝试访问 因为不是从任何一点开始都能找过整个图的if v1 x 如果点x不在之前曾经被访问过的图里 length 0 定义一个ans数组存答案 length记答案的长度 dfs 0 x return0 上机练习 1 珍珠BEAD 问题描述 有n颗形状和大小都一致的珍珠 它们的重量都不相同 n为整数 所有的珍珠从1到n编号 你的任务是发现哪颗珍珠的重量刚好处于正中间 即在所有珍珠的重量中 该珍珠的重量列 n 1 2位 下面给出将一对珍珠进行比较的办法 给你一架天平用来比较珍珠的重量 我们可以比出两个珍珠哪个更重一些 在作出一系列的比较后 我们可以将某些肯定不具备中间重量的珍珠拿走 例如 下列给出对5颗珍珠进行四次比较的情况 1 珍珠2比珍珠1重2 珍珠4比珍珠3重3 珍珠5比珍珠1重4 珍珠4比珍珠2重根据以上结果 虽然我们不能精确地找出哪个珍珠具有中间重量 但我们可以肯定珍珠1和珍珠4不可能具有中间重量 因为珍珠2 4 5比珍珠1重 而珍珠1 2 3比珍珠4轻 所以我们可以移走这两颗珍珠 写一个程序统计出共有多少颗珍珠肯定不会是中间重量 输入格式 输入文件第一行包含两个用空格隔开的整数N和M 其中1 N 99 且N为奇数 M表示对珍珠进行的比较次数 接下来的M行每行包含两个用空格隔开的整数x和y 表示珍珠x比珍珠y重 输出格式 输出文件仅一行包含一个整数 表示不可能是中间重量的珍珠的总数 输入样例 BE