Skip to content
Deadline to Die

Module 1: Graph Basics (The Social Network)

📚 Module 1: Graph Basics

Course ID: DSA-303
Subject: The Social Network

A Graph is a set of points where some pairs are connected by lines. It’s the ultimate “free-form” data structure.

🏗️ Step 1: Vertices & Edges

  1. Vertex (Node): A point (e.g., A Person, A City, A Page).
  2. Edge: A connection between points (e.g., A Friendship, A Road, A Hyperlink).

🧩 The Analogy: Facebook

  • Vertex: You and your friends.
  • Edge: The “Friend” connection. Since friendship is mutual, this is an Undirected graph.
  • Directed (Twitter): You can follow someone without them following you. The edges have “Arrows.”

🏗️ Step 2: Adjacency List (The “Friend List”)

How do we store this in code? We don’t use a 2D grid. We use an Adjacency List.

🧩 The Analogy: The Phone Contact List

For every person, you store a list of their friends.

  • Alice: [Bob, Charlie]
  • Bob: [Alice, Dave]
  • Charlie: [Alice]

In Code (Python Dictionary):

graph = {
    'Alice': ['Bob', 'Charlie'],
    'Bob': ['Alice', 'Dave'],
    'Charlie': ['Alice']
}

🏗️ Step 3: Weights (The “Cost”)

Sometimes, an edge has a Weight (a number).

  • Analogy: On a map, the edge between City A and City B has a weight of 50 miles.

🥅 Module 1 Review

  1. Vertex: The data point.
  2. Edge: The relationship.
  3. Directed: One-way connections.
  4. Adjacency List: The most efficient way to store a graph in code.

:::tip Slow Learner Note A Tree (Milestone 6) is actually just a very restricted type of Graph! A graph becomes a tree if it has no cycles (loops) and all nodes are connected. :::