我期待在Python中找到断开连接的子图
以此图为例:索引0代表节点A,1代表B ......等等-1只是占位符,因为这是一个没有边连接自己的简单图 .
5表示边缘的权重(将来会有不同权重的图表)
[[-1 5 5 0 0]
[ 5 -1 0 0 0]
[ 5 0 -1 0 5]
[ 0 0 0 -1 0]
[ 0 0 5 0 -1]]
要查找断开连接的图形,我首先创建了一个True / False,如果我已经访问过边缘 . (0和-1默认为True),如下所示:
[[ True False False True True]
[False True True True True]
[False True True True False]
[ True True True True True]
[ True True False True True]]
我解决这个问题的方法是从具有错误值的任何边开始,并从行所表示的节点开始,并遍历连接该节点及其子节点的所有可能边,依此类推 . 当我遍历这些顶点时,我会将布尔矩阵标记为True,因为我已“访问”该边缘 . 一旦我知道我已“访问”了所有边缘,我知道我将有一个连接的子图 . 然后我将在我的True / False矩阵中寻找另一个“False”并从那里开始寻找另一个断开连接的图形,并继续直到我将所有元素填充为True .
但是,我被困在穿过边缘
这是我的算法:
reducedMatrix = np.load(reducedweightmatrix)
print(reducedMatrix)
boolarray = (reducedMatrix == 0) | (reducedMatrix == -1)
print(boolarray)
def traverse(iy,visited_nodes,looped):
#Only move to next index if there is no loop
# already visited node?
print("I am currently at: "+ str(iy))
print(visited_nodes)
print(looped)
print("-----------------\n")
if (iy in visited_nodes):
looped = True
if(not looped):
print("I enterred the loop")
children = []
#Find connected "children" vertices
for ix,weight in enumerate(reducedMatrix[iy]):
if weight != 0 and weight != -1:
#Collect the index with connected vertices
children.append(ix)
#I AM GOING TO VISIT THESE VERTICES
boolarray[iy,ix] = True
print(children)
visited_nodes.append(iy)
for child,children in enumerate(children):
print(child)
traverse(child,visited_nodes,looped)
return visited_nodes
print(traverse(0,[],False))
使用上面显示的示例,以下是日志消息:
[[-1 5 5 0 0]
[ 5 -1 0 0 0]
[ 5 0 -1 0 5]
[ 0 0 0 -1 0]
[ 0 0 5 0 -1]]
[[ True False False True True]
[False True True True True]
[False True True True False]
[ True True True True True]
[ True True False True True]]
I am currently at: 0
[]
False
-----------------
False
I enterred the loop
[1, 2]
0
I am currently at: 0
[0]
False
-----------------
True
1
I am currently at: 1
[0]
False
-----------------
False
I enterred the loop
[0]
0
I am currently at: 0
[0, 1]
False
-----------------
True
[0, 1]
根据上面的例子,算法应该显示如下:[0,1,2,4]请指出我在哪里出错了递归
1 回答
我不太明白这段代码,
只需将其更改为
答案就在那边 .
你想要的是访问孩子的每个孩子,而不是孩子的索引 . 您之前在
children
中保存的是索引编号 . 你肯定不想找到索引号的索引 .Edit :如果要迭代迭代,请不要将您的值命名为与iterable本身相同 . 猜猜下面会发生什么?