- 博客主页：誓则盟约
- 系列专栏：IT竞赛 专栏
- 关注博主，后期持续更新系列文章
- 如果有错误感谢请大家批评指出，及时修改
- 感谢大家点赞👍收藏⭐评论✍
-
图的定义和基本概念：
-
图（Graph）是一种由顶点（Vertex，也称为节点 Node）和边（Edge）组成的数据结构。
顶点是图中的基本元素，表示某个对象或实体。顶点可以用一个标识符来表示，例如一个数字或一个字符串。
边则用于连接图中的顶点，表示顶点之间的关系。边可以是有向的，也可以是无向的。
在无向图中，边没有方向，顶点之间的连接是双向的。如果顶点
v和顶点w之间有一条无向边，那么我们可以说v和w是相邻的，并且从v可以到达w，从w也可以到达v。在有向图中，边是有方向的，从一个顶点指向另一个顶点。如果有一条从顶点
u到顶点v的有向边，我们表示为(u, v)，那么可以说u是v的前驱，v是u的后继。从u可以沿着边到达v，但从v不一定能直接到达u，除非存在另一条从v到u的有向边。
-
有向图（Directed Graph）和无向图（Undirected Graph）是图的两种主要类型，它们的主要区别在于边的方向性：
无向图：
- 边的特征：在无向图中，边没有方向，顶点之间的连接是双向的。如果存在一条连接顶点
u和顶点v的边，那么既可以从u到达v，也可以从v到达u。 - 表示方法：通常用一对顶点来表示一条边，例如
(u, v)表示顶点u和顶点v之间有一条边。由于边是无向的，所以(u, v)和(v, u)表示的是同一条边。 - 应用场景：适用于表示顶点之间对称的关系，比如朋友关系（如果 A 是 B 的朋友，那么 B 也是 A 的朋友）。
-
有向图：
- 边的特征：在有向图中，边是有方向的，从一个顶点指向另一个顶点。如果存在一条从顶点
u到顶点v的有向边，那么只能从u沿着边的方向到达v，而不能从v沿着这条边到达u，除非存在另一条从v到u的有向边。 - 表示方法：用一个有序对来表示一条有向边，例如
(u, v)表示从顶点u到顶点v的有向边，与(v, u)是不同的边。 - 应用场景：常用于表示具有方向性的关系，比如网页中的链接（从一个网页指向另一个网页）、任务之间的依赖关系（一个任务必须在另一个任务完成后才能开始）等。
图的表示方法：
- 邻接矩阵是用一个二维矩阵来表示图的连接关系。矩阵的行和列都对应图的顶点。若顶点和顶点之间有边相连，矩阵中的值为（或边的权值），否则为。这种表示法简单直观，适用于顶点数较少的图。
-
邻接表是一种用于表示图的常见数据结构。对于图中的每个顶点，使用一个链表或数组来存储与其相邻的顶点。
具体来说，为图中的每个顶点创建一个链表（或动态数组）。链表（或数组）中的每个节点表示与该顶点相邻的一个顶点，并可以选择性地包含边的权值等信息。
图的遍历算法：
深度优先搜索（Depth-First Search，DFS）是一种图（或者树）的遍历算法。它从起始节点开始，沿着一条路径尽可能深地访问节点，直到无法继续或达到目标节点，然后回溯到上一个未完全探索的节点，继续探索其他路径。
DFS 的原理：
- 选择一个起始节点并将其标记为已访问。
- 对于该节点的未访问相邻节点，选择一个进行递归访问。
- 重复上述过程，直到没有未访问的相邻节点，然后回溯。
DFS 的实现步骤：
- 访问起始节点，并将其标记为已访问。
- 对于起始节点的每个未访问相邻节点，进行递归的 DFS 调用。
- 当一个节点的所有相邻节点都已被访问，回溯到上一个节点，继续探索其他未访问的相邻节点。
以下是使用 Python 实现 DFS 的代码示例：
# 定义一个图（以邻接表的形式表示）
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': [],
'F': []
}
# 用于标记已访问的节点
visited = set()
def dfs(node):
if node in visited:
return
visited.add(node)
print(node)
for neighbor in graph[node]:
dfs(neighbor)
# 选择一个起始节点，例如 'A'
dfs('A')
