components.py

class Node(object):
    def __init__(self, name, checkpoint=False):
        self.name = name
        self.explored = False
        self.checkpoint = checkpoint
        self.edges = []

    def add_edge(self, other):
        self.edges.append(other)

    def __str__(self):
        edges_str = ', '.join(str(other) for other in self.edges)
        return '(' + self.name + ': ' + edges_str + ')'

    def __repr__(self):
        return self.name


def dfs(root):
    if len(root.edges) == 0:
        return [root]
    elif len(root.edges) == 1:
        return [root] + dfs(root.edges[0])
    else:
        return [[root]] + [dfs(other) for other in root.edges]


def dfs_tree(root):
    root.explored = True

    new_node = Node(root.name, root.checkpoint)
    for other in root.edges:
        if not other.explored and not other.checkpoint:
            new_node.add_edge(dfs_tree(other))
    return new_node


if __name__ == '__main__':
    a = Node('A')
    b = Node('B')
    c = Node('C')
    d = Node('D', checkpoint=True)
    e = Node('E')
    f = Node('F', checkpoint=True)
    g = Node('G')
    h = Node('H', checkpoint=True)

    nodes = [a, b, c, d, e, f, g, h]

    a.add_edge(b)
    a.add_edge(c)
    b.add_edge(f)
    f.add_edge(h)
    c.add_edge(d)
    c.add_edge(e)
    d.add_edge(g)
    e.add_edge(g)
    g.add_edge(h)

    print dfs(dfs_tree(a))