In this lesson, we will cover three fundamental graph algorithms:

• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Dijkstra's Algorithm

Each algorithm will be explained with Java code and detailed complexity analysis.

1. Breadth-First Search (BFS)

BFS is a traversal algorithm that explores the graph level by level, starting from the source node and visiting all its neighbors before moving to the next level.

Time Complexity for BFS Code

1. Initialization:

   • Queue Initialization: Initializing the queue is O(1).

2. Traversal:

   • Outer While Loop:
     • The loop runs as long as the queue is not empty. Each vertex is enqueued and dequeued exactly once.
     • The poll() operation is O(1) and runs O(V) times, where V is the number of vertices.
   • Inner For Loop:
     • Iterates over all adjacent nodes of currentNode. The total number of iterations across all for loops (over all vertices) is O(E), where E is the number of edges.
     • The queue.add() operation for adding nodes to the queue is O(1) and is performed at most O(V + E) times.

Overall Time Complexity:

• The algorithm visits each vertex and each edge exactly once, resulting in: O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Space Complexity for BFS Code

1. Visited Array:

   • The visited array requires O(V) space to store the visited status for each vertex.

2. Queue:

   • The maximum number of vertices stored in the queue at any time is O(V) in the worst case (e.g., when all vertices are at a single level in the graph).
   • Space used by the queue: O(V).

Overall Space Complexity:

• The space complexity is: O(V) for the visited array and queue.

2. Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking, making it useful for pathfinding and connected component analysis.

Time Complexity for DFS Code

1. Traversal:
   • Recursive Calls:
     • Each vertex is visited once, marking it as visited and processing its adjacent vertices.
     • For each vertex node, the adjacent vertices are iterated over, resulting in a time complexity proportional to the number of edges, O(E).
   • Recursive Call Stack:
     • Each recursive call processes one vertex, and the call stack grows based on the depth of the recursion.

Overall Time Complexity:

• The total time complexity for DFS is: O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Space Complexity for DFS Code

1. Visited Array:
   • The visited array requires O(V) space to keep track of whether each vertex has been visited.
2. Recursive Call Stack:
   • Depth of Recursion:
     • For a balanced graph, the maximum depth of the recursion is O(\log V).
     • In the worst case (e.g., a graph that behaves like a linked list), the depth of the recursion could be O(V).

Overall Space Complexity:

• The space complexity consists of:
  • O(V) for the visited array.
  • O(V) for the recursion stack in the worst case.

3. Dijkstra's Algorithm

Dijkstra's Algorithm is used to find the shortest paths from a single source node to all other nodes in a weighted graph with non-negative weights.

Time Complexity for Dijkstra's Algorithm Code

1. Initialization:

   • Distances Array: Initializing the distances array takes O(V), where V is the number of vertices.
   • Priority Queue Initialization: Adding the starting node to the priority queue is O(1).

2. While Loop:

   • The main loop runs as long as the priority queue is not empty. Each vertex is added to and removed from the priority queue once.
   • Priority Queue Operations:
     • Polling: Removing an element from the queue takes O(\log V).
     • Adding/Updating: Inserting or updating an element in the queue also takes O(\log V).
   • Number of Priority Queue Operations: Each vertex and its edges are processed once, resulting in O((V + E) \log V) operations. Here, E represents the number of edges in the graph.

3. For Loop (Iterating Over Adjacent Nodes):

   • Each edge is relaxed at most once. The sum of iterations over all adjacent nodes across the entire graph is O(E).
   • Checking and Updating Distances: Each operation for checking and updating distances runs in O(1), but adding to the queue takes O(\log V).

Overall Time Complexity:

• The total time complexity is: O((V + E) \log V)

  This is due to the use of a priority queue and processing each edge and vertex.

Space Complexity for Dijkstra's Algorithm Code

1. Distances Array:

   • Requires O(V) space to store the shortest distances for each vertex.

2. Priority Queue:

   • Can hold up to O(V) elements at most, leading to O(V) space in the worst case.

Overall Space Complexity:

• The space complexity consists of:
  • O(V) for the distances array.
  • O(V) for the priority queue.