1

我有一个非常大的 DAG 字符串（~200k）。我想找到该图中存在的最长路径。下面的代码是我设置图表的方式（来自字符串列表new_list）。

#create new empty graph
g = nx.DiGraph()

#add all words to graph
for word in new_list:
    g.add_node(word)

#fill graph with valid word chains
for word in g.nodes():
    for c in string.ascii_lowercase:
        new_word = alphagramatize(word+c) #add char c to word in alphagram order
        if(binary_search(new_list, new_word) != -1):
            g.add_edge(word, new_word)

我尝试了检查从每个节点到每个其他节点的路径距离的幼稚方法......这显然是不切实际的并且不会终止。

我也试图longest_path()从这个线程重新编写代码，但无济于事。

我已经阅读了很多关于执行图形的拓扑排序和排序的知识，但是在实现这一点时遇到了麻烦。Networkx 提供了一个功能topological_sort(g)，以便为我完成工作。但是，既然我有一个 topo_sorted 图，我该如何从这里开始呢？

4

0 回答 0