Traversal

Traversal refers to the process of visiting all vertices(nodes) in a graph in a systematic way. There are primarily 2 ways for traversing graph, each with different applications and characteristics.

DFS

DFS explores by going down as deep as possible starting from a node and the backtracks to the next branch once it is done with the processing of the current branch. This algorithm makes use of either an explicit stack data structure (iteratively) or the call stack (recursive). Main applications fo DFS are

• Detecting cycles in a graph
• Topological sorting
• Finding strongly connected components
• Path finding in puzzles

How DFS works?

• Start at a choosen vertex
• Mark it as visited
• Explore an unvisited adjacent vertex
• Backtrack to the previous vertex and continue

BFS

BFS explores a graph level by level, visiting all vertices at the current depth before moving to vertices at the next depth level. It makes use of queue. Main applications of BFS are

• Finding shortest path in unweighted graphs
• Level-order Traversal
• Web Crawling

How BFS works?

• Start at a choosen vertex and add it to a queue
• While the queue is not empty:
  • Remove a vertex from the front of the queue
  • Mark it as visited
  • Add all unvisited adjacent vertices to the back of the queue

1972. Find if Path Exists in Graph

Easy3

797. All Paths From Source to TargetMedium

116. Populating Next Right Pointers in Each NodeMedium

323. Number of Connected Components in an Undirected GraphMedium

1972. Find if Path Exists in Graph

DFS - Recursive

Interactive Visualization

Python

class Solution:
    def validPath(
        self, n: int, edges: List[List[int]], source: int, destination: int
    ) -> bool:
        graph = defaultdict(list)

        for src, dst in edges:
            graph[src].append(dst)
            graph[dst].append(src)

        return self.helper(graph, source, destination, set())

    def helper(self, graph, node, target, visited):

        if node == target:
            return True

        if node in visited:
            return False

        visited.add(node)

        for neighbor in graph[node]:
            if self.helper(graph, neighbor, target, visited):
                return True

        return False

DFS - Iterative

Interactive Visualization

Python

class Solution:
    def validPath(
        self, n: int, edges: List[List[int]], source: int, destination: int
    ) -> bool:
        graph = defaultdict(list)

        for src, dst in edges:
            graph[src].append(dst)
            graph[dst].append(src)

        stack = [source]
        visited = set()

        while stack:
            node = stack.pop()

            if node == destination:
                return True

            if node in visited:
                continue

            visited.add(node)

            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

        return False

BFS - Iterative

Interactive Visualization

Python

class Solution:
    def validPath(
        self, n: int, edges: List[List[int]], source: int, destination: int
    ) -> bool:
        graph = defaultdict(list)
        for src, dst in edges:
            graph[src].append(dst)
            graph[dst].append(src)

        queue = deque([source])
        visited = set()

        while queue:
            node = queue.popleft()
            if node == destination:
                return True

            if node in visited:
                continue

            visited.add(node)

            for neighbor in graph[node]:
                queue.append(neighbor)

        return False

---