python实现无向图中环查找的Tarjan算法代码

### 回答1：

class Tarjan:
    def __init__(self, graph):
        self.graph = graph
        self.index = 0
        self.stack = []
        self.visited = [False for _ in range(graph.num_vertices)]
        self.indices = [-1 for _ in range(graph.num_vertices)]
        self.low_link_values = [-1 for _ in range(graph.num_vertices)]
        self.on_stack = [False for _ in range(graph.num_vertices)]
        self.scc = []

    def is_cyclic(self):
        for vertex in range(self.graph.num_vertices):
            if not self.visited[vertex]:
                self.strongconnect(vertex)
        return any(len(x) > 1 for x in self.scc)

    def strongconnect(self, vertex):
        self.visited[vertex] = True
        self.indices[vertex] = self.index
        self.low_link_values[vertex] = self.index
        self.index += 1
        self.stack.append(vertex)
        self.on_stack[vertex] = True

        for neighbor in self.graph.get_adjacent_vertices(vertex):
            if not self.visited[neighbor]:
                self.strongconnect(neighbor)
                self.low_link_values[vertex] = min(self.low_link_values[vertex], self.low_link_values[neighbor])
            elif self.on_stack[neighbor]:
                self.low_link_values[vertex] = min(self.low_link_values[vertex], self.indices[neighbor])

        if self.low_link_values[vertex] == self.indices[vertex]:
            scc = set()
            while True:
                w = self.stack.pop()
                self.on_stack[w] = False
                scc.add(w)
                if w == vertex:
                    break
            self.scc.append(scc)

上面是Tarjan算法查找无向图中环的Python代码。使用时，需要传入一个图对象，然后调用is_cyclic()方法，如果返回值为True，则说明图中存在环。

注意，这段代码需要图数据结构的支持，图的实现可以自己实现或者使用第三方库如networkx。

### 回答2：
Tarjan算法是一种强连通分量算法，可以用于在无向图中查找环。下面是用Python实现Tarjan算法的代码：

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]
        self.visited = [False] * num_vertices
        self.low = [0] * num_vertices
        self.ids = [0] * num_vertices
        self.id = 0
        self.result = []

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

    def tarjan(self, v, parent):
        self.visited[v] = True
        self.low[v] = self.ids[v] = self.id
        self.id += 1

        for neighbor in self.adj_list[v]:
            if neighbor == parent:
                continue
            if not self.visited[neighbor]:
                self.tarjan(neighbor, v)
                self.low[v] = min(self.low[neighbor], self.low[v])
                if self.low[neighbor] > self.ids[v]:
                    self.result.append((v, neighbor))
            else:
                self.low[v] = min(self.low[v], self.ids[neighbor])

    def find_cycles(self):
        for i in range(self.num_vertices):
            if not self.visited[i]:
                self.tarjan(i, -1)

        if len(self.result) == 0:
            print('The graph does not contain any cycles.')
        else:
            print('The cycles in the graph are:')
            for cycle in self.result:
                print(cycle)


g = Graph(5)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 0)
g.add_edge(2, 4)
g.find_cycles()

以上代码实现了一个`Graph`类，包含了添加边、Tarjan算法等功能。通过调用`find_cycles`方法可以找到给定无向图中的所有环。在测试代码中，创建了一个包含5个顶点的无向图，并添加了若干条边。通过调用`find_cycles`方法，将打印出图中的所有环。如果图中不包含任何环，则会打印出相应的提示信息。

### 回答3：
Tarjan算法是一种用于查找无向图中环的强大算法。它通过遍历图中的每个节点，深度优先搜索子节点，并利用栈来维护当前遍历路径的节点。具体的Python实现如下：

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for _ in range(vertices)]
        self.Index = [-1] * vertices
        self.Lowlink = [-1] * vertices
        self.OnStack = [False] * vertices
        self.stack = []
        self.count = 0

    def addEdge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

    def tarjan(self, u, parent):
        self.Index[u] = self.count
        self.Lowlink[u] = self.count
        self.count += 1
        self.stack.append(u)
        self.OnStack[u] = True

        for v in self.adj[u]:
            if v == parent:
                continue
            if self.Index[v] == -1:
                self.tarjan(v, u)
                self.Lowlink[u] = min(self.Lowlink[u], self.Lowlink[v])
            elif self.OnStack[v]:
                self.Lowlink[u] = min(self.Lowlink[u], self.Index[v])

        if self.Lowlink[u] == self.Index[u]:
            w = -1
            while w != u:
                w = self.stack.pop()
                self.OnStack[w] = False
                print(w, end=" ")
            print()

    def findCycle(self):
        for i in range(self.V):
            if self.Index[i] == -1:
                self.tarjan(i, -1)


# 测试样例
g = Graph(5)
g.addEdge(1, 0)
g.addEdge(0, 2)
g.addEdge(2, 1)
g.addEdge(0, 3)
g.addEdge(3, 4)

print("无向图中的环为:")
g.findCycle()

这段代码首先定义了一个Graph类来表示无向图，其中包括图的顶点数和邻接列表。在tarjan函数中，使用了Index、Lowlink和OnStack列表来记录每个节点的索引、最低链接值以及是否在栈中。遍历节点时，使用递归进行深度优先搜索，并根据Index和Lowlink值来判断是否找到环。在findCycle函数中，遍历图中的每个节点，对没有被访问过的节点调用tarjan函数进行环的查找。最后的测试样例中，创建了一幅无向图，然后调用findCycle函数查找环，并输出结果。

希望这段代码能够帮助你理解Python实现的Tarjan算法，并在无向图中查找环的过程中能够起到指导作用。