Python: Graph, DFS, set, defaultdict - error in changing dictionary size

Question

This problem arose when I was trying a depth-first approach of printing a disconnected graph.

I am using a defaultdict for my adjacency list representation of the graph. I know that if a key isn't in the dictionary, the defaultdict would add it and provide whatever default value you set (in my case a list).

Before you comment this as a duplicate, I have read the posts here and here. They show that the dictionary is being changed during the iteration but I don't quite get how in my particular case. I am not popping any values from the defaultdict.

The code is adapted from GeeksForGeeks but I decided to use a set instead of a list for visited vertices and I renamed the DFSUtil function, DFSHelper. Moreover, the graph being printed is the same as the one below except that I added a node 5 pointing to node 4. I tried to add this to make the graph truly disconnected. Without this additional entry, no error is produced.

Here's my code:

from collections import defaultdict

class Graph:
  def __init__(self):
    self.graph = defaultdict(list)

  def addEdge(self, u, v):
    self.graph[u].append(v)

  def DFSHelper(self, vertex, visited):
    # recursively visit adjacent nodes
    if vertex not in visited:# and vertex in self.graph:
      visited.add(vertex)
      print(vertex)

      for neighbor in self.graph[vertex]:
        self.DFSHelper(neighbor, visited)

  def DFS(self): # for disconnected graph
    visited = set()

    # print(self.graph.keys())
    for vertex in self.graph.keys():
      if vertex not in visited:
        self.DFSHelper(vertex, visited)

    print('Visited : ', visited)

g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
g.addEdge(5, 4) # disconnected graph - I added this edge myself

print(g.graph)
print("Following is DFS of a disconnected graph")
g.DFS()

I noticed that when I changed the first line in DFSHelper from:

if vertex not in visited:

to

if vertex not in visited and vertex in self.graph:

the error would disappear but I don't get why that is the case. My assumption is that vertex 4 which is not a key is being searched in the defaultdict and since the default action of a defaultdict is to create an entry rather than return a key error, the defaultdict is changed during iteration. However, I don't see how 4 is being passed into the function defaultdict.

Here's the output with the error.

Following is DFS of a disconnected graph
0
1
2
3
5
4
Traceback (most recent call last):
  File "depth-first-search-disconnected_graph.py", line 41, in <module>
    g.DFS()
  File "depth-first-search-disconnected_graph.py", line 25, in DFS
    for vertex in self.graph.keys():
RuntimeError: dictionary changed size during iteration

Note the 4 being printed.

Here's the output with the error resolved.

Following is DFS of a disconnected graph
0
1
2
3
5
Visited :  {0, 1, 2, 3, 5}

Answer 1

When you get to the edge of 4 and 5, you go through the neighbors of 5 when the code reaches for neighbor in self.graph[vertex]. The only neighbor of 5 is 4 and you then call the function recursively with 4 as the vertex. In the next call of the DFSHelper, the defaultdict adds an entry for 4 because it's missing.

Just add your condition if vertex in self.graph before the for-loop to avoid this error.