什么是强连通分量 (SCC)？

在有向图中，如果两个顶点 u 和 v 能相互到达（即存在从 u 到 v 的路径，也存在从 v 到 u 的路径），则称这两个顶点是强连通的。强连通是顶点之间的一种等价关系。有向图中的极大强连通子图，被称为强连通分量 (Strongly Connected Components, SCC)。

Tarjan 算法的核心思想

Tarjan 算法是一个基于深度优先搜索 (DFS) 的算法，它能在 O(V+E) 的时间内找出有向图中的所有强连通分量。

什么是 Dijkstra 算法？

Dijkstra 算法是一种用于计算图中 单源最短路径 的经典算法。它适用于所有边权都为 非负数 的图。

给定一个图和一个源点 s，Dijkstra 算法可以计算出 s 到所有其他节点的最短路径长度。

算法思想

Dijkstra 算法基于贪心策略。它维护一个从源点 s 出发的距离集合 dist，其中 dist[v] 表示当前已知的从 s 到 v 的最短距离。

什么是广度优先搜索？

广度优先搜索（BFS）是另一种用于遍历或搜索树或图的算法。它从根（或任意起始节点）开始，探索邻居节点，然后再逐层探索下一级的邻居节点。

算法思想

BFS 的核心是队列。

1. 创建一个队列，并将起始节点放入队列中。
2. 将起始节点标记为已访问。
3. 当队列不为空时，循环执行： a. 从队列中取出一个节点 u。 b. 访问 u 的所有未被访问的邻居节点。 c. 将这些邻居节点加入队列，并标记为已访问。

什么是深度优先搜索？

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索图的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

算法思想

DFS 的核心是栈（可以是显式的栈，也可以是函数调用栈）。

1. 从起始节点开始，访问它。
2. 将其一个未被访问的邻居节点压入栈中，并访问它。
3. 重复步骤 2，直到当前路径没有未被访问的邻居。
4. 如果当前节点没有未访问的邻居，就从栈中弹出一个节点，回溯。
5. 重复步骤 2-4，直到栈为空。