Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It's implemented using recursion or a stack.

def dfs(graph, node, visited):
    if node not in visited:
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

Applications

1. Maze Solving: DFS can find a path through a maze by exploring all possible routes.
2. Connected Componants: Identifying all nodes reachable from a given node.
3. Topological Sorting: Arranging nodes in a linear order where each node comes before its successors.

Breadth-First Search (BFS)

BFS explores all neighbors at the presant depth before moving to nodes at the next level. It uses a queue for implementation.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                queue.append(neighbor)

Applications

1. Shortest Path: In unweighted graphs, BFS finds the shortest path between two nodes.
2. Web Crawling: BFS is used to index web pages level by level.
3. Social Networking: Finding people within a certain distance in a network.

A* Search Algorithm

A* combines BFS with heuristics to find the shortest path more efficiently. It uses a priority queue to select the most promising node.

import heapq

def astar(graph, start, goal, heuristic):
    open_set = []
    heapq.heappush(open_set, (0, start))
    came_from = {}
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0
    f_score = {node: float('inf') for node in graph}
    f_score[start] = heuristic(start, goal)

    while open_set:
        current = heapq.heappop(open_set)[1]
        if current == goal:
            return reconstruct_path(came_from, current)
        for neighbor in graph[current]:
            tentative_g = g_score[current] + 1
            if tentative_g < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score[neighbor], neighbor))
    return None

Applications

1. Pathfinding: Used in games and robotics for effciient navigation.
2. Puzzle Solving: Solving puzzles like the 8-puzzle with minimal moves.
3. Route Planning: Finding the quickest route in transportation networks.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a start node to all other nodes in a weighted graph with non-negative weights.

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]
    while heap:
        current_dist, current_node = heapq.heappop(heap)
        if current_dist > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    return distances

Applications

1. Network Routing: Finding the shortest path in computer networks.
2. Traffic Management: Optimizing traffic flow in road networks.
3. Flight Scheduling: Determining the most efficient flight paths.

Jump Point Search (JPS)

JPS optimizes A* for uniform-cost grids by skipping nodes that don't affect the path.

def jump_point_search(grid, start, goal):
    open_set = [start]
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}
    while open_set:
        current = min(open_set, key=lambda x: f_score[x])
        if current == goal:
            return reconstruct_path(came_from, current)
        open_set.remove(current)
        for neighbor in prune_neighbors(current, grid, goal):
            tentative_g = g_score[current] + distance(current, neighbor)
            if tentative_g < g_score.get(neighbor, float('inf')):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
                if neighbor not in open_set:
                    open_set.append(neighbor)
    return None

Applications

1. Video Games: Efficient pathfinding in grid-based games.
2. Robotics: Navigation in grid-like environments.
3. Geographic Information Systems: Finding paths in raster maps.