scipy的前辈深度_first_order

Question

我使用scipy版本1.14.1按深度优先顺序遍历最小生成树，但有些结果我不明白，即scipy返回的前辈不正确。

这是下图的说明：

以下代码

import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse.csgraph import depth_first_order

rows = np.array([0, 1, 2, 2, 4, 9, 2,  2, 10, 10, 8 ])
cols = np.array([1, 2, 3, 4, 9, 5, 6, 10, 11,  8, 7 ])

# construct undirected graph
X = coo_matrix( (12,12))
X.col = np.concatenate( (rows, cols), axis=0)
X.row = np.concatenate( (cols, rows), axis=0)
X.data = np.ones(len(X.row))

# the minimum spanning tree is the graph itself
tree = minimum_spanning_tree(X)
print(tree)

# traversing the graph
print(depth_first_order(tree, i_start=0, directed=False, return_predecessors=True))

给出最小生成树（实际上是图本身）：

  Coords    Values
  (0, 1)    1.0
  (1, 2)    1.0
  (2, 3)    1.0
  (2, 4)    1.0
  (2, 6)    1.0
  (2, 10)   1.0
  (4, 9)    1.0
  (5, 9)    1.0
  (7, 8)    1.0
  (8, 10)   1.0
  (10, 11)  1.0

和深度优先顺序：

[ 0, 1, 2, 3, 4, 9, 5, 6, 10, 11, 8, 7]

前辈：

[-9999, 0, 1, 2, 2, 9, 2, 8,10, 4, 2, 10]

所以它说 9 有 9 作为祖先，但它是 4，从这个位置来看结果是不一致的。

感谢您的帮助。

Answer 1

你误会了

predecessors

。 数组的索引是节点本身，而不是节点在深度优先数组中的位置。

也就是说，5 的父级是 9，6 的父级是 2，7 的父级是 8，...