408数据结构-图的基本概念 自学知识点整理

*第六章个人感觉是最难的,请各位抓稳扶手,系好安全带。


图的定义

通俗来讲,一个图由一些点和连接这些点的若干边组成,边的两头必须都有顶点,否则不是图。
注:G: GraphV: VertexE: Edge
对图 G G G,其由顶点集 V V V和边集 E E E组成,记为 G = ( V , E ) G=(V,E) G=(V,E),其中 V ( G ) V(G) V(G)表示图 G G G中顶点的有限非空集; E ( G ) E(G) E(G)表示图 G G G中顶点之间的关系(边)集合。若 V = { v 1 , v 2 , ⋯   , v n } V=\left\{ {{v}_{1}},{{v}_{2}},\cdots ,{{v}_{n}} \right\} V={v1,v2,,vn},则用 ∣ V ∣ \left| V \right| V表示图 G G G中顶点的个数, E = { ( u , v ) ∣ u ∈ V , v ∈ V } E=\left\{ \left( u,v \right)\left| u\in V,v\in V \right. \right\} E={(u,v)uV,vV},用 ∣ E ∣ \left| E \right| E表示图 G G G中边的条数。

注意:线性表可以是空表,树也可以是空树,但是图不可以是空图。这意味着,图中不能一个顶点也没有,图的顶点集 V V V一定非空,但边集 E E E可以为空,此时图中只有顶点而没有边。

图的基本概念及术语

有向图、无向图

