CODEWITHSUNDEEP
breadth-first-searchadjacency-listadjacency-matrix
John Doe
John Doe

Reputation: 185

How is BFS on an adjacency matrix list O(m+n)?

I'm trying to figure out how a BFS is O(m+n), where n is the number of vertices and m is the number of edges.

The algorithm is:

public void bfs()
{
    //BFS uses Queue data structure
    Queue q=new LinkedList();
    q.add(this.rootNode);
    printNode(this.rootNode);
    rootNode.visited=true;
    while(!q.isEmpty())
    {
        Node n=(Node)q.remove();
        Node child=null;
        while((child=getUnvisitedChildNode(n))!=null)
        {
            child.visited=true;
            printNode(child);
            q.add(child);
        }
    }
    //Clear visited property of nodes
    clearNodes();
}
//

In an adjacency list, we store the vertices in an array/hash table, and a linked list of the edges that each vertex forms with other vertices.

My main question is this: how do we implement get unvisited child node? It's clear that you mark nodes as visited, but when traversing, you go through all the linked lists, so you count every edge twice, so the complexity is O(2m+n) right? Does that just get rounded down to O(m+n)?

Also, can we employ a similar strategy for an adjacency matrix? If I'm given an matrix of size n x n, and I want to know if a specific element exists, can I do a BFS to figure that out?

Thanks.

Upvotes: 2

Views: 3752

Answers (1)

zvrba
zvrba

Reputation: 24546

The O-notation "reduces" multiplicative constants to 1, so O(2m+n) gets reduced to O(m+n).

Upvotes: 3

Related Questions