当前位置:网站首页>The path from root node to all leaves in a tree (or directed acyclic graph)

The path from root node to all leaves in a tree (or directed acyclic graph)

2020-12-07 14:21:06 osc_ ictoo263

problem : Suppose there's a tree now , Note that the trees here are not necessarily binary trees ( In other words, it can be a multi branch tree ), We want to enumerate the paths from the root node to each leaf node , How to implement this algorithm ?

The following example mainly uses Python To achieve . To make it easier to build a tree ( And then there's the digraph ), I'm going to use it directly here Python in NetworkX package (NetworkX It's a use. Python Graph theory and complex network modeling tools for language development ). First introduce the necessary packages .

import copy
import networkx as nx
from collections import deque

import matplotlib.pyplot as plt
%matplotlib inline

Building a multi fork tree T:

T = nx.DiGraph()
T.add_nodes_from(['a','b','c','d','e','f','g','i'])
T.add_edges_from([('a','b'),('b','c'),('c','d'),('d','e')])
T.add_edges_from([('b','f'),('f','g'),('f','h'),('b','i')])

nx.draw(T, with_labels=True)
plt.show()

Execute the above code , The results are shown in the figure below ( Be careful , Trees can also be seen as a special kind of directed graph . the NetworkX It is mainly used to deal with graphs , So the trees are not as hierarchical as we usually see , But essentially they are consistent ):

obviously , From the root node a To the leaf node e、g、h、i There are [a->b->c->d->e]、[a->b->f->g]、[a->b->f->h]、[a->b->i].

 

Specifically ( Non recursive ) The design idea of the algorithm can be inspired from the depth first traversal of the tree . The only thing to notice is that , If there is a bifurcation at a node , We need to maintain an additional stack structure to hold the path that has been obtained in front of the fork . The specific implementation code is given below , Note that this is a non recursive implementation :

majorStack = deque([])
minorStack = deque([])

listoflists = []
a_list = []

entry_node = 'a'

def find_all_paths():
    max_times = 0
    
    minorStack.append(entry_node)

    popCount = {}
    
    while minorStack:
        minLast = minorStack.pop()
        majorStack.append(minLast)
        a_list.append(minLast)
    
        current_s_nodes = list(T.successors(minLast))
        if current_s_nodes:
            for element in current_s_nodes:
                minorStack.append(element)
    
        majLast = majorStack[-1]
        #Loop condition:tos is a leaf OR all children of tos have been accessed
        while( not list(T.successors(majLast)) or 
                ( popCount.get(majLast, -1) == len(list(T.successors(majLast))))):
            last = majorStack.pop()
        
            if majorStack:
                majLast = majorStack[-1]
            else: # if majorStack is empty, then finish
                return
        
            if popCount.get(majLast, -1) == -1:
                popCount[majLast]=1
            else:
                popCount[majLast]=popCount[majLast]+1
        
            # if last is a leaf, then find a path from the root to a leaf
            if not list(T.successors(last)):
                listoflists.append(copy.deepcopy(a_list))
            
            a_list.pop()
        

find_all_paths()

print(listoflists)

Execute the above code , The results are as follows :

[['a', 'b', 'i'], ['a', 'b', 'f', 'h'], ['a', 'b', 'f', 'g'], ['a', 'b', 'c', 'd', 'e']]

so , Our algorithm successfully finds the path from the root node to all the leaf nodes .


below , We want to expand the problem , Suppose you want to find all the paths from the entry point to the exit point from a directed graph ? Be careful , The digraph here is limited to acyclic . for example , Here's an example based on NetworkX Examples of generated directed acyclic graphs :

G = nx.DiGraph()

G.add_node('a')                  # Add a node 1
G.add_nodes_from(['b','c','d','e','f','g','i'])    # Add point set 
G.add_edges_from([('a','b'),('b','c'),('c','d'),('d','e')])
G.add_edges_from([('b','f'),('f','g'),('f','h'),('b','j')])
G.add_edges_from([('h','k'),('h','i'),('j','h'),('k','l')])

nx.draw(G, with_labels=True)
plt.show()

Execute the above code , The results are shown in the figure below . From the entry node a To the exit node e、g、i、l There are [a->b->c->d->e]、[a->b->f->g]、[a->b->f->h->i]、[a->b->f->h->k->l]、[a->b->j->h->i]、[a->b->j->h->k->l].

Based on the algorithm given above to search the path in the tree , It is very simple to implement similar functions in directed acyclic graphs , We just need to add a line of code :

majorStack = deque([])
minorStack = deque([])

listoflists = []
a_list = []

entry_node = 'a'

def find_all_paths():
    max_times = 0
    
    minorStack.append(entry_node)

    popCount = {}
    
    while minorStack:
        minLast = minorStack.pop()
        majorStack.append(minLast)
        a_list.append(minLast)
    
        current_s_nodes = list(G.successors(minLast))
        if current_s_nodes:
            for element in current_s_nodes:
                minorStack.append(element)
                popCount[element]= -1
    
        majLast = majorStack[-1]
        #Loop condition:tos is a leaf OR all children of tos have been accessed
        while( not list(G.successors(majLast)) or 
                ( popCount.get(majLast, -1) == len(list(G.successors(majLast))))):
            last = majorStack.pop()
        
            if majorStack:
                majLast = majorStack[-1]
            else: # if majorStack is empty, then finish
                return
        
            if popCount.get(majLast, -1) == -1:
                popCount[majLast]=1
            else:
                popCount[majLast]=popCount[majLast]+1
        
            # if last is a leaf, then find a path from the root to a leaf
            if not list(G.successors(last)):
                listoflists.append(copy.deepcopy(a_list))
            
            a_list.pop()
        

find_all_paths()
print(listoflists)

Execute the above code , The results are as follows :

[['a', 'b', 'j', 'h', 'i'], ['a', 'b', 'j', 'h', 'k', 'l'], ['a', 'b', 'f', 'h', 'i'], ['a', 'b', 'f', 'h', 'k', 'l'], ['a', 'b', 'f', 'g'], ['a', 'b', 'c', 'd', 'e']]

It can be seen that the results obtained are consistent with our expectations .

 

【 The end of this paper 】

版权声明
本文为[osc_ ictoo263]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201207141706992i.html