Search code examples
pythondepth-first-search

Search through the network and stop when the value of the node along the search path meet the target

graph

I got a directed network graph and need to find all possible paths from node "a" and compare the value of every node along every possible path. If it reaches a node which value is less than the value of a, then it will stop to search the rest of that specific path. For example, in this network, we can get four possible paths:

a,b,e,m

a,c,f,k

a,c,g,h

a,c,g,I

Solution

  • The specific code will depend on what graph framework (if any) you are using to represent the graph. In general, a depth-first search is a recursive algorithm; so if you have a list of sub-nodes for each node (assuming your structure is a tree like the one in the image), you can loop through each node's children and then for each:

    • If value is greater than or equal to a, recursively check sub-nodes
    • Otherwise, stop the recursive call (i.e., backtrack up the branch toward the root node)

    This is just general guidance; if you can provide a sample of your current code, we can give some more specific direction.