E E E有向边(也称)的有限集合,则称图 G G G为有向图。
弧是顶点的有序对,记为 ⟨ v , w ⟩ \left\langle v,w \right\rangle v,w,其中 v , w v,w v,w是顶点, v v v称为弧尾 w w w称为弧头 ⟨ v , w ⟩ \left\langle v,w \right\rangle v,w称为从 v v v w w w的弧,也称 v v v邻接到 w w w。( ⟨ v , w ⟩ ≠ ⟨ w , v ⟩ \left\langle v,w \right\rangle \ne \left\langle w,v \right\rangle v,w=w,v

如图6.1(a)中,有向图 G 1 G_1 G1可表示为:
G 1 = ( V 1 , E 1 ) {{G}_{1}}=\left( {{V}_{1}},{{E}_{1}} \right) G1=(V1,E1)
V 1 = { 1 , 2 , 3 } {{V}_{1}}=\left\{ 1,2,3 \right\} V1={1,2,3}
E 1 = { ⟨ 1 , 2 ⟩ , ⟨ 2 , 1 ⟩ , ⟨ 2 , 3 ⟩ } {{E}_{1}}=\left\{ \left\langle 1,2 \right\rangle ,\left\langle 2,1 \right\rangle ,\left\langle 2,3 \right\rangle \right\} E1={1,2,2,1,2,3}

E E E无向边(也称)的有限集合,则称图 G G G为无向图。
边是顶点的无序对,记为 ( v , w ) \left( v,w \right) (v,w) ( w , v ) \left( w,v \right) (w,v)。可以说 w w w v v v互为邻接点。边 ( v , w ) \left( v,w \right) (v,w)依附于 w w w v v v,或称边 ( v , w ) \left( v,w \right) (v,w) v , w v,w v,w相关联。( ( v , w ) = ( w , v ) \left( v,w \right) = \left( w,v \right) (v,w)=(w,v)

如图6.1(b)中,无向图 G 2 G_2 G2可表示为:
G 2 = ( V 2 , E 2 ) {{G}_{2}}=\left( {{V}_{2}},{{E}_{2}} \right) G2=(V2,E2)
V 2 = { 1 , 2 , 3 , 4 } {{V}_{2}}=\left\{ 1,2,3,4 \right\} V2={1,2,3,4}
E 2 = { ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) } {{E}_{2}}=\left\{ \left( 1,2 \right),\left( 1,3 \right),\left( 1,4 \right),\left( 2,3 \right),\left( 2,4 \right),\left( 3,4 \right) \right\} E2={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

无向与有向可以类比标量与向量进行理解。比如从 v v v w w w有一条弧 ⟨ v , w ⟩ \left\langle v,w \right\rangle v,w,就可以认为有一条有向线段从 v v v指向 w w w
(图片来自王道考研408数据结构2025)
图片来自王道考研408数据结构2025

简单图、多重图

对一个图 G G G,若其满足:①不存在重复边;②不存在顶点到自身的边。则称图 G G G简单图。上图6.1中的图 G 1 G_1 G1和图 G 2 G_2 G2均为简单图。
若图 G G G中某两个顶点之间的边数大于 1 1 1条,又或者允许顶点通过一条边与自身关联,则称图 G G G多重图
多重图和简单图的定义是相对的。(408初试数据结构考察简单图!!!)
之后讨论的所有图只有简单图,多重图只需了解其概念即可。

顶点的度、入度和出度

对于无向图,顶点 v v v的度是指依附于顶点 v v v的边的条数,记为 T D ( v ) TD(v) TD(v)无向图的全部顶点的度之和等于边数的 2 2 2,因为每条边和两个顶点相关联。
n n n个顶点、 e e e条边的无向图中, ∑ i = 1 n T D ( v i ) = 2 ∣ E ∣ \sum\limits_{i=1}^{n}{TD\left( {{v}_{i}} \right)}=2\left| E \right| i=1nTD(vi)=2E
在图6.1(b)中,每个顶点的度均为 3 3 3

对于有向图,顶点 v v v的度分为入度和出度,入度是以顶点 v v v为重点的有向边的数目,记为 I D ( v ) ID(v) ID(v)出度是以顶点 v v v为重点的有向边的数目,记为 O D ( v ) OD(v) OD(v)。顶点 v v v的度等于其入度与出度之和,即 T D ( v ) = I D ( v ) + O D ( v ) TD(v)=ID(v)+OD(v) TD(v)=ID(v)+OD(v)有向图的全部顶点的入度之和与出度之和相等,并且等于边数,这是因为有向图中每条弧都为一个顶点贡献一个入度,为一个顶点贡献一个出度(每条边都有一个唯一起点和终点)。
n n n个顶点、 e e e条边的有向图中, ∑ i = 1 n I D ( v i ) = ∑ i = 1 n O D ( v i ) = e \sum\limits_{i=1}^{n}{ID\left( {{v}_{i}} \right)}=\sum\limits_{i=1}^{n}{OD\left( {{v}_{i}} \right)}=e i=1nID(vi)=i=1nOD(vi)=e
在图6.1(a)中,顶点 2 2 2的出度为 2 2 2、入度为 1 1 1

顶点-顶点的关系描述

  • 路径:顶点 v p v_p vp到顶点 v q v_q vq之间的一条路径是指顶点序列 v p , v i 1 , v i 2 , ⋯   , v i m , v q {{v}_{p}},{{v}_{{{i}_{1}}}},{{v}_{{{i}_{2}}}},\cdots ,{{v}_{{{i}_{m}}}},{{v}_{q}} vp,vi1,vi2,,vim,vq。当然,关联的边也可理解为路径的构成要素。
  • 回路:第一个顶点和最后一个顶点相同的路径被称为回路或
  • 简单路径:在路径序列中,顶点不重复出现的路径称为简单路径。
  • 简单回路:除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路。
  • 路径长度:路径上的边的数目称为路径长度。
  • (点到点的)距离:从顶点 u u u出发到顶点 v v v的最短路径若存在,则此路径的长度称为从 u u u v v v的距离。若从 u u u v v v根本不存在路径,则记该距离为无穷( ∞ ∞ )。

连通、连通图

无向图中,若从顶点 v v v到顶点 w w w有路径存在,则称 v v v w w w连通的。若图 G G G中任意两个顶点都是连通的,则称图 G G G连通图,否则为非连通图
对于 n n n个顶点的无向图 G G G:若 G G G是连通图,则最少有 n − 1 n-1 n1条边;若 G G G是非连通图,则最多可能有 C n − 1 2 C_{n-1}^{2} Cn12条边。

有向图中,若有一对顶点 v v v w w w,从 v v v w w w w w w v v v之间都有有路径存在,则称 v v v w w w这两个顶点是强连通的。若图中任意一对顶点都是强连通的,则称此图为强连通图
对于 n n n个顶点的有向图 G G G:若 G G G是强连通图,则最少有 n n n条边(形成回路)。

注意:在无向图中讨论连通性,在有向图中讨论强连通性

子图

设有两个图 G ( V , E ) G\left( V,E \right) G(V,E) G ′ ( V ′ , E ′ ) {{G}^{'}}\left( {{V}^{'}},{{E}^{'}} \right) G(V,E),若 V ′ {{V}^{'}} V V V V的子集,且 E ′ {{E}^{'}} E E E E的子集,则称 G ′ {{G}^{'}} G G G G子图
(注意:挑选出来的点子集和边子集构成的新图必须满足“图的定义”,否则不是子图,图都不是)
若有满足 V ( G ′ ) = V ( G ) V\left( {{G}^{'}} \right)=V\left( G \right) V(G)=V(G)的子图 G ′ {{G}^{'}} G,则称其为 G G G生成子图

连通分量

无向图中的极大连通子图称为连通分量
其中,“极大连通子图”的含义是:子图必须连通,在此基础上,包含尽可能多的顶点和边
(图片来自王道考研408数据结构2025)
图片来自王道考研408数据结构2025
有向图中的极大强连通子图称为强连通分量
其中,“极大强连通子图”的含义是:子图必须强连通,在此基础上,保留尽可能多的
(图片来自王道考研408数据结构2025)
图片来自王道考研408数据结构2025

生成树、生成森林

连通图的生成树包含图中全部顶点的一个极小连通子图
极小连通子图的含义是:子图要保持连通,在此基础上,包含尽可能少的边。
若一个连通图有 n n n个顶点,则它的生成树含有 n − 1 n-1 n1条边。构造生成树的方式并不唯一。对生成树而言,若砍去它的一条边,则会变成非连通图;若加上一条边,则会形成一个回路(环)。

在非连通图中,连通分量的生成树构成了非连通图的生成森林
也就是说,对非连通图,其所有的极大连通子图的生成树的集合,构成这个非连通图的生成森林。
(知识点回顾:树与森林)

注意:区分极大连通子图和极小连通子图。极大连通子图要求子图必须连通,而且包含尽可能多的顶点和边;极小连通子图是既要保持子图连通又要使得边数最少的子图。

边的权、带权图/网

  • 边的权:在一个图中,每条边都可以标上具有某种含义的数值,该数值称为该边的权值
  • 带权图/网:边上带有权值的图称为带权图,也称
  • 带权路径长度:当图是带权图时,一条路径上所有边的权值之和,称为该路径的带权路径长度

几种特殊形态的图

  • 无向完全图:对一个无向图,若其任意两个顶点之间都存在边,则称这样的无向图为无向完全图。容易得到,对一个顶点数为 n n n的无向完全图,其边的数量为 C n 2 C_{n}^{2} Cn2
  • 有向完全图:对一个有向图,若其任意两个顶点之间都存在方向相反的两条弧,则称这样的有向图为有向完全图。若一个有向完全图有 n n n个顶点,则其边数为 2 C n 2 2C_{n}^{2} 2Cn2 n ( n − 1 ) n(n-1) n(n1)
  • 稀疏图稠密图:边数很少的图称为稀疏图,反之称为稠密图。稀疏和稠密本身是模糊的概念,没有绝对的界限,稀疏图和稠密图常常是相对而言的。一般来说,当图 G G G满足 ∣ E ∣ < ∣ V ∣ log ⁡ ∣ V ∣ \left| E \right|<\left| V \right|\log \left| V \right| E<VlogV时,可以将 G G G视为稀疏图。当然这个定义也不绝对,作了解即可。
  • 不存在回路,且连通无向图 n n n个顶点的树,必有 n − 1 n-1 n1条边。森林中各个子图是极小且连通的。
    n n n个顶点的图中有大于 n − 1 n-1 n1条的边,则其中一定有回路。
  • 有向树:一个顶点的入度为 0 0 0、其余顶点的入度均为 1 1 1有向图,称为有向树。这个入度为 0 0 0的顶点可以视为树中的根结点。需要注意的是,树是连通图,但有向树并不是强连通图。

这些基本概念需要结合课后习题熟记于心,不然后续内容会难以理解。
虽然都是些八股文,但还是得努努力背下来,要理解到位才行。下一篇博客应该会开始上代码。
以上。

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

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

相关文章

Hive安装教程

前置条件:hadoop&mysql docker容器安装mysql-CSDN博客 以下的/opt/bigdata目录根据自己实际情况更改 1.上传hive包并解压 tar -zxvf apache-hive-3.1.3-bin.tar.gz -C /opt/bigdata/ 2.修改路径 mv /opt/bigdata/apache-hive-3.1.3-bin/ hive cd /opt/bigdata/hive/…

螺旋矩阵的思想

方阵类型 https://leetcode.cn/problems/spiral-matrix-ii/ lc59: 螺旋矩阵&#xff0c; 解题思路 关键点&#xff1a; 上方&#xff0c; 从左到右&#xff1b; 右侧&#xff0c;从上到下&#xff1b; 下方&#xff0c;从右到左&#xff1b; 左侧&#xff0c; 从下往上&…

加密与解密(第四版)】第二十五章笔记

第二十五章 数据取证技术 25.1 硬盘数据的获取和固定 取证专用的Linux可启动光盘 硬盘复制机 利用取证计算机复制硬盘 手机&#xff08;JTAG&#xff09; 电子数据的固定&#xff08;HASH值&#xff09; 25.2 硬盘的分区和数据恢复 25.3 内存分析 25.4 动态仿真技术 25.…

SpringBoot——整合Thymeleaf模板

目录 模板引擎 新建一个SpringBoot项目 pom.xml application.properties Book BookController bookList.html ​编辑 项目总结 模板引擎 模板引擎是为了用户界面与业务数据分离而产生的&#xff0c;可以生成特定格式的页面在Java中&#xff0c;主要的模板引擎有JSP&…

探索Python编程世界:从基础到实战

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 一、Python语言简介与动态特性 代码示例&#xff1a;动态类型与变量命名 二、Python应用领…

【软件设计师】大题

一、数据流图 基础知识 数据流图&#xff08;Data Flow Diagram,DFD&#xff09;基本图形元素&#xff1a; 外部实体&#xff08;External Agent&#xff09; 表示存在于系统之外的对象&#xff0c;用来帮助用户理解系统数据的来源和去向加工&#xff08;Process&#xff09;数…

犀牛8 for Mac/Win:重塑三维建模的新标杆

在数字创意的浪潮中&#xff0c;犀牛8&#xff08;Rhinoceros 8&#xff09;作为一款卓越的三维建模软件&#xff0c;以其强大的功能和出色的性能&#xff0c;在Mac和Windows平台上都赢得了广大设计师和工程师的青睐。 犀牛8不仅继承了前代产品的优秀基因&#xff0c;更在细节…

从 0 开始本地部署大语言模型

1、准备 ● Ollama&#xff1a;ollama.com ● Docker&#xff1a;https://docs.openwebui.com/ 2、下载 Ollama 进入 Ollama 官网&#xff0c;点击 Download 。 下载完成后&#xff0c;双击安装&#xff0c;什么都不需要勾选&#xff0c;直接下一步即可。安装完成&#xf…

[读论文]精读Self-Attentive Sequential Recommendation

论文链接&#xff1a;https://arxiv.org/abs/1808.09781 其他解读文章&#xff1a;https://mp.weixin.qq.com/s/cRQi3FBi9OMdO7imK2Y4Ew 摘要 顺序动态是许多现代推荐系统的一个关键特征&#xff0c;这些系统试图根据用户最近执行的操作来捕获用户活动的“上下文”。为了捕捉…

Hive运行错误

Hive 文章目录 Hive错误日志错误SessionHiveMetaStoreClientql.Driver: FAILED: Execution Error, return code 2 from org.apache.hadoop.hive.ql.exec.mr.MapRedTaskerror: Could not find or load main class org.apache.hadoop.mapreduce.v2.app.MRAppMaster Please check …

GIT 新建分支和合并分支

文章目录 前言一、新建分支二、切回老分支&#xff0c;保留新分支的更改三、合并分支 前言 本文主要针对以下场景进行介绍&#xff1a; 场景一&#xff1a;创建新的分支 当前分支(dev_1)已经开发完毕&#xff0c;下一期的需求需要在新分支(dev_2)上进行开发&#xff0c;如何创…

每日5题Day8 - LeetCode 36 - 40

每一步向前都是向自己的梦想更近一步&#xff0c;坚持不懈&#xff0c;勇往直前&#xff01; 第一题&#xff1a;36. 有效的数独 - 力扣&#xff08;LeetCode&#xff09; 题目要求我们进行判断&#xff0c;我们不需要自己填写&#xff0c;所以要一个标志位&#xff0c;来看当…

LLM——探索大语言模型在心理学方面的应用研究

1. 概述 心理学经历了多次理论变革&#xff0c;目前人工智能&#xff08;AI&#xff09;和机器学习&#xff0c;特别是大型语言模型&#xff08;LLMs&#xff09;的使用&#xff0c;预示着新研究方向的开启。本文详细探讨了像ChatGPT这样的LLMs如何转变心理学研究。它讨论了LL…

从旅游广告联想到《桃花源记》

近日收到《长江头条网》等知名网络自媒体相邀,促我写点儿旅游题材的文案。虽说笔者游历过许多名山大川的绝美风景区,但那是在70岁之前的事儿了。如今年逾78岁,纵使有少许自有资本能够支持出游,可体力难撑,岂不是花钱买罪受吗?而且,写没有亲身经历过的事挺难,即便发表出…

台灯的功能作用有哪些?护眼台灯真的护眼吗?

现在的学生会长时间使用平板、手机、电脑等&#xff0c;这些设备的屏幕会产生一定的频闪和蓝光辐射&#xff0c;也就会影响视力健康&#xff0c;而护眼养眼也成了家长关注的问题&#xff0c;视力疲劳和眼部疾病不仅影响个体的生活质量&#xff0c;还可能导致长期的健康问题。当…

装修:尽显个性品味

家&#xff0c;是心灵的港湾&#xff0c;也是生活的舞台。装修&#xff0c;不仅是对空间的改造&#xff0c;更是对生活态度的诠释。无论是温馨的北欧风&#xff0c;还是华丽的欧式古典&#xff0c;或是简约的现代感&#xff0c;我们的专业团队都能为您量身打造。每一个细节&…

力扣--哈希表13.罗马数字转整数

首先我们可以知道&#xff0c;一个整数&#xff0c;最多由2个罗马数字组成。 思路分析 这个方法能够正确将罗马数字转换为阿拉伯数字的原因在于它遵循了罗马数字的规则&#xff0c;并且对这些规则进行了正确的编码和处理。 罗马数字规则 罗马数字由以下字符组成&#xff1a…

如何使用ffmpeg 实现10种特效

相关特效的名字 特效id 特效名 1 向上移动 2 向左移动 3 向下移动 4 颤抖 5 摇摆 6 雨刷 7 弹入 8 弹簧 9 轻微跳动 10 跳动 特效展示(同时汇总相关命令) pad背景显示 pad背景透明 相关命令(一会再讲这些命令&#xff0c;先往下看) # 合成特效语音 ffmpeg -y -loglevel erro…

Pandas高效数据清洗与转换技巧指南【数据预处理】

三、数据处理 1.合并数据&#xff08;join、merge、concat函数&#xff0c;append函数&#xff09; Concat()函数使用 1.concat操作可以将两个pandas表在垂直方向上进行粘合或者堆叠。 join属性为outer&#xff0c;或默认时&#xff0c;返回列名并集&#xff0c;如&#xff…

day34 贪心算法 455.分发饼干 376. 摆动序列

贪心算法理论基础 贪心的本质是选择每一阶段的局部最优&#xff0c;从而达到全局最优。 贪心一般解题步骤&#xff08;贪心无套路&#xff09;&#xff1a; 将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解 455.分发饼干 …