Попытка найти отключенные графики в 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]]

Мой подход к этой проблеме состоит в том, чтобы начать с любого края с ложным значением и начать с узла, представленного строками, и пройти через все возможные ребра, соединяющие этот узел и его дочерний узел, и так далее. Когда я прохожу по этим вершинам, я отмечу логическую матрицу как истинную, поскольку я «посетил» это ребро. Как только я узнаю, что «посетил» все ребра, я знаю, что у меня будет связный подграф. Затем я буду искать еще одно «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] Пожалуйста, укажите мне, где я ошибся с рекурсией

3
0
734
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Я не совсем понимаю этот фрагмент кода,

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, а не список детей. То, что вы ранее сохранили в children, является порядковым номером. Вы определенно не хотите находить индекс порядкового номера.

Редактировать: если вы выполняете итерацию по итерируемому объекту, пожалуйста, не называйте свое значение так же, как и само итерируемое. Угадайте, что происходит ниже?

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

Другие вопросы по теме