title: How can I generate a random tree in python?
body: <p>I want to implement Tabu Search in Python to solve a problem related to a Graph (finding trees, coloring problem and that kind of stuff). I have written basic codes in Python and that's the first time I am writing something like that. I know how the algorithm works (in theory) and I am having some trouble to implement it.</p>
  
  <p>What's the best way to generate the random solution so I can start the algorithm? I want to generate a random tree from an initial graph:</p>
  
  <pre><code>graph = { "a" : ["c"],
        "b" : ["c", "e"],
        "c" : ["a", "b", "d", "e"],
        "d" : ["c"],
        "e" : ["c", "b"],
        "f" : []
      }
  </code></pre>
  
  <p>I'm using these functions to see the edges and isolated nodes:</p>
  
  <pre><code>def generate_edges(graph):
      edges = []
      for node in graph:
          for neighbour in graph[node]:
              edges.append((node, neighbour))
  
      return edges
  
  print(generate_edges(graph))
  
  
  def find_isolated_nodes(graph):
      """ returns a list of isolated nodes. """
      isolated = []
      for node in graph:
          if not graph[node]:
              isolated += node
      return isolated
  
  print(find_isolated_nodes(graph))
  </code></pre>
  
  <p>And this one to find the paths:</p>
  
  <pre><code>def find_all_paths(self, start_vertex, end_vertex, path=[]):
  """ find all paths from start_vertex to
      end_vertex in graph """
  graph = self.__graph_dict
  path = path + [start_vertex]
  if start_vertex == end_vertex:
      return [path]
  if start_vertex not in graph:
      return []
  paths = []
  for vertex in graph[start_vertex]:
      if vertex not in path:
          extended_paths = self.find_all_paths(vertex,
                                               end_vertex,
                                               path)
          for p in extended_paths:
              paths.append(p)
  return paths
  </code></pre>
  
  <p>What I need is to find a tree as a random solution so I can change it until is the biggest possible one in the graph I have.</p>
  
  <p>What could be the best way to do that? Thank you.</p>