时间戳

首页 > 解决方案 > 尝试在 Python 中查找断开连接的图

python - 尝试在 Python 中查找断开连接的图

问题描述

我希望在 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，因为我已经“访问”了那个边缘。一旦我知道我已经“访问”了所有的边，我就知道我将有一个连通的子图。然后我将在我的真/假矩阵中寻找另一个“假”，然后从那里开始寻找另一个断开连接的图，并继续直到我将所有元素都填写为真。

但是，我被困在穿越边缘

这是我的算法：

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] 请指出我在递归中出错的地方

标签： pythonrecursiongraph-theory

解决方案

这段代码看不懂

for child,children in enumerate(children):
    print(child)
    traverse(child,visited_nodes,looped)

改成，

for child in children:
    print(child)
    traverse(child,visited_nodes,looped)

答案就在那里。

你要的是访问children中的每一个child，而不是children的索引。您children之前保存的是索引号。你肯定不想找到索引号的索引。

编辑：如果您正在迭代一个可迭代对象，请不要将您的值命名为与可迭代对象本身相同的名称。猜猜下面会发生什么？

children = list(range(10))  
for child,children in enumerate(children):
    pass
print(children)

推荐阅读