title: Python: Graph, DFS, set, defaultdict - error in changing dictionary size
body: <p>This problem arose when I was trying a depth-first approach of printing a disconnected graph.</p>
  
  <p>I am using a <code>defaultdict</code> for my adjacency list representation of the graph. I know that if a key isn't in the dictionary, the <code>defaultdict</code> would add it and provide whatever default value you set (in my case a <code>list</code>).</p>
  
  <p>Before you comment this as a duplicate, I have read the posts <a href="https://stackoverflow.com/questions/33679669/python-runtimeerror-dictionary-changed-size-during-iteration">here</a> and <a href="https://stackoverflow.com/questions/28257623/dictionary-changed-size-during-iteration">here</a>. 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 <code>defaultdict</code>.  </p>
  
  <p>The code is adapted from <a href="https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/" rel="nofollow noreferrer">GeeksForGeeks</a> but I decided to use a <code>set</code> instead of a <code>list</code> for visited vertices and I renamed the <code>DFSUtil</code> function, <code>DFSHelper</code>. 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.
  <a href="https://i.stack.imgur.com/pDkIm.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/pDkIm.png" alt="GeeksForGeeks graph being printed"></a></p>
  
  <p>Here's my code:</p>
  
  <pre><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()
  </code></pre>
  
  <p>I noticed that when I changed the first line in DFSHelper from:</p>
  
  <pre><code>if vertex not in visited:
  </code></pre>
  
  <p>to </p>
  
  <pre><code>if vertex not in visited and vertex in self.graph:
  </code></pre>
  
  <p>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 <code>defaultdict</code> and since the default action of a <code>defaultdict</code> is to create an entry rather than return a key error, the <code>defaultdict</code> is changed during iteration. However, I don't see how 4 is being passed into the function <code>defaultdict</code>.</p>
  
  <p>Here's the output with the error. </p>
  
  <pre><code>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 &lt;module&gt;
      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
  </code></pre>
  
  <p>Note the 4 being printed. </p>
  
  <p>Here's the output with the error resolved. </p>
  
  <pre><code>Following is DFS of a disconnected graph
  0
  1
  2
  3
  5
  Visited :  {0, 1, 2, 3, 5}
  </code></pre>