Graphs Introduction

# CHAPTER 24

Graphs Introduction #

1. Introduction #

2. Learning Objectives #

• Define the architectural components of a Graph (Vertices and Edges).

• Differentiate between Directed, Undirected, and Weighted Graphs.

• Implement Graphs in code using Adjacency Matrices.

• Implement Graphs in code using Adjacency Lists.

• Identify real-world systems built upon Graph Theory.

3. The Architecture: Vertices and Edges #

1. 1. Vertices (Nodes): The actual entities (e.g., A Person, A City, A Router).

1. 2. Edges (Links): The lines that physically connect two Vertices (e.g., A Friendship, A Highway, A Fiber-Optic Cable).

Unlike a Tree, a Graph has NO Root. You can start exploring a Graph from absolutely any Vertex.

4. Classifications of Graphs #

#### 4.1 Undirected vs. Directed Graphs

• Undirected Graph: The Edge is a two-way street. If Vertex A is connected to Vertex B, then B is inherently connected to A. (Example: A Facebook friendship. If I am your friend, you are my friend).

• Directed Graph (Digraph): The Edge is a one-way arrow! If A points to B, it does NOT mean B points to A. (Example: Twitter/X followers. I can follow a celebrity, but they do not follow me back).

#### 4.2 Weighted vs. Unweighted Graphs

• Unweighted Graph: Every Edge is identical. Traveling from A to B takes 1 "step".

• Weighted Graph: Every Edge has an explicit mathematical Integer (Weight/Cost) assigned to it. (Example: Google Maps. The edge between City A and City B might have a weight of "50 miles" or "45 minutes"). Pathfinding algorithms use these weights to calculate the shortest route.

5. Representing Graphs in Code #

#### 5.1 Adjacency Matrix (The 2D Array) An Adjacency Matrix uses a 2D Boolean Array. The rows and columns represent the Vertices. A 1 (or True) indicates an Edge exists between them.

Vertices: A, B, C
Edges: A-B, B-C

Matrix:
    A  B  C
A [ 0, 1, 0 ]   <-- A is connected to B
B [ 1, 0, 1 ]   <-- B is connected to A and C
C [ 0, 1, 0 ]   <-- C is connected to B

• Pros: Instant O(1) checks to see if an edge exists (if matrix[A][B] == 1).

• Cons: Disastrous O(V²) Space Complexity. If you have 1 million Facebook users, creating a 1-million by 1-million array will instantly crash the servers, especially since 99.9% of the slots will be 0 (False).

#### 5.2 Adjacency List (The Array of HashMaps/Lists) To fix the memory nightmare of the Matrix, we use an Adjacency List. We create a Dictionary (or Array) where every Vertex holds a dynamic List of *only* the vertices it connects to.

# Python Example: Adjacency List using a Dictionary
graph = {
    "A": ["B"],
    "B": ["A", "C"],
    "C": ["B"]
}

# Finding the neighbors of B is instant and consumes almost zero RAM!
print(graph["B"]) # Output: ['A', 'C']

• Pros: Flawless Space Complexity O(V + E). It only consumes RAM for edges that *actually exist*.

• Cons: Checking if a specific edge exists takes O(E) time, as you must search the specific Vertex's list.

6. Complexity Analysis (Adjacency List) #

7. Real-World Applications #

1. 1. Google's PageRank: The entire internet is a massive Directed Graph. Webpages are Vertices; hyperlinks are Directed Edges pointing to other pages. Google ranks pages based on how many edges point to them!

1. 2. Social Networks: LinkedIn calculates "2nd-degree connections" by traversing two edges outward from your Vertex.

1. 3. Logistics: Amazon calculates the fastest delivery route for a truck visiting 50 cities utilizing Weighted Graphs.

8. Common Mistakes #

• Using an Adjacency Matrix in Production: Junior developers love Adjacency Matrices because a 2D array is incredibly easy to visualize and code. Do not use them unless the Graph is "Dense" (almost every node connects to every other node). In the real world, Graphs are "Sparse" (You only have 500 friends out of 2 billion Facebook users). Adjacency Lists are strictly required for Sparse Graphs to prevent catastrophic memory crashes.

9. Best Practices #

• Master Hash Maps for Graphs: In interview settings, instantly defaulting to a HashMap<String, List<String>> (Java) or dict (Python) is the fastest, cleanest way to build a Graph on a whiteboard.

10. Exercises #

1. 1. Draw a Directed Weighted Graph with 3 nodes (A, B, C). A points to B (Weight 5). B points to C (Weight 10). C points to A (Weight 2).

1. 2. Write the Python Dictionary (Adjacency List) representation for the Graph you just drew.

11. MCQs with Answers #

13. Interview Preparation #

• *System Design:* "Design the underlying data structures required to build a feature similar to LinkedIn's 'Connections'. Defend your choice of Graph representation regarding Memory consumption." *(Answer: Always propose an Adjacency List utilizing HashMaps to prevent O(V²) memory blowout on sparse data).*

Common Pitfalls:

• In whiteboard coding, failing to account for "Undirected" logic. If the prompt asks you to create an Undirected Graph, and you execute graph[A].append(B), you MUST remember to also execute graph[B].append(A). A two-way street requires two entries in the Adjacency List!

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #