Rocket Academy Bootcamp
  • 🚀Welcome to Bootcamp!
  • 🛠️Logistics
    • Course Schedules
    • Course Methodology
    • Required Software
    • LinkedIn Education Badge
  • 📚General Reference
    • Naming, Casing, and Commenting Conventions
    • VS Code Tips
    • Recommended Resources
  • 🪨0: Foundations
    • 0.1: Command Line
    • 0.2: Git
      • 0.2.1: Branches
    • 0.3: GitHub
      • 0.3.1: Pull Requests
    • 0.4: JavaScript
      • 0.4.1: ES6
      • 0.4.2: Common Syntax
      • 0.4.3: Reference vs Value
      • 0.4.4: Classes
      • 0.4.5: Destructuring and Spread Operator
      • 0.4.6: Promises
        • 0.4.6.1: Async Await
    • 0.5: Node.js
      • 0.5.1: Node Modules
      • 0.5.2: NPM
      • 0.5.3: Nodemon
  • 🖼️1: Frontend
    • 1.1: HTML
    • 1.2: CSS
      • 1.2.1: Layout
    • 1.3: React
      • Styling in ReactJs
      • Using Styling Libraries with React
      • React Deployment
    • 1.E: Exercises
      • 1.E.1: Recipe Site
      • 1.E.2: Portfolio Page
      • 1.E.3: World Clock
      • 1.E.4: High Card
      • 1.E.5: Guess The Word
    • 1.P: Frontend App
  • 🏭2: Full Stack
    • 2.1: Internet 101
      • 2.1.1: Chrome DevTools Network Panel
      • 2.1.2: HTTP Requests and Responses
    • 2.2: Advanced React
      • 2.2.1: AJAX
      • 2.2.2: React Router
      • 2.2.3: useContext
      • 2.2.4: useReducer
      • 2.2.5: Environmental Variables
      • 2.2.6: React useMemo - useCallback
    • 2.3: Firebase
      • 2.3.1: Firebase Realtime Database
      • 2.3.2: Firebase Storage
      • 2.3.3: Firebase Authentication
      • 2.3.4: Firebase Hosting
      • 2.3.5: Firebase Techniques
    • 2.E: Exercises
      • 2.E.1: Weather App
      • 2.E.2: Instagram Chat
      • 2.E.3: Instagram Posts
      • 2.E.4: Instagram Auth
      • 2.E.5: Instagram Routes
    • 2.P: Full-Stack App (Firebase)
  • 🤖3: Backend
    • 3.1: Express.js
      • 3.1.1 : MVC
    • 3.2: SQL
      • 3.2.1: SQL 1-M Relationships
      • 3.2.2: SQL M-M Relationships
      • 3.2.3: SQL Schema Design
      • 3.2.4: Advanced SQL Concepts
      • 3.2.5: SQL - Express
      • 3.2.6: DBeaver
    • 3.3: Sequelize
      • 3.3.1: Sequelize One-To-Many (1-M) Relationships
      • 3.3.2: Sequelize Many-To-Many (M-M) Relationships
      • 3.3.3: Advanced Sequelize Concepts
      • 3.3.4 Database Design
    • 3.4: Authentication
      • 3.4.1: JWT App
    • 3.5: Application Deployment
    • 3.E: Exercises
      • 3.E.1: Bigfoot JSON
      • 3.E.2: Bigfoot SQL
      • 3.E.3: Bigfoot SQL 1-M
      • 3.E.4: Bigfoot SQL M-M
      • 3.E.5: Carousell Schema Design
      • 3.E.6: Carousell Auth
    • 3.P: Full-Stack App (Express)
  • 🏞️4: Capstone
    • 4.1: Testing
      • 4.1.1: Frontend React Testing
      • 4.1.2: Backend Expressjs Testing
    • 4.2: Continuous Integration
      • 4.2.1 Continuous Deployment (Fly.io)
      • 4.2.2: Circle Ci
    • 4.3: TypeScript
    • 4.4: Security
    • 4.5: ChatGPT for SWE
    • 4.6: Soft Skills for SWE
    • 4.P: Capstone
  • 🧮Algorithms
    • A.1: Data Structures
      • A.1.1: Arrays
        • A.1.1.1: Binary Search
        • A.1.1.2: Sliding Windows
      • A.1.2: Hash Tables
      • A.1.3: Stacks
      • A.1.4: Queues
      • A.1.5: Linked Lists
      • A.1.6: Trees
      • A.1.7: Graphs
      • A.1.8: Heaps
    • A.2: Complexity Analysis
    • A.3: Object-Oriented Programming
    • A.4: Recursion
    • A.5: Dynamic Programming
    • A.6: Bit Manipulation
    • A.7: Python
  • 💼Interview Prep
    • IP.1: Job Application Strategy
    • IP.2: Resume
    • IP.3: Portfolio
Powered by GitBook
On this page
  • Learning Objectives
  • Introduction
  • DFS and BFS for Graphs
  • DFS
  • BFS
  • Exercises
  • Pre-Class
  • Part 1
  • Part 2
  • Part 3
  • More Comfortable
  • Additional Resources
  1. Algorithms
  2. A.1: Data Structures

A.1.7: Graphs

PreviousA.1.6: TreesNextA.1.8: Heaps

Learning Objectives

  1. Graphs are used to model a wide variety of real-world problems, such as transport networks, social networks, disease networks, communication networks, website networks, e-commerce networks and more

  2. Graphs are generalised versions of trees, where edges can be directed or undirected, edges can have weights and there can be cycles

  3. DFS and BFS are the most common graph traversal algorithms, where we typically track visited nodes to avoid infinite loops

