Data Structures Series #4: Graphs - Implementation & Use Cases

Introduction

Welcome back to the Data Structures series! So far we've covered Stacks, Queues, and Binary Trees. Today we're exploring one of the most versatile and powerful data structures in computer science: Graphs. From social networks to GPS navigation, graphs model relationships between things in ways other structures simply can't. Let's dig in.

---

What is a Graph?

A Graph is a non-linear data structure made up of vertices (also called nodes) and edges (connections between nodes). Unlike trees, graphs have no strict parent-child hierarchy — any node can connect to any other node.

Key Terminology

• Vertex (Node): A single entity in the graph (e.g., a user, a city).
• Edge: A connection between two vertices.
• Directed Graph: Edges have a direction (A → B, but not B → A). Think Twitter followers.
• Undirected Graph: Edges go both ways (A — B). Think Facebook friends.
• Weighted Graph: Edges carry a cost or distance value. Think Google Maps routes.
• Adjacency: Two vertices are adjacent if they share an edge.

Undirected Graph Example:

    A --- B
    |     |
    C --- D

---

Implementing a Graph in JavaScript

The most common way to represent a graph is with an Adjacency List — an object where each key is a vertex and its value is an array of connected vertices. It's memory-efficient and easy to work with.

Basic Graph Class

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  // Add a vertex
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  // Add an undirected edge
  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

  // Remove an edge
  removeEdge(v1, v2) {
    this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2);
    this.adjacencyList[v2] = this.adjacencyList[v2].filter(v => v !== v1);
  }

  // Remove a vertex and all its edges
  removeVertex(vertex) {
    while (this.adjacencyList[vertex].length) {
      const adjacent = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacent);
    }
    delete this.adjacencyList[vertex];
  }
}

// Usage
const graph = new Graph();
graph.addVertex("Alice");
graph.addVertex("Bob");
graph.addVertex("Carol");
graph.addEdge("Alice", "Bob");
graph.addEdge("Bob", "Carol");
graph.addEdge("Alice", "Carol");

console.log(graph.adjacencyList);
// { Alice: ["Bob", "Carol"], Bob: ["Alice", "Carol"], Carol: ["Bob", "Alice"] }

---

Graph Traversals

Traversal means visiting every vertex in the graph. There are two fundamental approaches.

1. Depth-First Search (DFS)

DFS explores as far as possible along a branch before backtracking. It uses a stack (or recursion) to track the path.

// Recursive DFS
dfs(start) {
  const result = [];
  const visited = {};

  const explore = (vertex) => {
    if (!vertex) return;
    visited[vertex] = true;
    result.push(vertex);

    this.adjacencyList[vertex].forEach(neighbor => {
      if (!visited[neighbor]) explore(neighbor);
    });
  };

  explore(start);
  return result;
}

Use DFS when: you want to detect cycles, solve puzzles (like mazes), or find a path between two nodes.

---

2. Breadth-First Search (BFS)

BFS explores all neighbours at the current level before moving deeper. It uses a queue and is ideal for finding the shortest path.

bfs(start) {
  const queue = [start];
  const result = [];
  const visited = { [start]: true };

  while (queue.length) {
    const vertex = queue.shift();
    result.push(vertex);

    this.adjacencyList[vertex].forEach(neighbor => {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    });
  }

  return result;
}

Use BFS when: you need the shortest path, level-by-level exploration, or finding nodes within a certain distance.

---

DFS vs BFS — Quick Comparison

Feature	DFS	BFS
Data Structure	Stack / Recursion	Queue
Memory Usage	Lower (for sparse graphs)	Higher (stores all levels)
Shortest Path	❌ Not guaranteed	✅ Yes (unweighted graphs)
Best For	Cycles, paths, topological sort	Shortest path, level traversal

---

Real-World Use Cases

• Social Networks: Finding friends-of-friends (BFS), detecting communities.
• GPS & Navigation: Shortest route between cities using weighted graphs (Dijkstra's algorithm builds on BFS).
• Web Crawlers: Crawling links from page to page using DFS.
• Recommendation Engines: "People you may know" or "Products you might like."
• Dependency Resolution: Package managers (like npm) use directed graphs to resolve module dependencies.

---

Time and Space Complexity

Let V = number of vertices, E = number of edges.

Operation	Adjacency List	Adjacency Matrix
Add Vertex	O(1)	O(V²)
Add Edge	O(1)	O(1)
Remove Edge	O(E)	O(1)
DFS / BFS	O(V + E)	O(V²)
Space	O(V + E)	O(V²)

Adjacency List is preferred for sparse graphs (fewer edges) — which is the common real-world case. Adjacency Matrix can be useful when you need fast edge lookups in dense graphs.

---

Conclusion

Graphs are one of the richest and most applicable data structures you'll encounter. Once you understand vertices, edges, and the two core traversal strategies — DFS and BFS — you unlock the ability to model and solve a huge class of real-world problems.

Key takeaways:

• Use an adjacency list for most graph implementations.
• Use BFS for shortest paths and level-order traversal.
• Use DFS for cycle detection, backtracking, and deep exploration.
• Graphs power social networks, navigation, search engines, and much more.

Stay tuned for the next post in the series!

---

🔗 Connect with Me

If you found this post helpful, follow me on Dev.to for more insights on data structures and algorithms!