title: Parallelize a depth-first algorithm in python
body: <p>I need to create a connected graph from two dataframes called nodes and edges.</p>
  <p>I am using <a href="https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-python" rel="nofollow noreferrer">https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-python</a> algorithm to filter out the nodes, which are not connected.</p>
  <p>Here is the code:</p>
  <pre><code># Using a Python dictionary to act as an adjacency list
  graph = {
      'A' : ['B','C'],
      'B' : ['D', 'E'],
      'C' : ['F'],
      'D' : [],
      'E' : ['F'],
      'F' : []
  }
  
  visited = set() # Set to keep track of visited nodes.
  
  def dfs(visited, graph, node):
      if node not in visited:
          print (node)
          visited.add(node)
          for neighbour in graph[node]:
              dfs(visited, graph, neighbour)
  
  # Driver Code
  dfs(visited, graph, 'A')
  </code></pre>
  <p>So first, I create the graph dictionary from my dataframes, and then use <code>dfs()</code> function to choose the connected nodes.</p>
  <p>However this process, is a little bit time consuming. For a decent size nodes, edges dataframe it takes 157 seconds to execute. I would like to beat that via multiprocessing.</p>
  <p>Is it possible to multiprocess this <code>dfs</code> function? If yes how?</p>
  <p><strong>NOTE:</strong> I am guessing, creating the graph dictionary is not the bottleneck here. However, here is also its code:</p>
  <pre><code>graph = dict.fromkeys(nodes['id'])
  
  for key in graph.keys():
      t = []
      for i in edges.index:
          if key in edges['node_id'][i]:
              if edges['node_id'][i].index(key) == 0:
                  index = 1
              else:
                  index = 0
  
              t.append(edges['node_id'][i][index])
      graph[key] = list(set(t))
  </code></pre>