文章目录
- 图
🏡作者主页：点击！
🤖数据结构专栏：点击！
⏰️创作时间：2024年12月23日19点21分
图
任何一条边两头肯定都必须连接某个顶点
线性表可以是空表，树可以是空树，但图不可以是空，即 V 一定是非空集
简单图：
- 不存在重复边
- 不存在顶点到自身的边
默认探讨简单图
有向图和无向图
对于无向图：顶点的 v 的度是指依附于该顶点的边的条数，记为 TD(v)
对于有向图：入度是以顶点 v 为终点的有向边的数目，记为 ID(v)。出度是以顶点 v 为起点的有向边的数目，记为 OD(v)
顶点的度等于其入度和出度之和
回路：第一个顶点和最后一个顶点相同的路径称为回路或环
简单路径：路径序列中，顶点不重复出现的路径称为简单路径
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路
路径长度：路径上边的数目
点到点的距离：如一点到某一点之间最短路径存在，则此路径的长度称为一点到某一点的距离，若两点之间不存在路径，则记该距离为无穷
无向图中：两顶点之间单向有路径存在，则称两顶点是连通的
有向图中，两顶点之间双向有路径存在，则称两顶点是强连通
连通图是无向的（任意两个顶点都是连通的，否则称为非连通图）
#连通图，最少n-1条边 #非连通图，最多可能有 C^2n-1条边强连通图是有向的（图中任何一对顶点都是强连通的，则称此图为强连通图）
#对于n个顶点的有向图G #强连通图，则最少有n条边
连通分量
无向图中的极大连通子图称为连通分量（子图必须连通，且包含尽可能多的顶点和边）
强连通分量
有向图中的极大强连通子图称为有向图的强连通分量
生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图
n个顶点n-1条边
生成森林
在非连通图中，连通分量的生成树构成了非连通图的生成森林
边的权、带权图/网
边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值
带权图/网：边上带有权值的图称为带权图，也称网
带权路径长度：当图是带权图时，一条路径上所有便边的权值之和称为该路径的带权路径长度
无向完全图：无向图中任意两个顶点之间都存在边 n个顶点，Cn^2
有向完全图：有向图中任意两个顶点之间都存在相反的两条弧
边数很少的图称为稀疏图
反之称为稠密图
（无向树）树----不存在回路，且连通的无向图（n个顶点的树，必有 n-1 条边）
（有向树，一个顶点的入读为 0，其余顶点的入度均为 1 的有向图，称为有向树）