如何从NetworkX中按特定顺序提取图边构建Shapely LineString

需要找到一条经过一组近似对齐点的最短路径，路径需适配所有方向，无法仅通过x或y值对节点排序。采用NetworkX构建图、计算最小生成树（MST），最终导出路径生成Shapely LineString（非MultiLineString）。NetworkX绘图结果符合预期，但无法按绘图中的正确顺序导出边来构建LineString，导出的节点顺序混乱。尝试过NetworkX所有内置导出函数、清理重复节点，以及大语言模型提供的方案，均未解决问题。

示例代码：

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from scipy.spatial.distance import pdist, squareform

points_line = np.array([[  0.46734317, 149.36430674],
       [  0.46734547, 149.36334419],
       [  0.46744031, 149.36238631],
       [  0.4676268 , 149.36144199],
       [  0.46734317, 149.36430674],
       [  0.46743343, 149.36526506],
       [  0.4676154 , 149.36621026],
       [  0.46788741, 149.36713358],
       [  0.46824692, 149.36802648],
       [  0.94443392, 150.40378967],
       [  0.4676268 , 149.36144199],
       [  1.55364459, 144.98283937],
       [  0.94443392, 150.40378967],
       [  0.68606383, 157.76059211],
       [  0.68606634, 157.76135963],
       [  1.55364459, 144.98283937],
       [  1.6347943 , 136.57997287],
       [  0.92188273, 132.24795534],
       [  0.92178416, 132.24715728],
       [  0.92175003, 132.24635387],
       [  0.90765426, 125.94462804],
       [  0.90769726, 125.94367903],
       [  0.68606634, 157.76135963],
       [  1.08596441, 167.35367069],
       [  0.66299718, 175.68436124],
       [  0.90769726, 125.94367903],
       [  1.8455184 , 115.86662374],
       [  1.22148527, 103.42945831],
       [  1.22148224, 103.42852062],
       [  1.22156706, 103.42758676],
       [  1.22173897, 103.42666495],
       [  1.89690364, 100.55965775],
       [  1.23628246,  92.47574962],
       [  1.23624942,  92.47487388],
       [  1.23629318,  92.47399861],
       [  1.23641341,  92.47313053],
       [  2.28757468,  86.74385772],
       [  2.28778124,  86.74296467],
       [  2.2880687 ,  86.74209429],
       [  2.28843466,  86.74125389],
       [  2.28887603,  86.74045053],
       [  2.2893891 ,  86.73969096],
       [  2.82731279,  86.01709145]])

# 创建图
G = nx.Graph()

# 添加节点
for i, point in enumerate(points_line):
    G.add_node(i, pos=point)

# 计算点对之间的距离
distances = pdist(points_line)
distance_matrix = squareform(distances)

# 添加带权重的边
for i in range(len(points_line)):
    for j in range(i+1, len(points_line)):
        G.add_edge(i, j, weight=distance_matrix[i][j])

# 计算最小生成树
mst = nx.minimum_spanning_tree(G)

# 提取边（原方法，顺序混乱）
edges = list(mst.edges())

# 原方法生成点序列，存在顺序问题
consecutive_points = []
for edge in edges:
    consecutive_points.append(points_line[edge[0]])
    consecutive_points.append(points_line[edge[1]])

consecutive_points_array = np.array(consecutive_points)
indices = np.concatenate(([True], np.any(np.diff(consecutive_points_array, axis=0) != 0, axis=1)))
filtered_points_array = consecutive_points_array[indices]

# 绘图
pos = nx.get_node_attributes(G, 'pos')
plt.figure(figsize=(12, 8))
nx.draw_networkx_nodes(G, pos, node_size=20)
nx.draw_networkx_edges(mst, pos, edge_color='r', width=1)
plt.title("最小生成树")
plt.axis('equal')
plt.show()

问题核心：最小生成树是无向树结构，直接提取的edges是无序的，无法直接拼接成连续路径。需要通过遍历树的方式，从叶子节点出发按顺序访问所有节点，得到连续路径序列。

