将中国城市名首尾相连，最多能连几个？

欧琳的吟颂的回答

这个问题抽象一下就是求一个有向有环图的最长路径，是个NP-hard的问题……随便让GPT写了个简单的函数跑了跑，用的是DFS+回溯算法，不保证是最长的路径。如果不考虑县和市辖区，那最后的结果是：

那曲阜新乐昌吉安康定西宁德兴义乌海东台北镇江山南通辽阳泉州（28个）

一些次长的路径：

侯马康定西昌吉安陆丰镇江山南宁德兴义乌海东台中卫辉县（25个）

嘉义乌海东台北镇江山南昌吉安康定西宁德兴仁怀化州（23个）

应该还有更优的算法，我晚点再琢磨一下。

编辑： @Yixiao Huang 答主列出的更长，他考虑到了同一个字被复用的情况，而我的代码没有考虑到……

图的结构如图，networkx生成的。好糊……

附上代码：

import networkx as nx
import matplotlib.pyplot as plt

city_names = [...] # 城市名略过

G = nx.DiGraph()

for name in city_names:
    G.add_edge(name[0], name[-1])

# 获取所有连通组件，返回的是一个每个组件都是节点集合的迭代器
components = nx.weakly_connected_components(G)

# 按照大小排序这些组件，选择最大的一个
largest_component = max(components, key=len)

# 创建一个只包含最大连通组件的子图
G2 = G.subgraph(largest_component).copy()

# 设置一个较高的plt dpi
plt.figure(figsize=(20, 20), dpi=400)

# 设置一个字体（WSL默认没有中文字体会变黑框）
plt.rcParams['font.sans-serif'] = ['SimHei']


pos = nx.kamada_kawai_layout(G2)

nx.draw(G2, pos, with_labels=True)
plt.show()

import random

def longest_path_nx(G, start_node):
    visited = {node: False for node in G.nodes}
    path = []
    max_path = []
    max_len = 0

    def dfs(node, visited, path):
        nonlocal max_len, max_path

        # 标记当前节点为已访问，并添加到路径中
        visited[node] = True
        path.append(node)

        # 检查所有邻居节点
        for neighbor in G.neighbors(node):
            if visited[neighbor] == False:
                # print(len(path), path[-5:])
                # time.sleep(0.1)
                dfs(neighbor, visited, path)

        # 记录当前最长路径
        if len(path) > max_len:
            max_len = len(path)
            max_path = list(path)

        # 回溯：移除当前节点并标记为未访问
        path.pop()
        visited[node] = False

    dfs(start_node, visited, path)

    return max_len, max_path

# 使用方法：

max_length = 0
max_path = None

for _ in range(10000):  # 你可以自行调整这个值以改变搜索次数
    start_node = random.choice(list(G.nodes))
    length, path = longest_path_nx(G, start_node)
    if length > max_length:
        max_length = length
        max_path = path

print("最长路径的长度:", max_length)
print("最长路径:", max_path)