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

scipy depth_first_order的前身

depth-first-search networkx tree scipy python

user11634 · 技术社区 · 6 月前

我使用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 回复 | 直到 6 月前

Sandipan Dey 6 月前

从 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 6 月前

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

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

推荐文章

Google User · Django管理员在`list_display中未显示`creation_date`字段`

4 月前

user29747013 · 如何创建一个新的数据框架,其中包含原始数据框架中列的聚合列?

4 月前

ÎÎÎ½Î· ÎÎ®Î¹Î½Î¿Ï · Python lxml.html语法错误:使用lxml find时XPATH的谓词无效

4 月前

user29715306 · from_users=和chats=电视节目中的差异

4 月前

Redshoe · 当执行numpy.genfromtxt()时,python是否会读取文件的所有行?

4 月前

RASEL MAHMUD · 为什么以及如何在is_even()函数内的IF条件中递归X变量在满足0后递增?[副本]

4 月前

prayner · 更新嵌套字典包含列表中的项

4 月前

Bringo Jr · 我可以在O(n)中解决这个问题吗?

4 月前

Dave · 如何在for循环中修改列表值

4 月前

Shukurullox Komiljonov · 从记录中获得相互和解。使用SQL

4 月前