Breadth First Search Algorithm

in Study on C/C++, Algorithm

  • Reviewing what I studied, how this work will be explained as well.

Graph Traversal

When we have a graph with nodes and edges, the problem of starting from a specific node and visiting all other nodes is called a Graph Traversal Problem or Graph Search. This traversal problem can be properly stated as:

Given a graph G = <V, E>, starting from a specific node s, visit all nodes (vertices) v in V.

BFS

BFS starts by expanding a frontier from the starting point (frontier: nodes previously visited). It then visits adjacent nodes from the current node.

BFS visits child nodes before grandchild nodes, making it equivalent to Level Order Traversal in trees (Root -> Left -> Right).

It is typically implemented using a Queue. The algorithm starts by placing the starting node in the queue, then repeatedly removes a node from the queue, checks all adjacent nodes, marks unvisited nodes as visited, and adds them to the queue. This process continues until the queue is empty.

Implementation

This implementation made an assumption that we are given adjacent link list.

bool visited[9];
vector<int> graph[9];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while(!q.empty()) {
        int node = q.front()
        q.pop();

        for(int i = 0; i < graph[node]; i++){
            int adjacentNode = graph[node][i];
            if (!visited(adjacentNode)) {
                q.push(adjacentNode);
                vistied[adjacentNode] = true;
            }
        }
    }
}

Time Complexity

  • The Time complexity would be O(V + E). where V is the Vertex, E is the Edge.

Resource