修改后的代码：

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from scipy.spatial.distance import pdist, squareform
from shapely.geometry import LineString

points_line = np.array([[  0.46734317, 149.36430674],
       [  0.46734547, 149.36334419],
       [  0.46744031, 149.36238631],
       [  0.4676268 , 149.36144199],
       [  0.46734317, 149.36430674],
       [  0.46743343, 149.36526506],
       [  0.4676154 , 149.36621026],
       [  0.46788741, 149.36713358],
       [  0.46824692, 149.36802648],
       [  0.94443392, 150.40378967],
       [  0.4676268 , 149.36144199],
       [  1.55364459, 144.98283937],
       [  0.94443392, 150.40378967],
       [  0.68606383, 157.76059211],
       [  0.68606634, 157.76135963],
       [  1.55364459, 144.98283937],
       [  1.6347943 , 136.57997287],
       [  0.92188273, 132.24795534],
       [  0.92178416, 132.24715728],
       [  0.92175003, 132.24635387],
       [  0.90765426, 125.94462804],
       [  0.90769726, 125.94367903],
       [  0.68606634, 157.76135963],
       [  1.08596441, 167.35367069],
       [  0.66299718, 175.68436124],
       [  0.90769726, 125.94367903],
       [  1.8455184 , 115.86662374],
       [  1.22148527, 103.42945831],
       [  1.22148224, 103.42852062],
       [  1.22156706, 103.42758676],
       [  1.22173897, 103.42666495],
       [  1.89690364, 100.55965775],
       [  1.23628246,  92.47574962],
       [  1.23624942,  92.47487388],
       [  1.23629318,  92.47399861],
       [  1.23641341,  92.47313053],
       [  2.28757468,  86.74385772],
       [  2.28778124,  86.74296467],
       [  2.2880687 ,  86.74209429],
       [  2.28843466,  86.74125389],
       [  2.28887603,  86.74045053],
       [  2.2893891 ,  86.73969096],
       [  2.82731279,  86.01709145]])

# 创建图并计算MST
G = nx.Graph()
for i, point in enumerate(points_line):
    G.add_node(i, pos=point)

distances = pdist(points_line)
distance_matrix = squareform(distances)
for i in range(len(points_line)):
    for j in range(i+1, len(points_line)):
        G.add_edge(i, j, weight=distance_matrix[i][j])

mst = nx.minimum_spanning_tree(G)

# 找到叶子节点（度数为1的节点）作为遍历起点
leaf_nodes = [node for node in mst.nodes if mst.degree(node) == 1]
start_node = leaf_nodes[0]

# 深度优先遍历MST，得到节点访问顺序
visited = []
def dfs(node):
    visited.append(node)
    for neighbor in mst.neighbors(node):
        if neighbor not in visited:
            dfs(neighbor)

dfs(start_node)

# 根据访问顺序提取坐标点
ordered_points = points_line[visited]

# 生成Shapely LineString
line = LineString(ordered_points)
print("生成的LineString:", line)

# 验证绘图
pos = nx.get_node_attributes(G, 'pos')
plt.figure(figsize=(12, 8))
nx.draw_networkx_nodes(G, pos, node_size=20)
nx.draw_networkx_edges(mst, pos, edge_color='r', width=1)
# 绘制生成的路径
plt.plot(ordered_points[:,0], ordered_points[:,1], 'b--', linewidth=2, label='有序路径')
plt.title("最小生成树与有序路径")
plt.legend()
plt.axis('equal')
plt.show()

关键说明：

1. 叶子节点选择：MST作为树结构至少有两个叶子节点，任选其一作为遍历起点即可
2. DFS遍历：递归访问每个节点的未访问邻居，确保路径连续覆盖所有节点，每个节点仅访问一次
3. LineString生成：按遍历顺序提取的坐标点可直接转换为Shapely LineString，无需额外去重处理

内容的提问来源于stack exchange，提问作者user19109076