反馈顶点集问题的所有算法

反馈顶点集问题是在有向图中寻找一个顶点集，使得该图中不存在从该顶点集中的任意顶点出发的环。以下是反馈顶点集问题的几种常见算法：

拓扑排序：对有向无环图进行拓扑排序，得到的顶点序列即为一个反馈顶点集。
Tarjan算法：使用深度优先搜索遍历图，同时记录每个节点的“发现时间”和“最小发现时间”，如果某个节点存在后向边（即存在环），则该节点的最小发现时间一定小于等于后向边指向的节点的发现时间。通过记录每个节点的最小发现时间，可以找到所有反馈顶点集。
Johnson算法：首先对图进行一次变换，将图中所有权值变为非负值，并添加一个新的源节点，连向所有其他节点，权值为0。然后使用Bellman-Ford算法求解源节点到所有节点的最短路径，将权值还原为原来的值。最后，对于每个节点，使用Dijkstra算法求解该节点到其他节点的最短路径，同时记录路径上的前驱节点。通过前驱节点可以找到所有反馈顶点集。
最小割算法：将有向图转化为无向图，求解最小割，将割边切断，得到两个连通分量。如果其中一个分量中存在环，则该环为一个反馈顶点集。如果两个分量中都不存在环，则可以继续将两个分量分别进行最小割，直到找到反馈顶点集为止。
随机算法：使用随机算法，从图中随机选取一些节点，判断是否存在反馈顶点集，如果不存在，则继续随机选取节点，直到找到反馈顶点集为止。由于随机算法的随机性，不能保证每次都能找到反馈顶点集，但是可以提高算法的效率。