图论基础概念(详细讲解)

news/2024/9/11 3:45:43/ 标签: 图论

今天,我们讲解一下图论的概念,首先我们知道图是一个什么东西。

图你可以理解成一个网络系统,两个节点之间可能会有边,边链接两个节点,可能是有向(就比如说a只能往b,或者b只能往c),可能是无向(就是相当于没有方向,如果a和b有一条无向边的话,a可以往b,b可以往a),一条边可能有长度,我写一些图论题目常见的用词:
1.有向边:上面说了,他是有方向的,比如说a到b的有向边不能由b到a

2.无向边:上面说了,就是只要连上了两个都能到达

3.边权:代表边的长度,有些图可能不需要考虑边长,比如说判断两点是否可达这种问题是没有边权的。

4.反向边:只对有向边有效,比如说a->b,他的反向边就是b->a

5.重边:出现了两条一模一样的边,可能会影响后面的算法,所以说要注意(不过一般来讲,基础题是保证了没有重边,不过仍然需要注意)

6.自环:自己向自己连一条边,这种情况和重边一样的,也会影响算法,甚至可能让一些算法卡住。

7.链:对于任意一个节点,他们当中没有分叉,比如说这种:1->2,2->3这种,就有点像一条直线。这种数据可能需要小心,因为有些算法会在链上退化(比如说像BST(二叉搜索树)),不过有时候骗分的时候也可以特判链的情况。

8 .环:相当于把链的首尾相接,有时候环也会卡住。

9.树:这种数据比较友好,一些图的算法不会在上面退化,反倒还容易骗分一些,定义是:由n个节点和n-1条组成的无向无环图。

10.菊花图:就是所有点都连到了一个点,形成了一朵"菊花",有些算法会在上面退化,比如说spfa算法的O(km)会在菊花图的情况下变成O(nm)(这里一定要注意这种情况,以前NOI曾经有人写了spfa被菊花图卡了)

11.蒲公英图:菊花图和链组成起来,也会让一些算法退化。

12.负权/负权边:意思说一条边的权值为负数,这回让一些算法出问题(例如dijkstra最短路),这种时候必须要spfa算法了(当然不止这些,还有一些其他的算法也会在负权边上出问题)。

13.负权回路/负环:相当于一个环里所有数为负数,为让最短路算法卡进去(包括spfa),遇到负环可能需要用spfa判断负环.

14.正权回路/正环:根负环一样的,只不过是正数,这也会让求最长路时出问题

15.连通图:图是联通的,对于任意两点,他们都有一条路径。

16.点权:有一些题目,他不是边有长度,而是经过一个点有点权(比如说我经过一个点需要支付多少钱啊这种的),一般来讲,树形dp一般是没有边权而是点权。


http://www.ppmy.cn/news/1475396.html

相关文章

windows信息收集和提权

目录 手动收集 工具收集 windows本地内核提权 本地提权 根据windows去找需要的exp进行利用 提权后结合mimikatz使用 msf提权 简单提权 生成后门 上线 BypassUAC绕过UAC提权 msf带的bypassuac模块可以尝试提权 Bypassuac提权命令操作 提权成功 ​local_exploi…

Xcode数据分析全解:洞察应用性能的密钥

标题:Xcode数据分析全解:洞察应用性能的密钥 在应用开发和优化的过程中,数据分析是提升用户体验和应用性能的关键步骤。Xcode作为苹果官方的集成开发环境,提供了多种工具和集成方案来支持应用的数据分析。本文将详细介绍如何在Xc…

WordPress主题底部纯文本文章列表

