Skip to main content
Algorithms Analysis
CHAPTER 22 Beginner

Graph Theory Introduction

Updated: May 17, 2026
15 min read

# CHAPTER 22

Graph Theory Introduction

1. Introduction

If you want to represent a line of people waiting for a bus, you use an Array. If you want to represent a corporate hierarchy (CEO -> Managers -> Employees), you use a Tree. But how do you represent the internet? How do you represent a map of the United States highway system? How do you represent Facebook's massive web of mutual friendships? These structures are not straight lines, and they are not neat top-down hierarchies. They are chaotic, highly interconnected webs. In Computer Science, we model these webs using Graphs. Graph Theory is the mathematical foundation of navigation algorithms, network routing, and social media infrastructure.

2. Learning Objectives

By the end of this chapter, you will be able to:
  • Define Vertices (Nodes) and Edges (Relationships).
  • Differentiate between Directed and Undirected graphs.
  • Differentiate between Weighted and Unweighted graphs.
  • Represent graphs in RAM using Adjacency Matrices.
  • Represent graphs in RAM using Adjacency Lists.

3. The Anatomy of a Graph

A Graph consists of two fundamental components: $G = (V, E)$.
  1. 1. Vertices (V): The actual entities or physical locations. (e.g., A specific User on Facebook, or the city of Chicago). Also called Nodes.
  1. 2. Edges (E): The mathematical links that physically connect two Vertices. (e.g., The friendship between two users, or Interstate 90 connecting Chicago to Boston).

4. Types of Edges

Graphs are categorized based on how the Edges behave.

#### Undirected vs. Directed

  • Undirected Graphs: The edge is a two-way street. If Mark is friends with Sarah on Facebook, Sarah is inherently friends with Mark. The relationship is bidirectional.
  • Directed Graphs (Digraphs): The edge is a strict one-way street (indicated by an arrow). On Twitter/X, Mark can follow a Celebrity, but that does NOT mean the Celebrity follows Mark back.

