没有合适的资源?快使用搜索试试~ 我知道了~
图论知识点+算法实现课件
需积分: 0 3 下载量 113 浏览量
2023-06-28
22:28:27
上传
评论
收藏 2.26MB PDF 举报
温馨提示
试读
31页
图论最短路算法是解决图中两点之间的最短路径问题的算法。主要有以下几种: 1. Dijkstra算法:从起点开始按照距离逐步扩展,记录每个点到起点的距离,并标记已经找到最短路径的点。 2. Bellman-Ford算法:允许边权为负数,通过松弛操作逐步更新每个点到起点的最短距离,可以检测负权环。 3. Floyd-Warshall算法:通过动态规划的方式计算每两个点之间的最短路径长度,适用于小规模图的情况。 4. A*算法:基于Dijkstra算法,但每次选择离目标点最近的点进行扩展,加速算法运行时间。 以上算法都可以在有向图或无向图中找到两点之间的最短路径。
资源推荐
资源详情
资源评论
图论
图论
1、 图论简介
1.1 、 图论的定义
1.2 图论的相关概念
1.2.1 、 图 (Grapg):定义
1.2.2 、 概念定义
相邻:
度: (针对于无向图和有向图)
入度和出度
图的类别
图上路径
子图
连通
图的稀疏
特殊的图
割点和桥
2、图的存储方式
2.1 、 直接存边
2.2、 邻接矩阵
2.3 、邻接表
2.4、 链式前向星
3、 DFS(图上)
DFS 序列
4、BFS(图上)
5、 拓扑排序
Kahn 算法(BFS做法)
如何判环呢?
如何输出字典序最小呢?
DFS拓扑
DFS判断是否存在环(比DFS来说,相对麻烦很多)
练习题1、 https://www.luogu.com.cn/problem/P1347 P1347 排序
6、最短路
性质
记号
图的松弛
最短路求取方法
6.1、 Dijkstra
6.2、 Floyd 算法
6.3、 SPFA
7、作业题:
习题1、 P1983 [NOIP2013 普及组] 车站分级
习题2、P1030 [NOIP2001 普及组] 求先序排列
习题3、 P1078 [NOIP2012 普及组] 文化之旅
1、 图论简介
详细信息
1.1 、 图论的定义
图论 (Graph theory) 是数学的一个分支,图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点
及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表
事物,连接两顶点的边则用于表示两个事物间具有这种关系。
来源于 图论 - 维基
百科,自由的百科全书
1.2 图论的相关概念
下述的知识在OI之中并不是全部都非常常见,图论作为一个难度较高的知识点,不同难度对应不同的
知识点;
1.2.1 、 图 (Grapg):定义
图 (graph) 是一个二元组 。其中
其中V(G)是非空集,称为 点集 (vertex set),对于V中的每个元素,我们称其为 顶点 (vertex) 或 节点
(node),简称 点;E(G)为 V(G)各结点之间边的集合,称为 边集 (edge set)。
常用
表示图。当V,E都是有限集合时,称为 G有限图。
当V或E是无限集合时,称G为 无限图。
图有多种,包括 无向图 (undirected graph),有向图 (directed graph),混合图 (mixed graph) 等。
若 G 为无向图,则 E 中的每个元素为一个无序二元组 (u, v),称作 无向边 (undirected edge),简称 边
(edge),其中
。设 e = (u, v),则 u 和 v 称为 e 的 端点 (endpoint)。
若 G 为有向图,则 E 中的每一个元素为一个有序二元组 (u, v),有时也写作
,称作 有向边 (directed edge) 或 弧 (arc),在不引起混淆的情况下也可以称作 边 (edge)。设 e =
,则此时 u 称为 e 的 起点 (tail),v 称为 e 的 终点 (head),起点和终点也称为 e 的 端点 (endpoint)。并
称 u 是 v 的直接前驱,v 是 u 的直接后继。
为什么起点是 tail,终点是 head?
若 G 为混合图,则 E 中既有 有向边,又有 无向边。
若 G 的每条边
都被赋予一个数作为该边的 权,则称 G 为 赋权图。如果这些权都是正实数,就称 G 为 正权图。
图 G 的点数
也被称作图 G 的 阶 (order)。
形象地说,图是由若干点以及连接点与点的边构成的。
1.2.2 、 概念定义
相邻:
在无向图 G = (V, E) 中,若点 v 是边 e 的一个端点,则称 v 和 e 是 关联的 (incident) 或 相邻的
(adjacent)。对于两顶点 u 和 v,若存在边 (u, v),则称 u 和 v 是 相邻的 (adjacent)。
一个顶点
的 邻域 (neighborhood) 是所有与之相邻的顶点所构成的集合,记作 N(v)。
一个点集 S 的邻域是所有与 S 中至少一个点相邻的点所构成的集合,记作 N(S),即:
度: (针对于无向图和有向图)
与一个顶点 v 关联的边的条数称作该顶点的 度 (degree),记作 d(v)。特别地,对于边 (v, v),则每条这
样的边要对 d(v) 产生 2 的贡献。
对于无向简单图,有
握手定理(又称图论基本定理):对于任何无向图 G = (V, E),有
推论:在任意图中,度数为奇数的点必然有偶数个。
若 d(v) = 0,则称 v 为 孤立点 (isolated vertex)。
若 d(v) = 1,则称 v 为 叶节点 (leaf vertex)/悬挂点 (pendant vertex)。
若
,则称 v 为 偶点 (even vertex)。
若
,则称 v 为 奇点 (odd vertex)。图中奇点的个数是偶数。
若
,则称 v 为 支配点 (universal vertex)。
入度和出度
对一张图,所有节点的度数的最小值称为 G 的 最小度 (minimum degree),记作
;最大值称为 最大度 (maximum degree),记作
。即:
, 。
在有向图 G = (V, E) 中,以一个顶点 v 为起点的边的条数称为该顶点的 出度 (out-degree),记作
。以一个顶点 v 为终点的边的条数称为该节点的 入度 (in-degree),记作
。显然
。
对于任何有向图 G = (V, E),有:
若对一张无向图 G = (V, E),每个顶点的度数都是一个固定的常数 k,则称 G 为 k- 正则图 (k-regular
graph)。
图的类别
自环 (loop):对 中的边 ,若 ,则 被称作一个自环。
重边 (multiple edge):若 中存在两个完全相同的元素(边),则它们被称作(一组)重边。
简单图 (simple graph):若一个图中没有自环和重边,它被称为简单图。具有至少两个顶点的简
单无向图中一定存在度相同的结点。(鸽巢原理)
抽屉原理
定义
抽屉原理,亦称鸽巢原理(the pigeonhole principle)。
它常被用于证明存在性证明和求最坏情况下的解。
简单情况
将 n+1 个物体,划分为 n 组,那么有至少一组有两个(或以上)的物体。
这个定理看起来比较显然,证明方法考虑反证法:假如每个分组有至多 1 个物体,那么最多有 1x
n 个物体,而实际上有 n+1 个物体,矛盾。
如果一张图中有自环或重边,则称它为 多重图 (multigraph)。
在 无 向 图 中 和 算 一 组 重 边 , 而 在 有 向 图 中 , 和 不 为 重 边 。
图上路径
途 径 : 途 径 是 连 接 一 连 串 顶 点 的 边 的 序 列 , 可 以 为 有 限 或 无 限 长 度 。
形 式 化 地 说 , 一 条 有 限 途 径 是 一 个 边 的 序 列 , 使 得 存 在 一 个 顶 点 序 列 满 足 ,
其 中 。 这 样 的 途 径 可 以 简 写 为 。
通 常 来 说 , 边 的 数 量 被 称 作 这 条 途 径 的 长 度 ( 如 果 边 是 带 权 的 , 长 度 通 常 指 途 径 上 的 边 权 之 和 , 题 目 中 也 可 能 另 有 定 义 ) 。
迹 : 对 于 一 条 途 径 , 若 两 两 互 不 相 同 , 则 称 是 一 条 迹 。
路 径 ( 又 称 简 单 路 径 : 对 于 一 条 迹 , 若 其 连 接 的 点 的 序 列 中 点 两 两 不 同 , 则 称 是 一 条 路 径 。
回 路 : 对 于 一 条 迹 , 若 , 则 称 是 一 条 回 路 。
环 圈 ( 又 称 简 单 回 路 简 单 环 :
对 于 一 条 回 路 , 若 是 点 序 列 中 唯 一 重 复 出 现 的 点 对 , 则 称 是 一 个 环 。
子图
对一张图 G = (V, E),若存在另一张图 H = (V', E') 满足
且
,则称 H 是 G 的 子图 (subgraph),记作
。
若对
,满足
,只要
,均有
,则称 H 是 G 的 导出子图/诱导子图 (induced subgraph)。
容易发现,一个图的导出子图仅由子图的点集决定,因此点集为
的导出子图称为 V' 导出的子图,记作
。
若
剩余30页未读,继续阅读
资源评论
LIURUOYU421308
- 粉丝: 15
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功