Graph Data Structure Fundamentals

What is a Graph?

A graph is a collection of nodes (called vertices) connected by links (called edges). Think of it like a social network: each person is a vertex, and each friendship is an edge connecting two people. Unlike trees or linked lists, graphs have no hierarchy — any node can connect to any other node, and connections can even form loops.

Formally, a graph G is defined as G = (V, E) where V is the set of vertices and E is the set of edges. Each edge connects two vertices. This simple definition gives rise to one of the most versatile data structures in computer science.

Types of Graphs

Undirected Graphs

In an undirected graph, edges have no direction. If there is an edge between A and B, you can traverse it both ways. Think of a road between two cities that allows traffic in both directions.

Here, edge (A,B) means A connects to B AND B connects to A.

Directed Graphs (Digraphs)

In a directed graph, each edge has a direction — it goes FROM one vertex TO another. Think of Twitter follows: you can follow someone without them following you back.

Here, A→B means A connects to B, but B does NOT necessarily connect back to A.

Weighted Graphs

In a weighted graph, each edge carries a numerical value (weight). Think of a road map where the weight represents distance or travel time between cities.

Key Terminology

Degree of a Vertex

The degree of a vertex is the number of edges connected to it. In the first undirected example, vertex A has degree 2 (connected to B and C).

For directed graphs, we distinguish:

• In-degree: Number of edges coming INTO the vertex
• Out-degree: Number of edges going OUT from the vertex

Path

A path is a sequence of vertices where each consecutive pair is connected by an edge. In our undirected example, A→B→D is a path from A to D. A simple path visits each vertex at most once.

Cycle

A cycle is a path that starts and ends at the same vertex. In the undirected example, A→B→D→C→A forms a cycle. Cycles are important — their presence or absence determines which algorithms you can use.

Connected Components

In an undirected graph, a connected component is a maximal set of vertices such that there is a path between every pair. If a graph has multiple disconnected pieces, each piece is a connected component.

This graph has 2 connected components: {A, B, C} and {E, F, G}.

Graph Properties

Simple vs Multigraph

A simple graph has no self-loops (edge from a vertex to itself) and no multiple edges between the same pair of vertices. A multigraph allows these.

Dense vs Sparse

A graph with V vertices can have at most V*(V-1)/2 edges (undirected) or V*(V-1) edges (directed). A graph is dense if |E| is close to this maximum (like a social network of a small group where everyone knows everyone). It is sparse if |E| is much smaller (like a road network where each city connects to only a few neighbors).

Bipartite Graphs

A graph is bipartite if its vertices can be divided into two sets such that every edge connects a vertex in one set to a vertex in the other. Think of a job matching problem: one set is workers, the other is jobs, and edges represent eligibility.

Python Representation (Quick Example)

Complexity Quick Reference

Real-World Applications

• Social Networks: Users are vertices, connections are edges (Facebook friendships, Twitter follows)
• Maps/Navigation: Intersections are vertices, roads are edges with distance weights
• Internet: Web pages are vertices, hyperlinks are directed edges (Google PageRank)
• Dependencies: Tasks are vertices, prerequisites are directed edges (build systems, course planning)
• Molecular Structure: Atoms are vertices, chemical bonds are edges
• Network Routing: Routers are vertices, links are edges with bandwidth weights

When to Think "Graph"

If your problem involves:

• Relationships between entities
• Finding shortest/longest paths
• Detecting cycles or dependencies
• Connectivity questions
• Network flow or matching

...then you are likely dealing with a graph problem. The next step is choosing the right representation and algorithm, which we cover in subsequent lessons.