图论1基础内容

server/2024/11/28 19:25:05/

1.  图的定义和术语

1.1 生活中的图

1.2 图的定义和术语

图由点和边连接组成,一些复杂的图中点和边会有相应的权值

1.2.1符号定义:G = (V,E)

节点集合V,其中的元素称为节点或者顶点

边集合E,其中的元素称为边

1.2.2 有向图和无向图

有向图中,一个点到另一个点的边指向性是单一的,例如A->B表示A有一条可以通向B的路,但不代表B也有一条可以通向A的路;无向图则表示AB互通

1.3 完全图、稀疏图和稠密图
1.3.1完全图:

有向完全图:任意两个顶点都有方向相反的有向边

无向完全图:任意两点都有边相连

1.3.2 稀疏图:

假设一幅图有n个节点m条边,当 m<nlog2n,即边的数量远小于节点的数量的图

1.3.3 稠密图:

假设一幅图有n个节点m条边,当 m>nlog2n,即边的数量远大于节点的数量的图

1.4 子图

对于一幅图G = (V,E),若有另一幅图G' = (V',E'),当V包含V'、E包含E'时,G'是G的子图,可以用集合来理解G={1,2,3,4},G'={3,4}

1.5 邻接点

在图(有向图、无向图)中,若节点a和节点b是边e的两个端点,则a和b是邻接的,边e关联与点a和点b

1.6 度、入度和出度
1.6.1 对于无向图,只有度的概念

在无向图中,一个节点的度是指与该节点直接相连的边的数量。这个度量反映了节点的连接强度。

1.6.2 对于有向图则有入度和出度的概念

入度:在有向图中,一个节点的入度是指从其他节点指向该节点的边的数量。这反映了有多少其他节点指向该节点。

出度:相应地,一个节点的出度是指从该节点指向其他节点的边的数量。这反映了该节点对其他节点的控制或影响程度。

图中,OD代表出度、ID代表入度

1.7 权值与网

图中两个节点之间的边带上一个有意义的数,称为边的权值,即边权

1.8 路径与回路

图中V1V4的长度是8;V1V4V3V2V5的长度是两相邻的点之间边权的顺序和8+2+3+5=18

V0V1V2V3V4是一条简单路径

V0V1V5是一条简单回路

1.9 连通图

G1是无向图,容易两点均有边连接,即可到达,是连通图

G2中有三个独立的连通块,极大连通子图并不是最大连通子图,G2中有3个连通分量

1.10 生成树

生成树指的是连通图中的极小连通子图

每两个点之间都存在一条可达到路径,如果有边权则生成树是原图边权之和最小的子图

2.  图的储存结构

2.1 数组表示法(邻接矩阵)

2.1.1不带权简单图的邻接矩阵

2.1.2带权简单图的邻接矩阵

2.2 邻接表
2.2.1不带权邻接表

2.2.2带权邻接表

3.  图的遍历

对于遍历要求把一个图所有节点不重复不遗漏访问一次

不重复图中可能存在环路访问顶点避免重复访问

不遗漏

按照一定次序进行访问比如接下来提到两种方法深度优先搜索DFS广度优先搜索BFS

保证不连通图各个顶点访问(遍历的过程存在回退的情况)

3.1 深度优先搜索DFS

DFS基于数据结构去实现,尽可能一条路走到底,如果还没完成全图的遍历再回退,然后选择可行路径继续走

对于这个图要求使用DFS,从V1出发优先访问序号顶点访问全图

遍历过程:V1 V2 V4 V5 V6 V3 V7 V8(V9还没有访问,进行回退。回退到V7 V3 V6 V5此时V5与V9连通) V9

3.2 广度优先搜索 BFS

BFS基于队列数据结构实现python通常使用优先队列遍历时先把起点加入队列然后找寻当前连通距离最近继续加入队列直到跑完全图

遍历策略

4.  图的应用

4.1 拓扑排序

拓扑排序针对有向无环图的顶点进行线性排列的算法,使得对于任何来自顶点A指向顶点B的边,A都在序列中出现在B之前。这样的排序存在于向无环图中,而对于非向无环图则不存在拓扑排序。

拓扑排序也可以用来检测图中有无

4.2 最小生成树

生成树连通图极小连通子图多一条就会成环少一条无法构成连通图

生成树的代价

G=(V,E)是一个无向连通代价生成树各边边权

生成树代价=9+49+11+1+21=91

最小生成树代价最小生成树

上图代价min=1+7+10+7+5=30

4.3 最短路问题

最短路径两个顶点之间经历边权之和最小的可达路径

4.3.1 Floyed

用于处理多源最短路多个出发一个点最短路,可以存在负权边

4.3.2 Dijkstra

用于处理源最短路出发一个点最短不可以存在负权边


http://www.ppmy.cn/server/145702.html

相关文章

Linux——用户级缓存区及模拟实现fopen、fweite、fclose

linux基础io重定向-CSDN博客 文章目录 目录 文章目录 什么是缓冲区 为什么要有缓冲区 二、编写自己的fopen、fwrite、fclose 1.引入函数 2、引入FILE 3.模拟封装 1、fopen 2、fwrite 3、fclose 4、fflush 总结 前言 用快递站讲述缓冲区 收件区&#xff08;类比输…

Flink CDC 使用实践以及遇到的问题

背景 最近公司在做一些业务上的架构调整&#xff0c;有一部分是数据从mysql采集到Starrocks&#xff0c;之前的一套方法是走 debezium 到 puslar 到 starrocks,这一套下来比较需要配置很多东西&#xff0c;而且出现问题以后&#xff0c;需要修改很多配置&#xff0c;而且现阶段…

基于SpringBoot的数据结构系统设计与实现(源码+定制+开发)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

单片机_简单AI模型训练与部署__从0到0.9

IDE&#xff1a; CLion MCU&#xff1a; STM32F407VET6 一、导向 以求知为导向&#xff0c;从问题到寻求问题解决的方法&#xff0c;以兴趣驱动学习。 虽从0&#xff0c;但不到1&#xff0c;剩下的那一小步将由你迈出。本篇主要目的是体验完整的一次简单AI模型部署流程&#x…

构建英语知识网站:Spring Boot框架解析

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…

HTML飞舞的爱心

目录 系列文章 写在前面 完整代码 代码分析 写在后面 系列文章 序号目录1HTML满屏跳动的爱心&#xff08;可写字&#xff09;2HTML五彩缤纷的爱心3HTML满屏漂浮爱心4HTML情人节快乐5HTML蓝色爱心射线6HTML跳动的爱心&#xff08;简易版&#xff09;7HTML粒子爱心8HTML蓝色…

【算法 python A*算法的实现】

- 算法实现&#xff1a; import heapqclass Node:def __init__(self, position, g0, h0):self.position position # 节点的位置self.g g # 从起点到当前节点的成本self.h h # 从当前节点到终点的启发式估计成本self.f g h # 总成本self.parent None # 父节点def __…

开发需求总结19-vue 根据后端返回一年的数据,过滤出符合条件数据

需求描述&#xff1a; 定义时间分界点&#xff1a;每月26号8点&#xff0c;过了26号8点则过滤出data数组中符合条件数据下个月的数据&#xff0c;否则过滤出当月数据 1.假如现在是2024年11月14日&#xff0c;那么过滤出data数组中日期都是2024-11月的数据&#xff1b; 2.假如…