如果是RiPro主题,请在后台顶部设置添加自定义CSS。其他主题在对应的CSS样式添加。 CSS代码: /*底部纯文本文章列表*/ .sjblog-list {height: 90px;background: #333;border-radius: 4px 4px 0 0;padding: 24px;margin: -20px -20px 22px -20px;positio…

守护服务之门:Eureka中分布式认证与授权的实现策略

守护服务之门:Eureka中分布式认证与授权的实现策略 引言 在微服务架构中,服务间的通信安全至关重要。Eureka作为Netflix开源的服务发现框架,虽然本身提供了服务注册与发现的功能,但并不直接提供认证与授权机制。为了实现服务的分…

Java面试八股之Redis单线程为什么性能高

Redis单线程为什么性能高 1.内存数据库特性 要点:Redis是一个内存数据库,其数据主要存储在内存中,而非磁盘。内存访问的速度远超磁盘,通常可达纳秒级别,这使得Redis在处理数据时几乎不受I/O瓶颈的影响。由于数据操作…

LeetCode(2)-反转链表、删除链表中等于val的节点、返回链表中的中间节点

一、反转链表 . - 力扣(LeetCode) 解法1: /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListN…

“论基于构件的软件开发方法及其应用”精选范文,软考高级论文,系统架构设计师论文

论文真题 基于构作的软件开发 (Component-Based Software Development,CBSD) 是一种基于分布对象技术、强调通过可复用构件设计与构造软件系统的软件复用途径。基于构件的软件系统中的构件可以是COTS (Commercial-Off-the-Shelf)构件&#x…

C#winfrom窗体开发图书管理系统

一、图书管理系统设计背景 图书馆管理系统是一个关键的信息技术应用,旨在提升图书馆的运营效率和用户的借阅体验。该系统通过数字化手段,实现了图书资源的高效管理和用户服务的便捷化。随着数字化时代的到来,传统的图书馆管理方式已经不能满…

Java实现将图片转换成PDF

1.引入依赖 <dependency><groupId>org.apache.pdfbox</groupId><artifactId>pdfbox</artifactId><version>2.0.24</version> </dependency>2.工具方法 package com.prescription.transfer.system.utils;import org.apache.p…

flutter 列表下拉框加搜索

1.使用控件搜索加下拉框dropdown_search: ^0.4.9和获取中文拼音lpinyin: ^1.1.1 2.加入中文查询和首字查询 在当中找到相应的packages&#xff0c;再在SelectDialog.dart当中加入引入拼音搜索 import package:lpinyin/lpinyin.dart; 更改匹配方法manageItemsByFilter使其可…

R包: phyloseq扩增子统计分析利器

介绍 phyloseq包对多类型数据的综合软件&#xff0c;并其对这些数据提供统计分析和可视化方法。 微生物数据分析的主要挑战之一是如何整合不同类型的数据&#xff0c;从而对其进行生态学、遗传学、系统发育学、多元统计、可视化和检验等分析。同时&#xff0c;由于同行之间需要…

期货量化交易客户端开源教学第九节——新用户注册

一、新用户注册界面设计&#xff1a; 注册时采用手机号注册&#xff0c;客户端发送新号注册申请由后台做审核&#xff0c;后台审核通过后向注册的手机号发送注册成功的消息。注册过的手机号不能再二次注册。 界面验证代码 private{ Private declarations }FVerf: AnsiString; …

【QT】布局管理器

布局管理器 布局管理器1. 垂直布局2. 水平布局3. 网格布局4. 表单布局5. Spacer 布局管理器 之前使⽤ Qt 在界⾯上创建的控件, 都是通过 “绝对定位” 的⽅式来设定的&#xff1b;也就是每个控件所在的位置, 都需要计算坐标, 最终通过 setGeometry 或者 move ⽅式摆放过去。 …

java 前端上传文件后端解析并转发到第三方存储,Hutool 工具

单个文件上传 PostMapping("/upload")public MyResponse<?> upload(MultipartFile file) {if (multipartFiles null || multipartFiles.length 0) {throw new MessageException("未选择文件");}InputStreamResource inputStreamResource new Inp…

实用教程:用 Go 的 net/textproto 包优化文本协议处理

实用教程&#xff1a;用 Go 的 net/textproto 包优化文本协议处理 介绍准备工作环境设置Go 基础回顾 基础使用创建连接发送请求接收响应 高级特性处理 MIME 头多行响应的管理错误处理与调试 实战案例实现一个简单的邮件客户端实现一个基于 net/textproto 的命令行工具 最佳实践…

从零开始开发视频美颜SDK:实现直播美颜效果

因此&#xff0c;开发一款从零开始的视频美颜SDK&#xff0c;不仅可以节省成本&#xff0c;还能根据具体需求进行个性化调整。本文将介绍从零开始开发视频美颜SDK的关键步骤和实现思路。 一、需求分析与技术选型 在开发一款视频美颜SDK之前&#xff0c;首先需要进行详细的需求…

WPF界面设计-更改按钮样式 自定义字体图标

一、下载图标文件 iconfont-阿里巴巴矢量图标库 二、xaml界面代码编辑 文件结构 &#xe653; 对应的图标代码 Fonts/#iconfont 对应文件位置 <Window.Resources><ControlTemplate TargetType"Button" x:Key"CloseButtonTemplate"…

数据结构与算法基础-学习-37-平衡二叉树(Avl树)之删除节点

目录 一、知识点回顾 1、二叉搜索树&#xff08;BST&#xff09; 2、平衡二叉树&#xff08;Avl树&#xff09;之查找 二、环境信息 三、实现思路 1、示例图 2、查询 3、删除 &#xff08;1&#xff09;叶子节点&#xff08;无子树节点&#xff09; &#xff08;2&am…

如何为IP申请SSL证书

目录 以下是如何轻松为IP地址申请SSL证书的详细步骤&#xff1a; 申请IP证书的基本条件&#xff1a; 申请IP SSL证书的方式&#xff1a; 确保网络通信安全的核心要素之一&#xff0c;是有效利用SSL证书来加密数据传输&#xff0c;特别是对于那些直接通过IP地址访问的资源。I…

同步的艺术:Conda包依赖的自动同步策略

同步的艺术&#xff1a;Conda包依赖的自动同步策略 引言 在复杂的软件开发项目中&#xff0c;依赖管理是确保项目顺利进行的关键环节。Conda作为Python和其他科学计算语言的强大包管理器&#xff0c;提供了依赖同步功能&#xff0c;帮助用户自动化和简化依赖项的同步过程。本…