title: Python: DFS Optimised Algorithm?
body: <p>I just implemented DFS on Python; however, I don't think this is the most optimised code possible due to the for loop on the third to last line. I know that this DFS works; however, is it optimised? The graph URL is attached below, as well as the code.</p>
  
  <pre><code>graphx=[[1, 1, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 1, 0], [0, 0, 1, 1, 0, 0, 0, 0], [0, 0, 1, 1, 1, 0, 1, 0], [0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 1, 1], [0, 1, 0, 1, 0, 1, 1, 0], [0, 0, 0, 0, 0, 1, 0, 1]]
  visited=[False]*len(graphx[0])
  stack=[]
  
  def dfs(graphx, a):
      stack.append(a)
      while len(stack)!=0:
          v=stack.pop()
          if visited[v]==False:
              visited[v]=True
              print(v)
              for w in range(len(graphx[0])):
                  if graphx[v][w]!=0:
                      stack.append(w)
  </code></pre>
  
  <p>Graph: <a href="http://i.imgur.com/BvBUdhP.png" rel="nofollow">http://i.imgur.com/BvBUdhP.png</a></p>
  
  <p>Somebody said this was O(n^2) time, which is very bad. How to optimise?</p>
  
  <p>Edit: Is this BFS corect, based on an answer for the original DFS?</p>
  
  <pre><code>def bfs(G, start):
      """Perform bfs on adjacency list of graph
      G: Adjacency list representation of graph.
      start: Index of start node.
      """
      visited = [False] * len(G)
      queue = []
      queue.append(start)
      while queue:
          v = queue.pop()
          if not visited[v]:
              visited[v] = True
              print(v)
              for neighbor in G[v]:
                  queue.insert(0, neighbor)
  </code></pre>