None Recursive version: Depth First Search in a Graph

mark_component.py

# Udacity, CS215, Homework 3.6 Mark components
# Rewrite `mark_component` to not use recursion 
# and instead use the `open_list` data structure 
# discussed in lecture

def mark_component(G, node, marked):
    total_marked = 1
    open_list = [node]
    while open_list:
        node = open_list.pop() # The key difference against BFS!
        marked[node] = True
        for neighbor in G[node]:
            if neighbor not in marked:
                #total_marked += mark_component(G, neighbor, marked)
                open_list.append(neighbor) 
                total_marked += 1
    return total_marked

#########
# Code for testing
#
def make_link(G, node1, node2):
    if node1 not in G:
        G[node1] = {}
    (G[node1])[node2] = 1
    if node2 not in G:
        G[node2] = {}
    (G[node2])[node1] = 1
    return G

def test():
    test_edges = [(1, 2), (2, 3), (4, 5), (5, 6)]
    G = {}
    for n1, n2 in test_edges:
        make_link(G, n1, n2)
    marked = {}
    assert mark_component(G, 1, marked) == 3
    assert 1 in marked
    assert 2 in marked
    assert 3 in marked
    assert 4 not in marked
    assert 5 not in marked
    assert 6 not in marked
    #print G
    #print mark_component(G, 1, marked)
    #print marked


test()

Print_results.py

Graph:
{1: {2: 1}, 2: {1: 1, 3: 1}, 3: {2: 1}, 4: {5: 1}, 5: {4: 1, 6: 1}, 6: {5: 1}}

total_marked: 
1(Why not 3?)

marked:
{1: True, 2: True, 3: True}