Search in Trees & Graphs

Introduction

Searching in trees and graphs is a fundamental operation used in many applications such as pathfinding, network analysis, and hierarchical data processing. The most common search techniques include Depth-First Search (DFS) and Breadth-First Search (BFS).

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking, which is suitable for pathfinding and connectivity checking.

DFS Algorithm

• Start from the root or any arbitrary node.
• Mark the node as visited and explore each unvisited adjacent node recursively.
• Backtrack when no unvisited adjacent nodes remain.

DFS Python Code Example

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=' ')
    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Usage
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs(graph, 'A')

Breadth-First Search (BFS)

BFS explores neighbor nodes at the current depth before moving on to nodes at the next depth level, useful for shortest path finding in unweighted graphs.

BFS Algorithm

• Initialize a queue and mark the start node as visited.
• Dequeue a node and enqueue all its unvisited neighbors.
• Repeat until the queue is empty.

BFS Python Code Example

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=' ')

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Usage
bfs(graph, 'A')

Graph Search Strategies

Graph search algorithms differ from tree search as they handle cycles and repeated states by maintaining visited or explored sets to avoid infinite loops and redundant processing.

• Graph Search keeps track of all explored nodes to prevent re-expansion.
• Tree-Like Search may revisit nodes multiple times due to multiple paths.
• Appropriate use of visited sets optimizes performance in complex graphs.

Applications

• Pathfinding in maps and games.
• Network connectivity and flow analysis.
• Detecting cycles or dependencies.
• Solving puzzles and exploring state spaces.