《NOIP普与讲座7-图基本知识(C++版)》由会员分享，可在线阅读，更多相关《NOIP普与讲座7-图基本知识(C++版)（41页珍藏版）》请在金锄头文库上搜索。
1、图的基本知识 图的概念 图的存储 图的遍历 图的应用 图的引入 1736年欧拉利用图论思想解决了哥尼斯堡七桥问题 一笔画 1 图的表示 2 无向图 有向图 带权图 提问 指出上图中哪个是无向图 哪个是有向图 哪个是带权图 相关概念 2 提问2 有向图中所有顶点的入度之和是 大于 等于 小于 所有顶点的出度之和 提问3 任意一个无向图一定有 偶数 奇数 个奇点 以上为关于图的度的三个定理 2 顶点的阶 度 入度 出度 奇点 偶点 课上小练 1 假设我们用d a1 a2 a5 表示无向图G的5个顶点的度数 下面给出的哪 些 组d值合理 A 5 4 4 3 1 B 4 2 2 1 1 C 3 3 3
2、 2 2 D 5 4 3 2 1 E 2 2 2 2 2 2 无向图G有16条边 有3个4度顶点 4个3度顶点 其余顶点的度均小于3 则G至少 个顶点 3 一个无向图有4个结点 其中3个的度数为2 3 3 则第4个结点的度数不可能是 北京理工 99年 A 0B 1C 2D 4 相关概念 欧拉图 1 定义 欧拉通路 通过图中每条边一次且仅一次 并且过每一顶点的通路 欧拉回路 通过图中每条边一次且仅一次 并且过每一顶点的回路 欧拉图 存在欧拉回路的图 2 定理1 存在欧拉路的条件 图是连通的 且存在0个或2个奇点 如果存在2个奇点 则欧拉路一定是从一个奇点出发 以另一个奇点结束 定理2 存在欧拉回
3、路的条件 图是连通的 且不存在奇点 相关概念 周游世界游戏问题 哈密尔顿图 1 定义 哈密尔顿通路 通过图中每个顶点一次且仅一次的通路 哈密尔顿回路 通过图中每个顶点一次且仅一次的回路 哈密尔顿图 存在哈密尔顿回路的图 2 判定 遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件 课上小练 在下图中 从顶点 出发存在一条路径可以遍历图中的每条边一次 而且仅遍历一次 A A点B B点C C点D D点E E点 课上小练 判断下图是否具有哈密尔顿回路 通路 例1 城市公交网 有一张城市地图 图中的顶点为城市 无向边代表两个城市间的连通关系 边上的权为在这两个城市之间修建高速公路的造价 研究
4、后发现 这个地图有一个特点 即任一对城市都是连通的 现在的问题是 要修建若干高速公路把所有城市联系起来 问如何设计可使得工程的总造价最少 例2 奇怪的电梯 呵呵 有一天我做了一个梦 梦见了一种很奇怪的电梯 大楼的每一层楼都可以停电梯 而且第i层楼 1 i N 上有一个数字Ki 0 Ki N 电梯只有四个按钮 开 关 上 下 上下的层数等于当前楼层上的那个数字 当然 如果不能满足要求 相应的按钮就会失灵 例如 33125代表了Ki K1 3 K2 3 从一楼开始 在一楼 按 上 可以到4楼 按 下 是不起作用的 因为没有 2楼 那么 从A楼到B楼至少要按几次按钮呢 核心 主要是点 边的存储 所以
5、我们想尽办法 存储 建立模型 1 邻接矩阵 邻接矩阵 是表示顶点之间相邻关系的矩阵 设G V E 是具有n个顶点的图 顶点序号依次为1 2 n 则G的邻接矩阵是具有如下定义的n阶方阵 图的存储 A2 0001000001010000110000000 建立带权无向图的领接矩阵 intmain constmax 1E5 n 10 intg n 1 n 1 inti j k e w g graph for i 1 i n i for j 1 j n j g i j max 输入样式 81221312141023825946353457 for i 1 i n i for j 1 j n j cou
6、t g i j cout endl cin e for k 1 k i j w g i j w g j i w 2 边集数组 边集数组 是利用一维数组存储图中所有边的一种图的表示方法 起点 终点 权 无向带权图的边集数组表示法 图的边集数组表示算法描述 以无向带权图为例 voidcreate3 GE 图用边集数组存储 for k 1 k i j w 读入一条边 Vi Vj 的两端点序号及权值 G k formvex i G k endvex j G k weight w 有向图 它表示为 静态数组 3 静态数组 静态数组 是对图中的每个顶点建立一个邻接关系的数组 0 1 2 3 4 1 2 3
7、 4 5 0 1 4 1 1 2 5 2 2 3 voidcreatelist memset g 0 sizeof g cin n e for k 1 k i j g i 0 g i g i 0 j 建立有向图的静态数组 输入样式 51425324243 4 图的三种存储结构比较 n阶e条边 例1 城市公交网 有一张城市地图 图中的顶点为城市 无向边代表两个城市间的连通关系 边上的权为在这两个城市之间修建高速公路的造价 研究后发现 这个地图有一个特点 即任一对城市都是连通的 现在的问题是 要修建若干高速公路把所有城市联系起来 问如何设计可使得工程的总造价最少 核心 主要是点 边的存储 所以我们
8、想尽办法 存储 图的应用 遍历 穷举 搜索 1 深度优先搜索 对下面两个图分别进行深度优先搜索 写出搜索结果 注意 分别从1出发 左图从顶点1出发 进行深度优先搜索的结果为 1 2 3 4 5右图从1出发进行深度优先搜索的结果为 1 4 2 5 3 图的搜索分为深度优先搜索和广度 宽度 优先搜索两种方法 对下图从1出发进行宽度优先搜索 写出搜索结果 2 广度优先搜索 左图从顶点1出发 进行广度优先搜索的结果为 1 2 3 4 5右图从顶点1出发 进行广度优先搜索的结果为 1 4 2 3 5 无向图G V E 其中V a b c d e f E a b a e a c b e c f f d e
9、 d 对该图进行深度优先遍历 得到的顶点序列正确的是 A a b e c d fB a c f e b dC a e b c f dD a b e d f c 轻松小练 该图进行广度优先遍历 得到的顶点序列正确的是什么 例1的深度优先遍历的递归过程如下 vioddfs inti 图用邻接矩阵存储 访问顶点i visited i true for j 1 j n j if NotVisited j a i j 1 dfs j 以上dfs i 的时间复杂度为O n n 对于一个非连通图 调用一次dfs i 即按深度优先顺序依次访问了顶点i所在的 强 连通分支 所以只要在主程序中加上 for i 1
10、 i n i 深度优先搜索每一个未被访问过的顶点 if notVisited dfs i 时间 O n n 例1的广度优先遍历如下 voidbfs inti 宽度优先遍历 图用邻接矩阵表示 访问顶点i Visited i true 顶点i入队q while 队列q非空 head v q head v for j 1 j n j if notVisited j 例2 奇怪的电梯 DFS BFS程序 请同学们课后独立完成 例3单词游戏 有N个盘子 每个盘子上写着一个仅由小写字母组成的英文单词 你需要给这些盘子按照合适的顺序排成一行 使得相邻两个盘子中 前一个盘子上面单词的末字母等于后一个盘子上面单
11、词的首字母 请你编写一个程序 判断是否能达到这一要求 如果能 请给出一个合适的顺序 样例 malform mouse acm 样例 malform mouse acm m m m m 模型1 将每个盘子看作一个顶点 如果盘子B能连接在盘子A后面 那么从A向B连一条有向边 模型1 问题转化为在图中寻找一条不重复地经过所有顶点的路径 即哈密尔顿路 但是 求哈密尔顿路是一个十分困难的问题 这样的建模没有给解题带来任何便利 我们必须另辟蹊径 模型2 以26个英文字母作为顶点 对于每一个单词 在图中从它的首字母向末字母连一条有向边 模型2 问题转化为在图中寻找一条不重复地经过所有边的路径 即欧拉路径 这
12、个问题能够在O E 时间内解决 小结 比较以上两个模型 模型1过于直接 模型2则打破了 顶点表示元素 边表示元素之间关系 的思维定势 将元素表示在边上 而顶点则起到连接各个元素的作用 例4拦截匪徒 catch 某市的地图是一个由n个点组成的无向图 每个点代表一个区 现在第p区发生了抢劫案 而警察为了截住匪徒埋伏在一个匪徒必经的区域 由于不知道匪徒会向哪个区域逃窜 局长要求身为警察局电脑专家的你计算出对于任意一个匪徒可能逃向的区j 找出一个可以截住匪徒的区k 即匪徒从p区逃向j区 必经过k区 由于地区j可能为匪徒的老巢所在 所以局长希望在路上拦住匪徒 而不是在j区抓捕 输入数据 第一行为n p
13、1 p n 100 接下来为n n的矩阵A A i j 1表示i区和j区有路相连 反之为0 输入数据 输出n 1行 按顺序从j 1 2 n依次输出对于每一个j 警察可以在哪些点埋伏 如有多个点 则要按照从小到大的顺序依次输出 如没有 则对应行输出 NO 输入样例 510110010110110000100100010 输出样例 NONO224 问题分析 简单地说 本题就是求无向图上一点到其他所有点的必经点 分析题目中所给的数据范围便会发现 用最简单的删点加上遍历图就可以完成 其实就是穷举点 我们用answer这个二维数组来记录哪些是关键点 割点 开始清为0 先删一个点i 然后遍历整幅图 看对于任意一个点j p是否与它连通 不连通就将answer i j 赋为1 表示i是从p到j的必经点 这样 把每个点都删过一次后 所有的必经点就求出来了 删除一个点只需要在深度搜索遍历之前 将该点标为已访问过 每次遍历之前都要初始化一些标记数组 有可能一开始图就是不连通的 这样的话 删了点之后就依然不连通 这时这个点就不一定是必经点了 请思考 要是范围变大 不能用 穷举 算法 又该怎么办 课堂总结 1 做图论题的关键 建模 什么是 点 什么是 边 2 建模好之后用什么算法进行解决 是遍历 搜索 还是其它在图论上的一些算法 例如 求最短路径 最小生成树 拓扑排序 二分匹配 网络流
