Depth first search using a dictionary?

Question

I'm trying to do a depth first search using a dictionary in which the key is the next node that will be visited and the value is the predecessor, but something isn't quite right. So far I have:

from collections import deque
class Graph:

    def __init__(self, n):
        self.adj = {}
        for i in range(n):
            self.adj[i] = []

    def are_connected(self, node1, node2):
        return node2 in self.adj[node1]

    def adjacent_nodes(self, node):
        return self.adj[node]

    def add_node(self):
        self.adj[len(self.adj)] = []

    def add_edge(self, node1, node2):
        if node1 not in self.adj[node2]:
            self.adj[node1].append(node2)
            self.adj[node2].append(node1)

    def number_of_nodes():
        return len()

def DFS(G, node1):
    S = [node1]
    marked = {}
    pred = {}
    for node in G.adj:
        marked[node] = False
    while len(S) != 0:
        current_node = S.pop()
        if not marked[current_node]:
            marked[current_node] = True
            for node in G.adj[current_node]:
                # if node == node2:
                #     return True
                S.append(node)
        if not marked[node]:
            pred[node] = current_node
    pred[current_node] = node
    return pred 

When I call:

G = Graph(20)
G.add_edge(1, 2)
G.add_edge(2, 3)
G.add_edge(3, 4)
G.add_edge(0, 1)
G.add_edge(4, 5)
G.add_edge(5, 6)
G.add_edge(6, 7)
G.add_edge(4, 6)
G.add_edge(2, 6)
G.add_edge(8, 9)
G.add_edge(10, 3)
G.add_edge(2, 3)

print(DFS(G, 1))

I get {0: 1, 6: 2, 10: 3, 1: 6} but that can't be right since there are many nodes in G that aren't even visited, and I can't quite see what the issue is. Any help is appreciated!

Answer 1

You have placed the if not marked[node] condition in the wrong place.

def DFS(G, node1):
    S = [node1]
    marked = {}
    pred = {}
    for node in G.adj:
        marked[node] = False
    while len(S) != 0:
        current_node = S.pop()
        if not marked[current_node]:
            marked[current_node] = True
            for node in G.adj[current_node]:
                # if node == node2:
                #     return True
                S.append(node)
                if not marked[node]:
                    pred[node] = current_node
    pred[current_node] = node
    return pred 

Output will be: {2: 1, 0: 1, 3: 4, 6: 2, 5: 4, 7: 6, 4: 6, 10: 3, 1: 6}

Is this what do you expect?