Requesting help with my implementation of depth-first search

[ichabod801]

Look at the first wrong edge in the output: (3, 4). There is no such edge in your graph. How did it get that? When you add (1, 3), you change w to 3, but your for loop is still looping over the edges from 1. The next edge is (1, 4), but since you've changed w to 3, it stores it as (1, 4).

I don't understand how this algorithm is supposed to be working. I skipped that chapter when I read Discrete Mathematics because I'd done it with Introduction to Algorithms. That book uses a recursive search, which was my first instinct. I think to get it working without recursion you are going to have to reset your tracking variables a lot. When you change w, you have to change the list of edges you are going through. And when you go back after hitting a dead end I think you will need to reset i as well.

Edit: This gets the correct list of edges, just in a different order, and without recursion. It could probably be more efficient.

input_graph = {1:[3,4,8,9,11], 2:[3,8,12], 3:[1,2,5,11], 4:[1,6,9,10], 5:[3,12], 6:[4,10], 7:[8,12],
    8:[1,2,7,10], 9:[1,4,11], 10:[4,6,8], 11:[1,3,9], 12:[2,5,7]}

def DFS(graph, root):
    visited = set([root])
    current = root
    edges = []
    while len(visited) < len(graph):
        possible = [node for node in graph[current] if node not in visited]
        if possible:
            edges.append((current, possible[0]))
            visited.add(possible[0])
            current = possible[0]
        else:
            current = [start for start, end in edges if end == current][0]
    return edges

print(DFS(input_graph, 1))