# Why does my BFS/DFS run so slowly?

My solutions (BFS/DFS) passed a few simple test cases, but for more difficult cases, the time limited has been exceeded. I was wondering if there is any way to fix it so that it may run faster?

PS: I know the class here does nothing and I don’t like it. It is just the way the website presents the solution.

BFS

``````class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
nodes_left = list(range(n))
def bfs(node, edges):
visited = {node}
queue = [node]
while queue:
m = queue.pop(0)
nodes_left.remove(m)
nbr = [i for i in range(n) if [m, i] in edges or [i, m] in edges]
for i in nbr:
if i not in visited:
queue += [i]

res = 0
while nodes_left:
res += 1
node = nodes_left
bfs(node, edges)

return res
``````

DFS

``````class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
nodes_left = list(range(n))
def dfs(node, edges, visited):
if node not in visited:
nodes_left.remove(node)
nbr = [i for i in range(n) if [node, i] in edges or [i, node] in edges]

for i in nbr:
dfs(i, edges, visited)

res = 0
while nodes_left:
res += 1
node = nodes_left
visited = set()
dfs(node, edges, visited)

return res

``````

The following BFS solution (which is from here) runs much faster

``````class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
dist = collections.defaultdict(list)
for source, target in edges:
dist[source].append(target)
dist[target].append(source)
count = 0
visited=set()
queue = collections.deque()
for x in range(n):
if x in visited:
continue
queue.append(x)
while queue:
source=queue.popleft()
if source in visited:
continue
for target in dist[source]:
queue.append(target)
count+=1
return count

``````

Here are some thoughts.

Consider using the `collections.deque` data structure. A list is not an efficient way to implement a queue. The reason is that list elements are stored contiguously in memory (simplifying a bit, since the Python list implementation is smarter than that). Basically, when you do `queue.pop(0)`, this takes all elements from `queue` and moves them one position to the left in order to resize the list, so it has a hidden cost that is proportional to the current size of the queue.

Same kind of problem here. `nodes_left` is a list. A `.remove()` operation in a list searches the list elements one by one, and once it has found a matching element, moves all the other elements to the right. This costs a time proportional to the length of `nodes_left` (i.e., `n`). Use a set instead; sets don’t have order, but removing an element from a set is typically done in constant time rather than time proportional to the size of the set.

And same here. The check `[m, i] in edges` can potentially do `len(edges)` operations. The underlying problem is that your graph structure is not designed for efficient access. Instead, try using, for example, a list of the vertices that each vertex is connected to, like the efficient solution is doing with

``````nodes_left = set(range(m))
``````

Is there any good way to access one of the elements?
I did this for a list.

``````node = nodes_left
``````

This is what I think I can do for a set:

``````for node in nodes_left:
break
``````

Yes: `nodes_left.pop()`, which removes an arbitrary element and returns it.

Thanks. Another relevant question:
Is there any way to get one arbitrary element from a set without removing it? Following your way, I would do:

``````element = s.pop() # s is the set
`s.pop()` is often what you want to use, but if it turns out more convenient not to remove the element at the same time, you can do `elt = next(iter(s))`, which is equivalent to the more verbose (and confusing) version you already proposed: `for elt in s: break`. Essentially, `for elt in s` first does `internal_iterator = iter(s)`, and then repeatedly calls `next(internal_iterator)` to get the successive elements (until that raises the exception `StopIteration`, indicating that the iterator is exhausted).