wap网站制作工具,网站的建设技术有哪些内容,男女直接做的视频网站免费观看,网站动效是代码做的吗前言
图论基础
图的相关概念
图的定义
图的分类
按数量分类#xff1a;
按边的类型分类#xff1a;
边权
简单图
度
路径
连通
无向图
有向图
图的存储
方法概述
代码
复杂度 前言 图论#xff08;Graph theory#xff09;#xff0c;是 OI 中的一样很大…前言
图论基础
图的相关概念
图的定义
图的分类
按数量分类
按边的类型分类
边权
简单图
度
路径
连通
无向图
有向图
图的存储
方法概述
代码
复杂度 前言 图论Graph theory是 OI 中的一样很大的一个模块围绕它有很多高难度的算法以及高级的概念。这篇文章将介绍关于图论的一部分基础概念干货满满话不多说步入正题—— 图论基础
干货太多了建议先收藏
图的相关概念
图的定义
图graph是一个二元组 G (V(G), E(G))。其中 V(G) 是非空集称为 点集vertex set对于 V 中的每个元素我们称其为 顶点vertex或 节点node简称 点E(G) 为 V(G) 各结点之间边的集合称为 边集edge set。
我们一般用 G (V, E) 表示图。 举个例子 这就是一张图12345 就是它的节点。 推荐一个网站Cs Academy 这里有十分好用的图编辑器可以帮你加强理解图论 图的分类
按数量分类
当 V, E 都是有限集合时称 G 为 有限图。
当 V 或 E 是无限集合时称 G 为 无限图。
按边的类型分类
图有多种包括 无向图 (undirected graph)有向图 (directed graph)混合图 (mixed graph) 等。
若为无向图则图中的每个元素为一个无序二元组 (u, v)称作 无向边 (undirected edge)简称 边 (edge)其中 u, v ∈ V。设 e (u, v)则 u 和 v 称为 e 的 端点 (endpoint)。
若为有向图则图中的每一个元素为一个有序二元组 (u, v)有时也写作 u → v称作 有向边 (directed edge) 或 弧 (arc)在不引起混淆的情况下也可以称作 边 (edge)。设 e u → v 则此时 u 称为 e 的 起点 (tail)v 称为 e 的 终点 (head)起点和终点也称为 e 的 端点 (endpoint)。并称 u 是 v 的直接前驱v 是 u 的直接后继。
若为混合图则图中既有 有向边又有 无向边。 还拿这张图来说这是一个无向图。 这就是一张有向图。 边权
若图的每条边都被赋予一个数作为该边的 权则称这张图为 赋权图。如果这些权都是正实数就称为 正权图。 这张图就是一张 赋权图。 简单图
自环 (loop)对 E 中的边 e (u,v) 若 u v 则 e 被称作一个自环。
重边 (multiple edge)若 E 中存在两个完全相同的元素边e1,e2 则它们被称作一组重边。
简单图 (simple graph)若一个图中没有自环和重边它被称为简单图。具有至少两个顶点的简单无向图中一定存在度相同的结点。
如果一张图中有自环或重边则称它为 多重图 (multigraph)。
度
与一个顶点 v 关联的边的条数称作该顶点的 度 (degree)记作 d(v)。特别地对于边 (v, v)则每条这样的边要对 d(v) 产生 2 的贡献。
对于无向简单图有 d(v) |N(v)|。
推论在任意图中度数为奇数的点必然有偶数个。一笔画问题应该了解过吧
若 d(v) 0则称 v 为 孤立点 (isolated vertex)。
若 d(v) 1则称 v 为 叶节点 (leaf vertex)/悬挂点 (pendant vertex)。
若 2 | d(v)则称 v 为 偶点 (even vertex)否则为 奇点 (odd vertex)。
若 d(v) |V| - 1则称 v 为 支配点 (universal vertex)。
这些概念了解就行了不需要特别去记
对一张图所有节点的度数的最小值称为 最小度 (minimum degree)最大值称为 最大度 (maximum degree)。
在有向图中以一个顶点为起点的边的条数称为该顶点的 出度 (out-degree)以一个顶点 为终点的边的条数称为该节点的 入度 (in-degree)。
如果给定一个序列 a可以找到一个图 G以其为度数列则称 a 是 可图化 的。
如果给定一个序列 a可以找到一个简单图 G以其为度数列则称 a 是 可简单图化 的。
路径
途径 (walk)途径是连接一连串顶点的边的序列可以为有限或无限长度。形式化地说一条有限途径 w 是一个边的序列 e1,e2,...,ek使得存在一个顶点序列 v0,v1,...,vk 满足 ei (v i-1,v i)其中 i ∈ [1, k] 。这样的途径可以简写为 v0 → v1 → v2 → ... → vk 。通常来说边的数量 k 被称作这条途径的 长度如果边是带权的长度通常指途径上的边权之和题目中也可能另有定义。 看不懂我也看不懂为了更好地理解可以把一张图当作一个地图节点就是车站边就是路那么路径就是从一个车站到另一个车站的路线。如果这张图是赋权图也就是说车站之间有了距离那么路径的 长度 就是车站到车站的路线的长度。 回路 (circuit)对于一条路径 w若 v0 vk则称 w 是一条回路。
连通
无向图
对于一张无向图 G (V,E)对于 u,v ∈ V若存在一条途径使得 v0 u, vk v则称 u 和 v 是 连通的 (connected)。由定义任意一个顶点和自身连通任意一条边的两个端点连通。
若无向图 G (V,E)满足其中任意两个顶点均连通则称 G 是 连通图 (connected graph)这一性质称作 连通性 (connectivity)。
有向图
对于一张有向图 G (V,E)对于 u,v ∈ V若存在一条途径使得 v0 u, vk v, 则称 u 可达 v。由定义任意一个顶点可达自身任意一条边的起点可达终点。无向图中的连通也可以视作双向可达。
若一张有向图的节点两两互相可达则称这张图是 强连通的 (strongly connected)。
若一张有向图的边替换为无向边后可以得到一张连通图则称原来这张有向图是 弱连通的 (weakly connected)。 到这你已经看过了图的大部分概念。全是干货如果还没理解可以收藏起来慢慢看 图的存储
本文会介绍最常用的存储方法也就是直接存边。
方法概述
使用一个数组来存边数组中的每个元素都包含一条边的起点与终点带边权的图还包含边权。
代码
struct Edge {int u, v;
};
vectorEdge e;
复杂度
查询是否存在某条边O(m) 。
遍历一个点的所有出边O(m) 。
遍历整张图O(nm) 。
空间复杂度O(m) 。 干货太多整理得肝疼求个点赞收藏不过分吧求求了
本文就到这里下次再见
