图论基础知识点

图论基础知识点

引用

CSDN

1.

https://blog.csdn.net/2302_76427329/article/details/146178003

图论是计算机科学和数学中的重要分支，广泛应用于网络分析、电路设计、社交网络分析等领域。本文将从基础概念出发，介绍图的种类、度、连通性、图的构造和遍历等核心知识点，帮助读者快速入门图论。

图的种类

• 有向图：节点之间通过箭头连接，表示方向性。
• 无向图：节点之间通过直线连接，没有方向性。
• 权值：边上的数值，可以理解为连接两个节点所需的消耗或距离。

度

• 无向图：节点的度是指与该节点相连的边的数量总和。
• 有向图：
• 入度：指向该节点的边的数量。
• 出度：从该节点出发的边的数量。

连通性

• 连通图：在无向图中，任意两个节点之间都存在路径，则称该图为连通图，否则为非连通图。
• 强连通图：在有向图中，任意两个节点之间都存在双向路径，则称该图为强连通图。
• 连通分量：在无向图中，极大连通子图称为该图的一个连通分量。
• 强连通分量：在有向图中，极大强连通子图称为该图的一个强连通分量。

上图中，节点123与节点34分别是一个连通分量。需要注意的是，连通分量必须是极大连通图，节点12构成的子图不能作为一个连通分量。

上图中，节点678不是强连通分量，因为8不能到达7。

图的构造

• 朴素存储：使用n * 2大小的数组存储节点连接方式，但需要遍历整个数组才能检查两个节点是否相连。
• 邻接矩阵：使用n * n大小的数组，检查任意两个顶点间是否存在边的操作非常快，适合稠密图，但在稀疏图中会浪费空间。
• 邻接表：根据边的数量来存储图，空间利用率高，适合稀疏图，但检查任意两个节点间是否存在边的效率相对较低。

图的遍历

• 深度优先搜索（DFS）：从一个节点出发，尽可能深地搜索图的分支，直到无法继续为止，然后回溯。
• 广度优先搜索（BFS）：从一个节点出发，逐层遍历图的节点，直到所有可达节点都被访问。

这两种搜索算法不仅适用于图，也可以在其他数据结构（如二叉树）上进行搜索。