Graph (abstract data type)

Breadth-First Search (BFS) and Depth-First Search (DFS) are fundamental graph traversal algorithms used to explore nodes and edges in a graph.

BFS explores the graph level by level, starting from a given node. It uses a queue to keep track of the nodes to be explored next. As it visits each node, it adds its unvisited neighbors to the queue. The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because BFS visits each vertex once and each edge once.

DFS explores the graph by going as deep as possible along each branch before backtracking. It uses a stack (either explicitly or through recursion) to keep track of the nodes to be explored next. Similar to BFS, DFS visits each vertex once and each edge once. Therefore, the time complexity of DFS is also O(V + E).