Skip to content

Instantly share code, notes, and snippets.

@vishr

vishr/dfs.py

Created December 4, 2011 06:59
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save vishr/1429463 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save vishr/1429463 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Vishal Rana revised this gist Dec 4, 2011. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions dfs.py
    View file
    Original file line number Diff line number Diff line change
    @@ -37,8 +37,8 @@ def iterative_dfs(tree, node, path=[]):
    9: [10, 11]
    })

    print "recursive_dfs: ", recursive_dfs(tree, 1)
    print "recursive_dfs:", recursive_dfs(tree, 1)
    # recursive_dfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

    print "iterative_dfs: ", iterative_dfs(tree, 1)
    print "iterative_dfs:", iterative_dfs(tree, 1)
    # iterative_dfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  2. Vishal Rana revised this gist Dec 4, 2011. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions dfs.py
    View file
    Original file line number Diff line number Diff line change
    @@ -35,10 +35,10 @@ def iterative_dfs(tree, node, path=[]):
    3: [4, 5],
    8: [9, 12],
    9: [10, 11]
    })
    })

    print "recursive_dfs: ", recursive_dfs(tree, 1)
    # recursive_dfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

    print "iterative_dfs: ", iterative_dfs(tree, 1)
    # iterative_dfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
    # iterative_dfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  3. Vishal Rana created this gist Dec 4, 2011.
    44 changes: 44 additions & 0 deletions dfs.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,44 @@
    from collections import defaultdict

    def recursive_dfs(tree, node, path=[]):
    """
    Recursive depth first search
    """
    path.append(node)
    for child in tree[node]:
    path = recursive_dfs(tree, child, path)
    return path

    def iterative_dfs(tree, node, path=[]):
    """
    Iterative depth first search
    """
    queue = [node]
    while queue:
    n = queue.pop(0)
    path.append(n)
    queue = tree[n] + queue
    return path

    # -------------------- #
    # 1 #
    # / | \ #
    # 2 7 8 #
    # / \ | \ #
    # 3 6 9 12 #
    # / \ | \ #
    # 4 5 10 11 #
    # -------------------- #
    tree = defaultdict(list, {
    1: [2, 7, 8],
    2: [3, 6],
    3: [4, 5],
    8: [9, 12],
    9: [10, 11]
    })

    print "recursive_dfs: ", recursive_dfs(tree, 1)
    # recursive_dfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

    print "iterative_dfs: ", iterative_dfs(tree, 1)
    # iterative_dfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]