tarjan算法（tarjan算法无向图）

tarjan算法是一种用于图的深度优先搜索的算法，用于查找图中的强连通分量。它由美国计算机科学家Robert Tarjan在1972年提出，并以他的名字命名。这个算法的主要思想是通过DFS遍历图，将节点标记为已访问，并给予每个节点一个低链接值（low-link），用来判断节点所在的连通分量。下面将详细介绍tarjan算法的步骤及应用。

## 算法步骤

1. 初始化：将所有节点标记为未访问状态，并创建一个堆栈用于存储节点。同时定义一个全局变量index，用于给每个节点赋予一个遍历顺序。

2. 遍历节点：从图中的任意一个未访问节点开始，进行深度优先搜索。遍历到一个节点时，将其标记为已访问，并给予其index和low-link值。

3. 控制回溯：当遍历到节点v时，将其入栈，并遍历其邻接节点u。如果u未被访问，则继续递归遍历u节点，并更新v节点的low-link值为v节点和u节点low-link的最小值。若u已被访问且在堆栈中，则将v节点的low-link值更新为v节点和u节点index的最小值，表示在v和u之间存在一条回边，即v节点所在的强连通分量未被完全遍历。

4. 判断连通分量：当遍历完所有与节点v相连的节点时，判断v节点的low-link值是否等于index值。若相等，则表示v节点是一个连通分量的根节点，将v节点出栈并将栈中所有节点弹出，这些节点构成了一个强连通分量。重复以上步骤，直到遍历所有节点。

## 算法应用

tarjan算法在图的深度优先搜索中被广泛应用。它可以有效地识别出图中的强连通分量，即具有相互可达的节点集合。这在许多问题中非常有用，例如寻找网络中的环路、判断图的连通性、解决路径规划问题等。

一个典型的应用是在有向图中判断是否存在循环路径。通过应用tarjan算法，可以轻松找到图中的所有强连通分量，并通过判断是否存在根节点为自己的强连通分量，来判断是否存在循环路径。

另一个应用是寻找有向图的拓扑排序。通过将图中的所有节点按照tarjan算法得到的连通分量进行拓扑排序，可以得到图中节点的一种合理顺序，使得任意一条有向边的起始节点都排在终止节点之前。

总之，tarjan算法是一个非常重要且实用的图算法，可以解决许多与图相关的问题。在实际应用中，我们可以根据具体问题的要求，灵活运用tarjan算法来解决各种图论问题。