用Python提取最小生成树

Question

用python自带的networkx提取出了引文网络（非连通图）中的最小生成森林如图：

已经整理成了Dataframe如图：

现在想从这个里面找到路径最长的一棵树，如何用代码实现呢？
或者：已经用Gephi测出了这个引文网络的直径，如何找出这条路径呢？

Answer 1

🌈🌈🌈参考通义千问和郭老师的小迷弟雅思莫了-编写提供🌈🌈🌈
您可以参考如下，如果回答的不正确，及时评论区回复我，我会根据你错误描述追加回复，直到您满意为止。

你可以使用networkx库中的各种函数来实现。和找最短路径相比，找最长路径要复杂一些，因为这是一个NP-hard问题。这就是说，我们必须采用一种启发式的、非精确的方法来解决，或者对于一些特定类型的图（比如树），我们可以找到精确的解决方案。

对于任何类型的图，你可以采用深度优先搜索（DFS）的方法查找最长路径。DFS函数会遍历图中的所有顶点，然后返回最长路径。如果图很大，这种方法可能会很慢，因为其复杂度为O(v + e) ，其中v 和 e 分别为顶点和边的数量。

import networkx as nx

G = ...   # 你从文件中加载的网络
longest_path = []
for n in G.nodes:
    # 遍历每一个节点，并对每一个节点执行深度优先搜索
    path = nx.single_source_dijkstra(G, n)
    if len(path) > len(longest_path):
        longest_path = path

print("Longest path is ", longest_path)

对于树（包括你提到的最小生成森林），最长路径必然是从一个叶节点到另一个叶节点的路径，我们可以用两次DFS来精确找到这条路径。首先，我们从图中任意一个节点出发做一次DFS，找到离这个节点最远的节点A，然后再从节点A出发做一次DFS，找到离节点A最远的节点B，那么从A到B的路径就是最长路径。

G = ...   # 你从文件中加载的网络

# 从任意一个节点出发进行DFS
start_node = list(G.nodes)[0]
_, path_1 = nx.single_source_dijkstra(G, start_node)
# 找到第一次DFS的最远节点
farthest_node = path_1[-1]

# 从最远节点出发进行第二次DFS
_, longest_path = nx.single_source_dijkstra(G, farthest_node)

print("Longest path is ", longest_path)

注意：上述代码中的nx.single_source_dijkstra函数不仅返回最长路径，还返回其他信息，我们只需要最长路径，所以用了_来忽略其他返回信息。你需要将G = ...替换为你真实的图。
以上只是为你提供一个基本的指导，你需要根据实际问题进行必要的调整。例如，你可能需要把你的图转化为无向图来进行以上操作。希望能帮到你，如果有其他问题，请随时提问。