【C++算法竞赛 · 图论】图论基础

前言

图论基础

图的相关概念

图的定义

图的分类

按数量分类:

按边的类型分类:

边权

简单图

路径

连通

无向图

有向图

图的存储

方法概述

代码

复杂度


前言

图论(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) 表示图。

举个例子:

这就是一张图,1,2,3,4,5 就是它的节点。

推荐一个网站: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),则 uv 称为 e 的 端点 (endpoint)

若为有向图,则图中的每一个元素为一个有序二元组 (u, v),有时也写作 u → v,称作 有向边 (directed edge) 或 弧 (arc),在不引起混淆的情况下也可以称作 边 (edge)。设 e = u → v ,则此时 称为 e 的 起点 (tail)v 称为 e 的 终点 (head),起点和终点也称为 e 的 端点 (endpoint)。并称 uv 的直接前驱,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,则称 uv 是 连通的 (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;
};
vector<Edge> e;

复杂度

查询是否存在某条边:O(m)

遍历一个点的所有出边:O(m) 

遍历整张图:O(nm)

空间复杂度:O(m)


干货太多,整理得肝疼,求个点赞收藏不过分吧!(求求了!)

本文就到这里,下次再见!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520669.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

小米造车,特斯拉销量不满人意,马斯克坐不住了:将于8月8日推出自动驾驶出租车

在Elon Musk声称路透社关于“放弃2.5万美元低成本电动汽车计划&#xff0c;而将所有精力集中于Robotaxi&#xff08;自动驾驶出租车&#xff09;”上的报道“撒谎”仅几小时后&#xff0c;特斯拉首席执行官在X社交平台上宣布&#xff0c;他将在8月8日的活动中揭示这款所谓的Rob…

Android APP加固利器:深入了解混淆算法与混淆配置

Android APP 加固是优化 APK 安全性的一种方法&#xff0c;常见的加固方式有混淆代码、加壳、数据加密、动态加载等。下面介绍一下 Android APP 加固的具体实现方式。 混淆代码 使用 ipaguard工具可以对代码进行混淆&#xff0c;使得反编译出来的代码很难阅读和理解&#xff…

相对论中关于光速不变理解的补充

近几个月在物理直播间聊爱因斯坦相对论&#xff0c;发现好多人在理解爱因斯坦相对论关于基本假设&#xff0c;普遍认为光速是不变的&#xff0c;质能方程 中光速的光速不变的&#xff0c;在这里我对这个假设需要做一个补充&#xff0c;他是基于质能方程将光速C 在真是光速变化曲…

JavaEE 初阶篇-生产者与消费者模型(线程通信)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 生产者与消费者模型概述 2.0 在生产者与消费者模型中涉及的关键概念 2.1 缓冲区 2.2 生产者 2.3 消费者 2.4 同步机制 2.5 线程间通信 3.0 实现生产者与消费者模…

【Python】 小顶堆:困难 Leetcode 23. 合并 K 个升序链表 -- Python中heapq对于自定义数据类型的比较

描述 给你一个链表数组&#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中&#xff0c;返回合并后的链表。 示例 1&#xff1a; 输入&#xff1a;lists [[1,4,5],[1,3,4],[2,6]] 输出&#xff1a;[1,1,2,3,4,4,5,6] 代码 代码1 由于可能存在相同…

构造函数和析构函数

目录 一&#xff1a;类的六个默认函数 二&#xff1a;构造函数 2.1概念 2.2特性 三&#xff1a;析构函数 3.1概念&#xff1a; 3.2特性 一&#xff1a;类的六个默认函数 如果一个类中什都没有&#xff0c;称为空类 空类中真的什么都没有吗?并不是&#xff0c;任何类在…

MySQL客户端安装并配置免密登录

最近在写脚本时需要向MySQL数据库中存储数据&#xff0c;且脚本运行的服务器与MySQL服务器不是同一台服务器&#xff0c;而且需要保证MySQL密码的安全性&#xff0c;不能在脚本中暴露&#xff0c;所以就需要在服务器上安装MySQL客户端&#xff0c;并配置免密登录。 一、虚拟机…

C++ List 到 Python List 的转换

当我们编写 C 库的封装器通常涉及使用一种跨语言的接口技术&#xff0c;比如使用C接口或者使用特定的跨语言库&#xff0c;比如SWIG&#xff08;Simplified Wrapper and Interface Generator&#xff09;或者Pybind11。这里我将简要介绍如何使用Pybind11来封装一个C库&#xff…

jenkins+docker实现可持续自动化部署springboot项目

