Блог

Главная - Вопросы по программированию - Терминальные узлы для каждого узла в графе

Терминальные узлы для каждого узла в графе

#python #graph #networkx

#python #График #networkx

Вопрос:

Я хочу перечислить все терминальные узлы относительно узла на графике, мой код работает, однако на сложном графике он работает неэффективно. КАК вы можете видеть, я использую рекурсию, которая не так эффективна при работе со сложным графиком.

 def neighbourt(T,item,st1,list1,list2):
 
    
    for n1 in T.neighbors(item):
        if n1 > item and T.degree(n1)> 1:
            #print(n1)
            st1=st1 neighbourt(T,n1,st1,list1,list2)
            
            
            
        elif n1 > item and T.degree(n1)==1:
            fruit_dictionary1 = dict(zip(list1,list2))
            ab=fruit_dictionary1[n1]
            st1=st1 str(ab) "_"
            #return st1
            
            
        
    return st1

Код написан на python, и item — это узел, а T — неориентированный граф.

Любое предложение было бы полезно.

Комментарии:

1. Используете ли вы графический пакет networkx? Я ожидаю, что он будет оптимизирован для быстрого выполнения этого типа рекурсии. python-course.eu/networkx.php

2. @C.Куни, да, я использую графический пакет NetworkX. Есть ли способ, которым я могу получить подграф конкретного узла, используя Networkx.

3. Под терминальными узлами вы подразумеваете листы? Не могли бы вы привести пример ввода / ожидаемого результата?

4. @abc Да, это означает, что пример конечных узлов A-> B, A-> C, B-> D, F, C-> E, для B я хочу D и F, а для C я хочу E …

Ответ №1:

Следующий код должен делать то же самое, но без рекурсии:

 def neighbourT(graph):
    for node in graph.nodes():
        for n in graph.neighbors(node):
            if n > node and graph.degree(n) == 1:
                print(node,n)

Например, для графа T:

 T = nx.Graph()
T.add_edge("A","B")
T.add_edge("A","C")
T.add_edge("B","D")
T.add_edge("B","F")
T.add_edge("C","E")
 
 neighbourT(T)
# prints
B D
B F
C E