一文教你读懂常见的图遍历算法
- 深度优先搜索（DFS）：
- 从一个起始节点开始，访问该节点并将其标记为已访问。
- 递归地访问所有与当前节点直接相连且未被访问过的节点。
- 重复上述步骤，直到所有节点都被访问过或没有未访问的节点。
- 广度优先搜索（BFS）：
- 从一个起始节点开始，将其放入队列中，并标记为已访问。
- 重复以下步骤直到队列为空：
- 从队列中取出一个节点。
- 访问该节点。
- 将与该节点直接相连且未被访问的节点放入队列中，并标记为已访问。
- Dijkstra算法：
- 创建一个距离数组和一个标记数组，用于存储从起始节点到每个节点的最短距离和是否被访问的标记。
- 初始化距离数组为无穷大，起始节点的距离为0。
- 重复以下步骤直到所有节点都被访问过：
- 选择距离数组中未被访问的节点中距离最小的节点作为当前节点。
- 更新与当前节点直接相连的节点的最短距离，如果新的距离比原来的距离小，则更新距离数组。
- 标记当前节点为已访问。
- Bellman-Ford算法：
- 创建一个距离数组，用于存储从起始节点到每个节点的最短距离。
- 初始化距离数组为无穷大，起始节点的距离为0。
- 重复以下步骤n-1次（n为节点数）：
- 遍历所有边，对每条边进行松弛操作：如果通过该边可以获得更短的路径，则更新距离数组。
- 检查是否存在负权环。如果在第n次迭代中仍然可以松弛边的距离，则存在负权环。
- Floyd-Warshall算法：
- 创建一个二维距离矩阵，用于存储任意两个节点之间的最短距离。
- 初始化距离矩阵，如果两个节点之间存在边，则距离为边的权重，否则为无穷大。
- 重复以下步骤，更新距离矩阵中的值：
- 对于每对节点i和j，遍历所有节点k，如果从i到j经过k的距离更短，则更新距离矩阵中的值。
- 拓扑排序：
- 拓扑排序用于有向无环图（DAG）中的节点排序，使得对于任意两个节点u和v，如果存在从u到v的路径，则u在排序中出现在v之前。
- 进行拓扑排序的方法是使用DFS或BFS。
- 对于DFS拓扑排序：
- 从一个未被访问的节点开始，递归地访问与该节点相连的未被访问的节点。
- 在访问完一个节点的所有相邻节点后，将该节点添加到排序结果的开头。
- 对于BFS拓扑排序：
- 统计每个节点的入度（即有多少条边指向该节点）。
- 将入度为0的节点放入队列中。
- 重复以下步骤直到队列为空：
- 从队列中取出一个节点，将其添加到排序结果中。
- 减少与该节点相邻节点的入度。
- 如果某个节点的入度变为0，则将其加入队列中。
- 强连通分量算法：
- 强连通分量是指有向图中的一组节点，其中任意两个节点都可以相互到达。
- Tarjan算法是一种常用的强连通分量算法。
- Tarjan算法使用DFS遍历图，通过维护一个栈和一个索引值来判断是否存在强连通分量。
- 在进行DFS遍历时，为每个节点分配一个唯一的索引值，并记录每个节点的索引值和最小可达索引值。
- 当遍历到一个节点时，将其压入栈中，并将其索引值和最小可达索引值设置为当前索引值。
- 如果遍历到的节点还没有被访问过，继续递归遍历其相邻节点，并更新最小可达索引值。
- 如果遍历到的节点已经被访问过，且仍在栈中，则将其最小可达索引值与当前节点的索引值进行比较，如果相等，则将栈中的节点弹出，并形成一个强连通分量。
互联网大厂测开经历，目前担任测试开发负责人，每天分享互联网面经，如果你有测试相关的问题，欢迎咨询，海鲜市场【简历优化】、【就业指导】、【模拟/辅导面试】，已辅导20位以上同学拿到心仪offer
简历修改119/次
模拟面试149/小时
测试开发工具指导149/小时
