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

1: The dict you wanna return from the DFS function is not able to show. Assumed that we have two paths to node 1 which are node 0 and node 2, if we got {1: 2}, then {1: 0} will replace the {1: 2} and you may lost some node paths.

2: To do the depth first search, we need to "walk to the end". your array S in the function make a loop but make breadth first.

I use recursive function to modify your code:

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

And I ran your test case. Here is the print result: [1, 2, 3, 4, 5, 6, 7, 10, 0]

Hope the answer may help you eh.

Answer 2

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?