title: How could I optimise this Python code of graph bfs/dfs transversal algorithms to deal with with large graphs?
body: <p>I would want to optimise this code bellow to make transversals in large graphs and respect the time constraints of processing where this algorithm will run. Do you have any clues, if necessary? Could I use any python embedded optimised data structure here? Every clue and knowledge is welcome, folks!</p>
  
  <pre><code>import sys
  import collections
  
  class Graph:
      def __init__(self, amount_vertice):
          self.vertice_list = []
          self.amount_vertice = amount_vertice
          # buffered previous connect components the origin in index vertex. Each entry contains (dfs and bfs) according to format [dfs, bfs]
          self.buffered_connect_component = [[[], []] for node in xrange(amount_vertice)]
          self.visited_vertice = [0 for node in xrange(amount_vertice)]
          for vertex in xrange(amount_vertice):
              line = sys.stdin.readline()
              self.vertice_list.append(map(lambda x: int(x), line.split()[2:]))
  </code></pre>
  
  <p>The portion of code above shows the initialization of my graph data structure according to the context specified:</p>
  
  <ul>
  <li>self.vertice_list is the adjacency lists of the graph</li>
  <li>self.amount_vertice is the amount of vertices the graph has.</li>
  <li>self.buffered_connected_component is the list of connected components retrieved before, just to speed up the code and avoid retrieve again in case of same connected component be asked. Each entry contains a connected component, according to dfs and bfs graph transversal algorithms.</li>
  <li><pre><code>def print_dfs(self, origin_vertex, number_query):
      path = [origin_vertex]
      while path:
          next_node = path.pop()
          if self.visited_vertice[next_node - 1] != number_query:
              self.visited_vertice[next_node - 1] = number_query
              self.buffered_connect_component[origin_vertex - 1][0].append(str(next_node))
              for candidate_next_node in self.vertice_list[next_node - 1][::-1]:
                  path.append(candidate_next_node)
  </code></pre></li>
  </ul>
  
  <p>The function above shows the famous Deep First Search Graph`s Algortihm implementation. Parameter origin_vertex is the vertex where the algorithm will begin to run, and number_query is just a parameter given from the context.</p>
  
  <pre><code>    def print_bfs(self, origin_vertex, number_query):
          path = collections.deque([origin_vertex])
          while path:
              next_node = path.popleft()
              if self.visited_vertice[next_node - 1] != number_query:
                  self.visited_vertice[next_node - 1] = number_query
                  self.buffered_connect_component[origin_vertex - 1][1].append(str(next_node))
                  for candidate_next_node in self.vertice_list[next_node - 1]:
                      path.append(candidate_next_node)
  </code></pre>
  
  <p>And for last, above the function that implements Breath First Search Graph`s Algorithm, and parameters similar to the bfs function.</p>