DFS Depth First Search on Graph in DSA Typescript - Build from Scratch

DFS Depth First Search on Graph

📖 Scenario: Imagine you have a map of cities connected by roads. You want to explore all cities starting from one city by traveling along the roads. This is like exploring a graph using Depth First Search (DFS).

🎯 Goal: You will build a simple graph using an adjacency list and write a DFS function to visit all connected cities starting from a given city.

📋 What You'll Learn

Create a graph as an adjacency list with exact cities and connections

Create a visited set to keep track of visited cities

Write a DFS function that visits cities recursively

Print the order of cities visited starting from 'A'

💡 Why This Matters

🌍 Real World

Graph traversal like DFS is used in maps, social networks, and solving puzzles by exploring connected points.

💼 Career

Understanding DFS is essential for software engineers working on algorithms, network analysis, and game development.

1

Create the graph as an adjacency list

Create a variable called graph as an object with these exact entries: 'A': ['B', 'C'], 'B': ['D'], 'C': ['E'], 'D': [], 'E': []

DSA Typescript

# Your code here

Hint

Use an object where keys are city names and values are arrays of connected cities.

2

Create a visited set to track visited cities

Create a variable called visited as a new empty Set<string>()

DSA Typescript

const graph: { [key: string]: string[] } = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['E'],
  'D': [],
  'E': []
};

// Your code here

Hint

Use new Set<string>() to create an empty set for visited cities.

3

Write the DFS function to visit cities recursively

Write a function called dfs that takes a city: string. Inside, add city to visited. Then use for loop with neighbor over graph[city]. If neighbor is not in visited, call dfs(neighbor) recursively.

DSA Typescript

const graph: { [key: string]: string[] } = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['E'],
  'D': [],
  'E': []
};

const visited: Set = new Set();

// Your code here

Hint

Use recursion to visit neighbors that are not yet visited.

4

Print the order of cities visited starting from 'A'

Call dfs('A') to start DFS from city 'A'. Then print the visited cities as an array using console.log(Array.from(visited))

DSA Typescript

const graph: { [key: string]: string[] } = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['E'],
  'D': [],
  'E': []
};

const visited: Set = new Set();

function dfs(city: string): void {
  visited.add(city);
  for (const neighbor of graph[city]) {
    if (!visited.has(neighbor)) {
      dfs(neighbor);
    }
  }
}

// Your code here

Hint

Call dfs('A') and then print the visited cities as an array.