目录 一、前言 二、微服务带来的挑战 2.1 微服务有哪些问题 2.2 微服务给运维带来的挑战 三、可持续集成与交付概述 3.1 可持续集成与交付概念 3.1.1 持续集成 3.1.2 持续交付 3.1.3 可持续集成与交付核心理念 3.2 可持续集成优点 3.3 微服务为什么需要可持续集成 四…

金三银四面试题(十五):Java基础问题(6)

这部分面试题多用于面试的热身运动&#xff0c;对很多找实习和准备毕业找工作的小伙伴至关重要。 HashMap与ConcurrentHashMap 都是key-value 形式的存储数据&#xff1b; HashMap 是线程不安全的&#xff0c;ConcurrentHashMap 是JUC 下的线程安全的&#xff1b; HashMap 底层…

降低笔记本电脑噪音的七种方法,看下有没有适合你的

序言 无论是玩游戏、浏览网络还是做严肃的工作,差不多都有这么一台笔记本电脑,它有足够的处理能力来处理几乎任何事情。不幸的是,它可能会变得非常大声,但有办法来遏制这种噪音。 清洁通风口和风扇,并使用硬表面 如果你的笔记本电脑现在比过去运行同样的软件时声音更大…

docker笔记(二):镜像、容器数据卷

四、 docker镜像 4.1 镜像 镜像是一种轻量级、可执行的独立软件包&#xff0c;用来打包软件运行环境和基于运行环境开发的软件&#xff0c;它包含运行某个软件所需的所有内容&#xff0c;包括代码、库、环境变量和配置文件 所有的应用&#xff0c;直接打包docker镜像就可以直…

深度学习500问——Chapter05: 卷积神经网络(CNN)(4)

文章目录 5.18 卷积神经网络凸显共性的方法 5.18.1 局部连接 5.18.2 权值共享 5.18.3 池化操作 5.19 全连接、局部连接、全卷积与局部卷积 5.20 局部卷积的应用 5.21 NetVLAD池化 参考文献 5.18 卷积神经网络凸显共性的方法 5.18.1 局部连接 我们首先了解一个概念&#xff0c…

Office办公软件之Excel的使用(一)

1、“开始”菜单中的部分属性 2、制作斜线表头 ctrl1,弹出设置单元格格式&#xff0c;选择“边框”&#xff0c;点击右下角有斜线的即可。 3、冻结窗口 一般冻结首列或首行&#xff0c;当我们翻页的时候&#xff0c;也能看到每一行的描述。 4、快捷键 1、 Ctrl1 设置单元格格…

【Java基础知识总结 | 第十篇】HashSet底层实现原理

文章目录 10.HashSet底层实现原理10.1HashSet特点10.2HashSet源码10.3 add流程10.4总结 10.HashSet底层实现原理 10.1HashSet特点 存储对象&#xff1a;HashSet 存储对象采用哈希表的方式&#xff0c;它不允许重复元素&#xff0c;即集合中不会包含相同的元素。当向 HashSet …

C语言实现快速排序算法

1. 什么是快速排序算法 快速排序的核心思想是通过分治法&#xff08;Divide and Conquer&#xff09;来实现排序。 算法的基本步骤是: 1. 选择一个基准值&#xff08;通常是数组中的某个元素&#xff09;&#xff0c;将数组分成两部分&#xff0c;使得左边的部分所有元素都小于…

2024.4.1-[作业记录]-day06-认识 CSS(三大特性、引入方式)

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; day06-认识 CSS(三大特性、引入方式) 文章目录 day06-认识 CSS(三大特性、引入方式)作业…

xss.pwnfunction-Ma Spaghet!

根据代码得知 这个是根据get传参的并且是由someboby来接收参数的 所以 <script>alert(1137)</script> js并没有执行因为 HTML5中指定不执行由innerHTML插入的<script>标签 所以 ?somebody<img%20src1%20onerror"alert(1337)"> 这样就成…

Java栈和队列的实现

目录 一.栈(Stack) 1.1栈的概念 1.2栈的实现及模拟 二.队列(Queue) 2.1队列的概念 2.2队列的实现及模拟 2.3循环队列 2.4双端队列&#xff08;Deque&#xff09; 一.栈(Stack) 1.1栈的概念 栈:一种特殊的线性表&#xff0c;其 只允许在固定的一端进行插入和删除元素操作…

JavaWeb--JavaScript Part 01

1. JavaScript概述 JavaScript&#xff08;简称JS&#xff09;是一种轻量级的、解释执行的客户端脚本语言&#xff0c;主要用于增强网页的交互性和动态性。它起源于Netscape的LiveScript&#xff0c;并在1995年发布时更名为JavaScript。尽管名称中包含"Java"&#xf…