Graph Basics

So far in this Algorithms course, we have worked mainly with arrays, recursion, sorting, searching, greedy methods, and dynamic programming.

From this lesson onward, we move into one of the most powerful and widely used concepts in computer science — Graphs.

Graphs are everywhere in the real world: roads, social networks, flight routes, recommendation systems, network routing, dependency resolution, and even modern AI systems.

What Is a Graph?

A graph is a way to represent relationships between objects. Each object is called a vertex (or node), and each relationship is called an edge.

Instead of storing values in a straight line (like arrays), graphs allow us to model complex connections.

Formally, a graph consists of:

• A set of vertices (nodes)
• A set of edges connecting those vertices

Real-World Intuition

Imagine a city map.

Each location (junction) is a node, and each road connecting two locations is an edge.

Now imagine social media. Each person is a node, and each friendship is an edge.

Graphs allow us to analyze such systems efficiently.

Types of Graphs

Graphs can be classified in many ways. Understanding these differences is essential before learning graph algorithms.

The most common distinctions are:

• Directed vs Undirected graphs
• Weighted vs Unweighted graphs

Directed vs Undirected Graphs

In an undirected graph, edges have no direction. If A is connected to B, then B is also connected to A.

In a directed graph, edges have a direction. A connection from A to B does not imply a connection from B to A.

Example:

• Friendship → Undirected
• Instagram follow → Directed

Weighted vs Unweighted Graphs

In an unweighted graph, edges simply represent connections.

In a weighted graph, each edge has a cost, distance, or weight.

Example:

• Road distance between cities
• Flight ticket cost
• Network latency

Graph Representation in Code

There are two main ways to represent graphs in programs:

• Adjacency Matrix
• Adjacency List

Adjacency List Representation

The adjacency list is the most commonly used representation because it is memory efficient and easy to traverse.

Each node stores a list of nodes it is connected to.

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

Here:

• A connects to B and C
• B connects to D
• C connects to D

Why Graphs Are Powerful

Graphs allow us to answer questions such as:

• Is there a path between two nodes?
• What is the shortest route?
• Are there cycles?
• Which nodes are most influential?

Almost all advanced graph algorithms build on these basics.

Common Mistakes Beginners Make

Many beginners struggle with graphs because they:

• Try to visualize everything at once
• Confuse direction of edges
• Ignore graph representation choice

The key is to start simple and focus on traversal logic.

Mini Practice

Consider this scenario:

• People are nodes
• Emails sent are directed edges

Answer this:

• Is this graph directed or undirected?
• Would weights be useful?

Exercises

Quick Quiz

In the next lesson, we will build on these foundations and learn Breadth-First Search (BFS), one of the most important graph traversal algorithms.