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

Question

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.

Answer 1

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