Optimizing BFS code to find connected components in a graph

Question

I am writing a Python code to find the connected components of a graph using BFS. The code works but takes a long time to run. Please suggest possible optimizations of my code.

The graph is stored as a dictionary g. For example, g could be {'a':['b','c'], 'b':['a'], c:['a','d'], 'd':['c']}. The list nodes contain all possible nodes in the graph.

        seen = []
        result = []   #List of Lists to hold the final result 
        for i in nodes:
            if i not in seen:
                comp = []
                level = [i]
                while level:
                    for j in level: 
                        seen.append(j)
                        comp.append(j)
                    q = []
                    for j in level:
                        for k in g[j]: 
                            if k not in seen: q.append(k)
                    level = q
                result.append(comp) 

Answer 1

You are asking for a performance review - so initially I'll miss the ball a bit. however, I'd just strongly argue against using one letter variable names. Naming conventions are one of the most important things in code in my opinion. You might argue that you are "just writing some code for studies" - but as soon as you wanted to share it here other people are reading your code, for instance, and now readability matters. I'd argue it mattered when you looked at it yourself too.

So I'd rename:

• i to node.
• comp to components.
• j to leaf potentially. That is what it is right? then I'd rename level to leaves too.
• q I would call new_leaves (or new_level)
• g should be graph.
• k to connected_node.

That would change the code to:

def bfs(graph, nodes):
    seen = []
    result = []   #List of Lists to hold the final result 
    for node in nodes:
        if node not in seen:
            components = []
            leaves = [node]
            while leaves:
                for leaf in leaves: 
                    seen.append(leaf)
                    components.append(leaf)
                new_leaves = []
                for leaf in leaves:
                    for connected_node in graph[leaf]: 
                        if connected_node not in seen: new_leaves.append(connected_node)
                leaves = new_leaves
            result.append(components) 

Then I would use set throughout, as @vnp mentions. You don't want duplicates. you don't care about orders. Sets are also more optimized in general.

So let's change that.

def bfs(graph, nodes):
    seen = set()
    result = []   #List of Lists to hold the final result 
    for node in nodes:
        if node not in seen:
            components = set()
            leaves = set([node])
            while leaves:
                for leaf in leaves: 
                    seen.add(leaf)
                    components.add(leaf)
                new_leaves = set()
                for leaf in leaves:
                    for connected_node in g[leaf]: 
                        if connected_node not in seen: new_leaves.add(connected_node)
                leaves = new_leaves
            result.append(components) 

    return result

At this point, you will also see that something weird is happening - just from reading it. If you are doing BFS, why are you overriding the leaves? You could just use a FIFO data structure, which would enforce that the first thing you get in is the first that gets popped. Similarly, you are doing two iterations of the same array (now set). no reason for that. I've chosen to use a list. you could also just use the queue module. I was a bit lazy.

def bfs(graph, nodes):
    seen = set()
    result = []   #List of Lists to hold the final result 
    for node in nodes:
        if node not in seen:
            components = set()
            leaves = [node]
            while leaves:
                leaf = leaves.pop()
                seen.add(leaf)
                components.add(leaf)
                for connected_node in graph[leaf]: 
                    if connected_node not in seen: leaves.append(connected_node)
            result.append(components) 

    return result

Something weird is also going on - if I understand your question correctly, then you'd probably want to reset the components after each flow, so it won't just continue growing. But without test cases, it is a bit difficult. I'd recommend you write some unit tests, and test different corner cases. Tests are also a great way to communicate the intent of code - again great for readability. I've written a single test based on the example you provide. If you write more it might be easier to help you. Regarding performance, BFS is in general O(E+V), and you cannot do much for that, but you should be able to do some optimizations. I'd need to understand the code better and verify that I'm not breaking anything. As mentioned, here is the first test case to get you started

def bfs(graph, nodes):
    seen = set()
    result = []   #List of Lists to hold the final result 
    for node in nodes:
        if node not in seen:
            components = set()
            leaves = [node]
            while leaves:
                leaf = leaves.pop()
                seen.add(leaf)
                components.add(leaf)
                for connected_node in graph[leaf]: 
                    if connected_node not in seen: leaves.append(connected_node)
            result.append(components) 
    return result;


def test_simple_case():
    output = bfs({'a':['b','c'], 'b':['a'], 'c':['a','d'], 'd':['c']}, ['a','b','c','d'])

    assert output == [set(['a', 'b', 'c', 'd'])]

If you install pytest you can run this out of the box.

Hope this moves you in the right direction, even if I didn't have a direct optimization. I'd wonder if this is still faster, but you can provide a bigger dataset in a test to help stress-test it :)