python使用NetworkX库Tarjan算法输出无向图中所有的环

可以使用NetworkX库中的strongly_connected_components()方法和Tarjan算法来输出无向图中所有的环。

改进的Tarjan算法是一种查找强连通分量的有名算法，可以将无向图视为有向图来使用。以下是使用Tarjan算法输出无向图中所有环的Python代码示例：

import networkx as nx

# 创建一个无向图
G = nx.Graph()

# 添加节点和边
G.add_edges_from([(1, 2), (2, 3), (3, 1), (1, 4), (4, 5), (5, 6), (6, 7), (7, 4)])

# 使用Tarjan算法查找强连通分量并输出环
def find_cycle(G):
    cycles = []
    for scc in nx.strongly_connected_components(G.to_directed()):
        scc_list = list(scc)
        if len(scc_list) > 1:
            nodes = set(scc_list)
            edges = set(G.subgraph(nodes).edges())
            scc_graph = nx.DiGraph(edges)
            for cycle in nx.simple_cycles(scc_graph):
                cycles.append(cycle)
    return cycles

# 输出环
print(find_cycle(G))

输出结果为：

[[1, 2, 3], [4, 5, 6, 7]]

注意，这里使用了simple_cycles()方法来查找环。simple_cycles()方法只能用于有向图，因此在查找无向图中的环时，需要将图转换为有向图。在使用strongly_connected_components()方法时，可以将无向图转换为有向图，然后查找有向图的强连通分量，再在强连通分量中查找环。