图的基本概念
673 字
3 分钟
图的基本概念
图的分类
有向图
· 定义：图中的边有方向性，用箭头表示。 · 表示：边 (A, B) 与 (B, A) 是两条不同的边。
无向图
· 定义：图中的边没有方向。 · 表示：边 (A, B) 与 (B, A) 是同一条边。 · 转换：可以将无向图中的一条边看作两条方向相反的有向边。
图的特殊结构
自环
· 定义：一条边从某个顶点出发，并指向其自身。
重边
· 定义：两个顶点之间存在两条或两条以上完全相同的边（在有向图中要求方向也相同）。
稠密图 vs 稀疏图
· 稀疏图：边数远少于顶点数的平方（|E| << |V|²），即“少边多点”。 · 稠密图：边数接近顶点数的平方（|E| ≈ |V|²），即“多边少点”。 · 这是一个相对概念，没有绝对的界限。
顶点与路径
顶点的度
· 无向图：与该顶点相关联的边的总数。 · 有向图： · 入度：指向该顶点的边的数目。 · 出度：从该顶点指出的边的数目。
路径
· 定义：一个顶点序列，其中每相邻两个顶点之间都存在一条边。 · 回路/环：路径的起点和终点是同一个顶点。
路径长度
· 无权图：路径上经过的边的数量。 · 带权图：路径上所有边的权值之和。
连通性
连通图与连通分量
· 连通图：在无向图中，如果任意两个顶点之间都存在路径，则该图称为连通图。 · 非连通图：不是连通图的无向图。 · 重要性质：一个有 n 个顶点的图，如果边数小于 n-1，则它一定是非连通图。 · 连通分量：无向图中的极大连通子图。 · “极大”意味着：再也找不到另一个包含该子图且比它更大的连通子图。 · 一个图可以有多个连通分量。
连通分量数的计算
· 对于一个有 n 个顶点、m 条边且无环的森林结构，其连通分量数可以通过以下公式计算： 连通分量数 = n - m
生成树
· 定义：一个连通图的生成树是包含其全部顶点的极小连通子图。 · 性质：
- 包含原图所有 n 个顶点。
- 只有 n-1 条边。
- 是连通的，并且无环。 · 关键特性： · 极小性：在生成树中移除任意一条边都会导致图变得不连通。 · 在生成树中添加任意一条边都会形成一个回路。
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章智能推荐
1
最小生成树
算法最小生成树：在连通带权无向图中，找到一个边权和最小的生成树
2
拓扑排序
算法定义：在有向图中，顶点表示活动，有向边表示活动Vi必须先于活动Vj进行 特性：必须是有向无环图
3
单源最短路
算法每次从未确定最短路径的点中，选择距离起点最近的点，标记它的最短路径，并用它来更新邻居节点的距离。
4
算法错题本
算法在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
5
数论
算法如果 $a$ 除以 $b$ 没有余数，那么 $a$ 就是 $b$ 的倍数，$b$ 就是 $a$ 的约数，记作 $b \mid a$。 约数，也称因数。
随机文章随机推荐