我希望您能够在Python中查找断开的子图。
以此图为例: 索引0表示节点A,1表示B...等等 -1只是一个占位符,因为这是一个简单的图,没有边连接自己。
5代表边的权重(将来会有不同权重的图)。
为了查找未连接的图形,我首先创建了一个True / False变量,用于记录我是否已经访问了边缘(0和-1默认为True),如下所示:
我的解决这个问题的方法是从任意一个带有false值的边开始,从行表示的节点开始,并遍历所有可能连接该节点及其子节点等的边。当我沿着这些顶点遍历时,我会将布尔矩阵标记为True,因为我已经“访问”了那条边。一旦我知道我已经“访问”了所有的边,我就知道我将拥有一个连通的子图。然后,我会在我的真/假矩阵中寻找另一个“False”,并从那里开始寻找另一个未连接的图形,并继续直到我将所有元素都填充为True。
然而,我卡在了遍历边的过程中。
以下是我的算法:
使用上面展示的示例,以下是日志信息:
根据上面的例子,该算法应该显示以下内容: [0,1,2,4] 请指出我在递归方面哪里出了问题。
以此图为例: 索引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]]
我的解决这个问题的方法是从任意一个带有false值的边开始,从行表示的节点开始,并遍历所有可能连接该节点及其子节点等的边。当我沿着这些顶点遍历时,我会将布尔矩阵标记为True,因为我已经“访问”了那条边。一旦我知道我已经“访问”了所有的边,我就知道我将拥有一个连通的子图。然后,我会在我的真/假矩阵中寻找另一个“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] 请指出我在递归方面哪里出了问题。