Skip to content

Instantly share code, notes, and snippets.

@vishr

vishr/bfs.py

Created December 4, 2011 06:05
Download ZIP

Revisions

  1. Vishal Rana revised this gist Dec 4, 2011. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion bfs.py
    View file
    Original file line number Diff line number Diff line change
    @@ -28,5 +28,5 @@ def iterative_bfs(tree, node, path=[]):
    7: [11, 12]
    })

    print "iterative_bfs: ", iterative_bfs(tree, 1)
    print "iterative_bfs:", iterative_bfs(tree, 1)
    # iterative_bfs: [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 bfs.py
    View file
    Original file line number Diff line number Diff line change
    @@ -26,7 +26,7 @@ def iterative_bfs(tree, node, path=[]):
    4: [7, 8],
    5: [9, 10],
    7: [11, 12]
    })
    })

    print "iterative_bfs: ", iterative_bfs(tree, 1)
    # iterative_bfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
    # iterative_bfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  3. Vishal Rana revised this gist Dec 4, 2011. 2 changed files with 3 additions and 47 deletions.
    6 changes: 3 additions & 3 deletions bfs.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,6 @@
    from collections import defaultdict

    def bfs(tree, node, path=[]):
    def iterative_bfs(tree, node, path=[]):
    """
    Iterative breadth first search
    """
    @@ -28,5 +28,5 @@ def bfs(tree, node, path=[]):
    7: [11, 12]
    })

    print "bfs: ", bfs(tree, 1)
    # bfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
    print "iterative_bfs: ", iterative_bfs(tree, 1)
    # iterative_bfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
    44 changes: 0 additions & 44 deletions dfs.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,44 +0,0 @@
    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]
  4. Vishal Rana revised this gist Dec 4, 2011. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion dfs.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,3 @@

    from collections import defaultdict

    def recursive_dfs(tree, node, path=[]):
  5. Vishal Rana created this gist Dec 4, 2011.
    32 changes: 32 additions & 0 deletions bfs.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,32 @@
    from collections import defaultdict

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

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

    print "bfs: ", bfs(tree, 1)
    # bfs: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
    45 changes: 45 additions & 0 deletions dfs.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,45 @@

    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]