代码之家 › 专栏 › 技术社区 › user11634

scipy depth_first_order的前身

depth-first-search networkx tree scipy python

user11634 · 技术社区 · 1 年前

我使用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,从这个位置来看,结果并不一致。

谢谢你的帮助。

2 回复 | 直到 1 年前

Sandipan Dey 1 年前

从 documentation ,功能 depth_first_order() 返回以下两个列表:

node_array ndarray,一维深度优先节点列表, 从指定节点开始。node_array的长度是数字从指定节点可访问的节点数。

predecessors ndarray,一维仅在以下情况下返回 return_prepeaters为True。每个前体的长度-N列表深度优先树中的节点。如果节点i在树中,那么它的父节点是前人给出的。如果节点i不在树中(对于父节点)然后前置节点[i]=-9999。

这基本上意味着第二个列表 前辈 return与第一个列表无关 node_array 返回。相反,第二份清单应被解读为:

[Ï[i] if i â G else -9999 for all i] ,在哪里 Ï[i] 是父母 node i 以及图表 G 这里有一棵(跨越)树。

名单 predecessors = [-9999, 0, 1, 2, 2, 9, 2, 8,10, 4, 2, 10] 应按如下方式阅读

[0]=-9999(因为节点0在G中没有父节点)

[1] =0(节点1的父节点是节点0)

[2] = 1

[3] = 2

[4] = 2

[[5] = 9

[6] = 2

[7] = 8

...

您可以通过以下方式获得相同的结果 networkx.dfs_predecessors() 更明确地说,它是一个字典,其中key是一个节点,value是节点的父节点(使用 dfs 遍历):

import networkx as nx
nx.dfs_predecessors(tree, source=0)
# {1: 0, 2: 1, 3: 2, 4: 2, 9: 4, 5: 9, 6: 2, 10: 2, 11: 10, 8: 10, 7: 8}

Frank Yellin 1 年前

你误会了 predecessors 数组中的索引是节点本身,而不是节点在深度优先数组中的位置。

这是说5的父是9,6的父是2,7的父是8。。。