Why does my BFS/DFS run so slowly?

Python Help
1

Question: Number of Connected Components in an Undirected Graph

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:
                        visited.add(i)
                        queue += [i]
            
        res = 0
        while nodes_left:
            res += 1
            node = nodes_left[0]
            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:
                visited.add(node)
                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[0]
            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
                visited.add(source)
                for target in dist[source]:
                    queue.append(target)
            count+=1
        return count
2

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

3

Thank you for your advice. If I use a set:

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[0]

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

for node in nodes_left:
    break
4

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

5

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.add(element)

Is there a one-line, easier way?
Thanks!

6

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).