#### Unweighted vs. Weighted

  • Unweighted Graphs: Every edge is equal. (e.g., A network of friends. You are either friends or you aren't. There is no numerical value to the friendship).
  • Weighted Graphs: The edges carry a numeric payload (Weight/Cost). If Vertices are Cities, the Edge connecting them has a "Weight" representing the physical mileage (e.g., Chicago to New York = 790 miles). Google Maps relies exclusively on Weighted Directed Graphs.

5. Translating Graphs into RAM

You cannot just draw circles and lines inside computer memory. You must translate the visual map into programmable Data Structures. Engineers use two primary techniques:

#### 1. Adjacency Matrix A 2D Array (Grid). If there are 5 Vertices, you create a 5x5 Matrix. If there is an Edge between Vertex 0 and Vertex 1, you write a 1 at matrix[0][1]. If there is no edge, you write a 0.

text
12345 
// A 3x3 Matrix representing 3 interconnected cities
    0  1  2
0 [ 0, 1, 0 ]  <- Node 0 is connected to 1.
1 [ 1, 0, 1 ]  <- Node 1 is connected to 0 and 2.
2 [ 0, 1, 0 ]  <- Node 2 is connected to 1.
  • Pros: Blazing fast $O(1)$ lookups. ("Are 0 and 1 connected? Check the array index!").
  • Cons: Disastrous $O(V^2)$ Space Complexity. If Facebook maps 1 Billion users, it creates a matrix of 1 Billion x 1 Billion indices. 99% of them will be 0 (because you aren't friends with a billion people). The server will crash instantly.

#### 2. Adjacency List An Array of Linked Lists (or dynamic arrays). Each index represents a Vertex, and it simply holds a list of the exact neighbors it is connected to.

text
1234 
Array Index:
[0] -> [1]           <- Node 0 only connected to 1
[1] -> [0, 2]        <- Node 1 connected to 0 and 2
[2] -> [1]           <- Node 2 only connected to 1
  • Pros: Perfect $O(V + E)$ Space efficiency. It only stores actual, existing relationships. Facebook strictly uses Adjacency Lists.
  • Cons: Slower lookups. To see if 1 is friends with 2, you must traverse the linked list at Index 1.

6. Real-World Applications

  1. 1. The PageRank Algorithm: The algorithm that made Google a multi-billion dollar company. It models the entire internet as a massive Directed Graph (Websites are Vertices, Hyperlinks are Directed Edges).
  1. 2. Network Routing: Cisco routers use Graph algorithms to discover the fastest pathway to bounce your data packets across global data centers.
  1. 3. AI Pathfinding: Video games use graphs (NavMeshes) to allow enemy NPCs to intelligently path around walls and obstacles to attack the player.

7. Common Mistakes

  • Confusing Trees and Graphs: All Trees are technically Graphs, but not all Graphs are Trees! A Tree is a highly restricted Graph that mandates a hierarchical structure and explicitly forbids "Cycles" (loops). A standard Graph has no root and can loop endlessly.

8. Exercises

  1. 1. If an Undirected Unweighted graph has 4 vertices, and every vertex is connected to every other vertex, how many total edges exist?
  1. 2. Draw a 4x4 Adjacency Matrix representing a Directed Graph where Node 0 points to Node 1, and Node 1 points to Node 2. All other cells are 0.

9. MCQs with Answers

Question 1

In Graph Theory nomenclature, what represents the physical entities or locations within a network (e.g., Users, Intersections, Servers)?

Question 2

In Graph Theory nomenclature, what represents the mathematical, structural connections between those entities?

Question 3

If an architectural network models a Twitter social infrastructure where User A "follows" User B, but User B does not follow User A back, what graph classification is explicitly required?

Question 4

When modeling a global aviation flight network, the Edges connecting airports must store the fuel cost required to execute the flight. What classification is this?

Question 5

When representing a Graph in system RAM utilizing an Adjacency Matrix, what is the catastrophic mathematical vulnerability regarding Space Complexity?

Question 6

To bypass Matrix memory limits, massive Enterprise systems (like Facebook) utilize Adjacency Lists. What underlying architecture typically powers an Adjacency List?

Question 7

What is the fundamental, defining architectural difference between a Standard Graph and a Binary Tree?

Question 8

If an Adjacency Matrix is utilized to map a purely Undirected Graph, what unique geometric property will the 2D Array possess?

Question 9

If a Graph architecture mandates that an Edge connects a Vertex directly back into itself (e.g., a webpage hyperlinking to its own URL), what is this called?

Question 10

Google's foundational PageRank algorithm revolutionized internet search by translating the World Wide Web into which explicit Graph architecture?

10. Interview Preparation

Top Interview Questions:
  • *System Architecture:* "You are building LinkedIn. There are 500 million users. Most users have roughly 50 connections. Do you use an Adjacency Matrix or an Adjacency List to store the network?" *(Answer: Adjacency List! This is a "Sparse" graph. A Matrix would allocate 250 Quadrillion cells, crashing immediately. A List dynamically allocates only the 50 connections per user, succeeding flawlessly).*

11. Summary

Graph Theory transforms abstract, chaotic real-world networks—social dynamics, global logistics, and internet routing—into strict mathematical structures. By defining Vertices, applying Vector directionality to Edges, and heavily managing Space Complexity via Adjacency Lists, we prepare the architectural foundation required for algorithmic traversal.

12. Next Chapter Recommendation

We have successfully mapped the Graph into computer memory. Now, we must write algorithms to systematically explore the web. If you want to find your "Friends of Friends" radiating outward in expanding waves, how do you do it? In Chapter 23: Breadth-First Search (BFS), we will utilize Queue data structures to systematically conquer the grid.

Finish this Chapter

Save your progress on your learning path and prepare for coding interview challenges.

Previous Chapter Backtracking Algorithms
Next Chapter Breadth-First Search (BFS)

Discussion

Join the discussion

Log in or create a free account to participate.

Sort: ·

Explore More

📖 Related Tutorials 4

❓ Related Quizzes 5

🧪 Related Labs 1