Depth-First Search and Related Algorithms

Depth First Search (DFS)

Definition

• Depth First Search (DFS): A recursive algorithm used to search all vertices of a graph or tree data structure.

  • Traversal: Refers to visiting all nodes within a graph.

Algorithm Overview

• DFS starts at the root node (or any arbitrary node in graphs) and explores as far as possible along each branch before backtracking.

Time and Space Complexity

• The time complexity of DFS is:
  O(|V| + |E|)

  • Where:

  • |V| = number of vertices

  • |E| = number of edges

  • This complexity is linear relative to the graph's size.

• The space complexity in the worst case is:
  O(|V|)

  • This space is used to maintain the stack of vertices on the current path and to keep track of already visited vertices.

Application Domains

• In applications like artificial intelligence or web crawling, the graph may be too large or infinite, leading DFS to only search within a limited depth.

DFS Approach

Basic Steps

1. Start at the root node or an arbitrary node.

2. Mark the node as visited.

3. Move to an adjacent unmarked node.

4. Repeat until no unmarked adjacent nodes are available.

5. Backtrack and explore any other unmarked adjacent nodes.

6. Print the nodes in the path.

Recursive Nature

• DFS employs backtracking to ensure all nodes are explored:

  • Backtrack: If no further nodes in the current path, revert to previous nodes to explore unvisited ones.

• To implement this, a stack is utilized:

  1. Pick a starting node and push its adjacent nodes onto the stack.

  2. Pop a node from the stack to select the next node to visit.

  3. Push its adjacent nodes onto the stack.

  4. Continue until the stack is empty, marking nodes as visited to prevent infinite loops.

Standard DFS Implementation

• Each vertex is categorized as:

  1. Visited

  2. Not Visited

• Steps include:

  1. Place a vertex on top of a stack.

  2. Take the top item from the stack, adding it to the visited list.

  3. List its adjacent vertices not in the visited list and push them onto the stack.

  4. Repeat until the stack is empty.

Example of DFS Execution

• Starting with an undirected graph with 5 vertices:

  1. Begin at vertex 0, adding it to the visited list and its adjacent vertices to the stack.

  2. Visit elements sequentially based on their stack positions (next is 1, then 2).

  3. Continue until all connected vertices are exhausted or visited.

Applications of DFS

• Unweighted Graphs: Creates a minimum spanning tree based on the shortest path tree.

• Cycle Detection: Allows detection of cycles within a graph.

• Pathfinding: Can find paths between two vertices.

• Topological Sorting: Useful for job scheduling based on dependencies.

• Finding Strongly Connected Components: Identifies clusters where paths exists between every pair of vertices.

• Handling Infinite Graphs: Prevents endless cycles that lead to unvisited nodes.

Breadth First Search (BFS)

Definition

• Breadth-First Search (BFS): An algorithm for searching tree data structures to find a node that fulfills a specific property.

  • Starts at the root node and explores all nodes at the current depth before moving deeper.

Memory Usage

• BFS typically requires additional memory, often implemented using a queue to track newly discovered child nodes.

Practical Example

• Comparing COVID-19 spread with BFS, where each infected node (person) represents a graph node, and the queue tracks newly infected individuals.

Applications of BFS

• Peer-to-Peer Networks: Used in networking applications such as BitTorrent.

• Search Engine Crawlers: Crucial for building indexes by finding links on a source page.

• GPS Navigation: Locates neighboring locations effectively.

• Packet Broadcasting: Efficient broadcast strategies in buffer systems.

Complexity of BFS

• Time Complexity:
  O(|V| + |E|)

• Space Complexity:
  O(|V|)

• The required space varies based on the graph representation and additional data structures used.

A Standard BFS Implementation

1. Initialize a queue and put a root vertex at its back.

2. Process each vertex by visiting and marking them as visited.

3. Check each vertex’s adjacent nodes, adding unvisited ones to the back of the queue.

4. Continue until the queue is empty.

Example of BFS Execution

• Starting from vertex 0, the algorithm visits vertices in breadth-first manner, marking nodes as visited and queuing up adjacent nodes sequentially.

Dijkstra's Algorithm

Definition

• Dijkstra's Algorithm: A method for finding the shortest path between two vertices in a weighted graph.

Key Principle

• The shortest path between any two vertices respects subpath properties, such as a subpath being a shortest path.

Steps of Dijkstra's Algorithm

1. Begin with a weighted graph.

2. Assign infinite path lengths to all vertices except the source.

3. Apply the greedy method to explore neighboring vertices and update path lengths.

4. Avoid extending paths that exceed already calculated lengths.

Complexity of Dijkstra's Algorithm

• Time Complexity:
  O(E imes ext{log} V)

  • Where E = number of edges, V = number of vertices.

• Space Complexity:
  O(V)

Applications of Dijkstra's Algorithm

• Finding optimal paths in various scenarios: social networks, telecommunications, and mapping systems.

Review of Dijkstra's Algorithm

• Mechanism to determine shortest distances, utilizing a priority queue to trace optimal paths. It helps efficiently calculate minimum distances from chosen vertices within supplied weighted graphs.