Introduction

Graphs are used to model a wide variety of real-world problems, such as transport networks, social networks, disease networks, communication networks, website networks, e-commerce networks and more. Graph theory can get complex and is the subject of entire university courses; in this submodule we will introduce the basics that are relevant for algorithm interviews.

The following video showcases the types of problems we can model and solve with graphs. We hope this excites you about the potential of graphs!

Graphs are generalised versions of trees, where edges can be directed or undirected, edges can have weights and there can be cycles. All trees are graphs but not all graphs are trees.

Directed edges are like the edges in trees, where they only point in 1 direction. These can be used to represent directed relationships such as follow requests on Instagram or Twitter.

Undirected edges are edges that connect nodes regardless of direction. These can be used to represent undirected relationships such as Facebook friendships or 2-way road networks.

Weighted edges are edges with a number associated with them. These can be used to represent metadata about connections between nodes, such as friendship scores between Facebook friends or road distances.

Graph cycles are loops within graphs. Trees have no cycles by definition, and are part of a common subset of graphs called "directed acyclic graphs", meaning graphs with directed edges and no loops.

The following video introduces the above concepts and 3 common ways of representing graphs in code: adjacency matrix, adjacency list and edge list.

DFS and BFS for Graphs

DFS and BFS are the most common graph traversal algorithms. Unlike trees, which are a type of graph with no cycles (called "acyclic" graphs), for graphs with cycles we will need to track visited nodes to avoid infinite loops.

Not all graph problems require DFS or BFS-like traversal algorithms, although many will. Some simpler graph problems can be solved by analysing edges without DFS or BFS.

DFS is generally a "simpler" algorithm because it involves recursion with no additional data structures beyond our graph. BFS requires the use of a queue to visit nodes in increasing distance order from the source node.

We would typically use DFS when we need to visit all nodes in the graph, and BFS when we wish to find the shortest path between nodes in the most efficient manner.

DFS

The following video explains the logic for DFS in graphs. Notice the use of a hash table to track which nodes have been visited to avoid cycles.

The following is DFS code for graphs in JavaScript. Notice it is similar to DFS for trees except we track visited nodes, and we reference a hash table that represents our graph to find neighbours.

// Represent graph in hash table with nodes as keys and neighbouring nodes as values
const graph = {
  a: ["b", "c"],
  b: ["d"],
  c: ["e"],
  d: ["f"],
  e: [],
  f: [],
};

// Track nodes we have visited in hash table
const visited = {};

const dfs = (currNode) => {
  // End this path if we reach visited node
  if (visited[currNode]) {
    return;
  }

  // Mark current node visited
  visited[currNode] = true;

  // Perform DFS on each neighbour
  for (const neighbour of graph[currNode]) {
    dfs(neighbour);
  }
};

// Start DFS on source node
dfs("a");

BFS

Visit each node in graph in increasing distance from source node. This is similar to the level-order tree traversal algorithm. Notice the use of a hash table to track which nodes have been visited to avoid cycles.

The following is BFS code for graphs in JavaScript. Notice it is similar to BFS for N-ary trees except we track visited nodes, and we reference a hash table that represents our graph to find neighbours.

// Represent graph in hash table with nodes as keys and neighbouring nodes as values
const graph = {
  a: ["b", "c"],
  b: ["d"],
  c: ["e"],
  d: ["f"],
  e: [],
  f: [],
};

// Track nodes we have visited in hash table
const visited = {};
// Track upcoming nodes to visit in a queue (represented by array for simplicity)
const queue = [];

const bfs = (sourceNode) => {
  // Mark source node as visited
  visited[sourceNode] = true;
  // Initialise BFS by adding source node to queue
  queue.push(sourceNode);

  while (queue.length > 0) {
    // Visit next node in queue
    const currNode = queue.shift(0);
    for (const neighbour in graph[currNode]) {
      // Only add neighbour to queue if not visited yet
      if (!visited[neighbour]) {
        // Mark neighbour as visited
        visited[neighbour] = true
        // Add neighbour to queue
        queue.push(neighbour);
      }
    }
  }
};

// Start BFS on source node
bfs("a");

Exercises

Pre-Class

    1. Hint: This does not require graph traversal

Part 1

    1. Hint: What additional data structures might be helpful for us to solve this problem?

    2. Hint: This does not require graph traversal

Part 2

    1. Hint: This requires graph traversal

Part 3

More Comfortable

    1. Hint: Would recursion be helpful?

Additional Resources

Find Center of Star Graph ()

Find the Town Judge ()

(Python)

(Python)

Find if Path Exists in Graph ()

Keys and Rooms () (Medium)

All Paths from Source to Target () (Medium)

(Python)

(Python)

Redundant Connection () (Medium)

Minimum Number of Vertices to Reach All Nodes () (Medium)

Number of Islands () (Medium)

in blog post

by freeCodeCamp

🧮
LeetCode
LeetCode
Rocket solution code
Rocket solution video
LeetCode
LeetCode
LeetCode
Rocket solution code
Rocket solution video
LeetCode
LeetCode
LeetCode
BFS vs DFS written explanation
Graph Algorithms for Technical Interviews video
Introduction to graphs and the problems we can solve with graphs
Introduction to graphs and how we can represent graphs in code
Walkthrough of DFS logic for graphs
Walkthrough of BFS logic for graphs