What is a Graph

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices, and edges are lines or arcs that connect any two nodes in the graph.
More formally, a graph is a finite set of vertices(or nodes) and a set of edges that connect a pair of nodes.

Important Graph Algorithms

• Breadth-First Search (BFS).
• Depth-First Search (DFS).
• Topological Sorting.
• Cycle Detection in Undirected Graph.
• Cycle Detection in Directed Graph.
• Kahn's Algorithm.
• Graph Bipartite check.
• Dijkstra's Algorithm.
• Bellman-Ford Algorithm.
• Prims Algorithm.
• Disjoint Set.
• Kruskal's Algorithm.
• Kosaraju's Algorithm.

Breadth-First Search (BFS)

Breadth-First Search algorithm is a graph traversal algorithm that starts traversing the graph from the root node and goes through all its neighboring nodes. We select the nearest node and visit all neighbors. We can consider any node in the graph as the root node.
Consider a graph given below, with node 0 as the root node. In the BFS algorithm, we will use a queue, a First In First Out(FIFO) data structure, and enqueue our root node. We will also maintain a boolean array to keep track of the nodes which are visited, unvisited because we don't want to traverse a node that visited before. We will be traversing all the nodes given in the graph and try to apply the BFS algorithm to each node. These are the initial setup we do for the BFS algorithm.

Until our queue is empty, repeat the following step:
Remove the node from the top of the queue.
Traverse through the neighbors of the removed node.
If the current neighbor is not visited, mark it as visited and add it to the queue.

Time Complexity

• We are traversing through all the nodes and edges. So time complexity will be O(V + E) where V = vertices or node, E = edges.

• We use a visited array, queue, and an adjacency list for the graph. So the space complexity will be O(V) + O(V) + O(V + E). (Ignoring the space for the final result list).

Code

Originally Published On LinkedIn Newsletter : LinkedIn Newsletter

Github Link