Graph Fundamentals
Graphs are one of the most versatile and powerful data structures in computer science. They model relationships between objects and appear everywhere — from social networks and maps to recommendation systems and the internet itself. For developers, understanding graphs means being able to recognize when a problem involves connectivity, reachability, or relationships — and knowing how to represent and reason about those structures in code.
What Is a Graph?#
A graph is a collection of vertices (also called nodes) connected by edges. Trees, which you may already be familiar with, are actually a special kind of graph — one that is connected, has no cycles, and follows a strict hierarchy. General graphs lift all of those restrictions: they can contain cycles, have multiple paths between the same pair of nodes, and carry no hierarchical structure at all.
Real-World Examples#
- Social Networks: People are vertices, friendships are edges
- Maps: Intersections are vertices, roads are edges
- Internet: Web pages are vertices, hyperlinks are edges
- Flight Routes: Airports are vertices, flights are edges
- Dependencies: Tasks/packages are vertices, dependencies are edges
Key Terminology#
| Term | Definition | Example |
|---|---|---|
| Vertex (Node) | A point in the graph | Person in a social network |
| Edge | A connection between two vertices | Friendship between two people |
| Adjacent | Two vertices connected by an edge | Friends who are directly connected |
| Degree | Number of edges connected to a vertex | Number of friends a person has |
| Path | A sequence of distinct vertices where each consecutive pair is connected by an edge | Driving A→B→C→D with no U-turns |
| Cycle | A closed path that starts and ends at the same vertex with no other repeated vertices | A round trip returning to the starting city |
| Connected | A graph where a path exists between every pair of vertices | Any city can reach any other city by road |
| Weight | Value assigned to an edge | Distance between cities |
Degree in Detail#
Degree counts only the edges directly attached to a vertex — indirect connections that pass through other vertices do not count toward a vertex's degree.
Reading the diagram:
- B (degree 3): Has three direct edges — to A, C, and D.
- A (degree 2): Has two direct edges — to B and C. Although A can indirectly reach D through B, that path does not count toward A's degree.
- C (degree 2): Has two direct edges — to A and B.
- D (degree 1): Has one direct edge — to B only. A vertex with degree 1 is called a leaf.
Direct vs. indirect connections: Degree reflects only immediate neighbors — vertices one hop away. The fact that A can reach D via B is an indirect connection and does not affect A's degree.
In directed graphs, degree splits into two components:
- In-degree: Number of edges entering a vertex. For example, if A→B and C→B, then B has in-degree 2.
- Out-degree: Number of edges leaving a vertex. For example, if B→C and B→D, then B has out-degree 2.
- A vertex's total degree equals its in-degree plus its out-degree.
Types of Graphs#
| Type | Description | Use Case |
|---|---|---|
| Undirected | Edges have no direction (A-B means both can reach each other) | Social networks, road maps |
| Directed | Edges point in one direction (A→B lets you travel from A to B, but not from B to A along that edge) | Web links, dependencies |
| Weighted | Edges have associated values (costs, distances) | Shortest path, network flow |
| Unweighted | All edges are equal | BFS for shortest path by hops |
| Cyclic | Contains at least one cycle | General graphs |
| Acyclic | Contains no cycles | Trees, DAGs |
| DAG | Directed Acyclic Graph — a directed graph with no cycles | Task scheduling, build systems |
| Connected | Path exists between any two vertices | Single-component networks |
| Disconnected | Some vertices have no path to certain others | Multiple isolated networks |
Graph Representations#
There are three main ways to represent a graph in code. Each has different time and space trade-offs, so choosing the right one depends on your graph's size, density, and the operations you need to perform most often.
1. Adjacency Matrix#
A 2D array where matrix[i][j] = 1 if there's an edge from vertex i to vertex j.
Pros:
- O(1) edge lookup and insertion
- Simple to implement
- Good for dense graphs
Cons:
- O(V²) space regardless of edge count
- O(V²) to iterate all edges
- Inefficient for sparse graphs
2. Adjacency List#
Each vertex stores a list of its neighbors.
Pros:
- O(V + E) space — efficient for sparse graphs
- O(degree) to iterate neighbors (visits only actual neighbors)
- Most commonly used representation in practice
Cons:
- O(degree) to check if a specific edge exists — you must scan through the neighbor list
- Slightly more complex to implement than a matrix
3. Edge List#
Simply a list of all edges as pairs (or triples for weighted graphs).
edges = [(0,1), (0,2), (1,2)]
Pros:
- Simplest representation
- O(E) space
- Good for algorithms that process edges (like Kruskal's MST)
Cons:
- O(E) to find neighbors
- O(E) to check if edge exists
Representation Comparison#
| Operation | Adjacency Matrix | Adjacency List | Edge List |
|---|---|---|---|
| Space | O(V²) | O(V + E) | O(E) |
| Add Edge | O(1) | O(1) | O(1) |
| Remove Edge | O(1) | O(degree) | O(E) |
| Check Edge | O(1) | O(degree) | O(E) |
| Get Neighbors | O(V) | O(degree) | O(E) |
| Iterate All Edges | O(V²) | O(V + E) | O(E) |
| Best For | Dense graphs, quick edge lookup | Sparse graphs (most common) | Edge-centric algorithms |
Implementation#
Graph Implementation
Build graphs using adjacency matrix and adjacency list representations
Common Graph Operations#
| Operation | Description | Common Approach |
|---|---|---|
| Traversal | Visit all vertices | BFS or DFS |
| Shortest Path | Find minimum distance between vertices | BFS (unweighted), Dijkstra (weighted) |
| Cycle Detection | Check if graph contains a cycle | DFS with visited tracking |
| Connectivity | Check if all vertices reachable | BFS/DFS from any vertex |
| Topological Sort | Order vertices so dependencies come first (only possible for DAGs) | Kahn's algorithm or DFS |
| Minimum Spanning Tree | Connect all vertices with minimum total edge weight | Prim's or Kruskal's algorithm |
Choosing the Right Representation#
Use this decision tree to pick the right representation based on your graph's density and the operations you perform most frequently:
General Rule: Default to an adjacency list. Most real-world graphs are sparse (far fewer edges than the V² maximum), and adjacency lists handle them efficiently. Switch to a matrix only when you need constant-time edge lookups, or to an edge list only when your algorithm processes edges directly (such as Kruskal's MST algorithm).
Reviewing AI-Generated Code#
When AI generates graph code for you, a solid understanding of the fundamentals lets you quickly spot issues before they cause bugs at runtime:
What to Verify#
| Issue | What to Check | Common AI Mistake |
|---|---|---|
| Representation Choice | Adjacency list vs matrix matches use case | Using O(V²) matrix for sparse graphs |
| Vertex Initialization | All vertices exist before adding edges | Adding edges to non-existent vertices |
| Directed vs Undirected | Edge additions match graph type | Adding one-way edge for undirected graph |
| Self-loops & Multi-edges | Check whether they should be allowed based on requirements | Not preventing duplicate edges when needed |
| Missing Vertices | Isolated vertices included in vertex list | Only including vertices with edges |
Common AI Pitfalls#
Graph Representation Bugs
Common mistakes AI makes when implementing graphs
Questions to Ask AI#
When reviewing AI-generated graph code, ask:
- "What's the space complexity with V vertices and E edges?"
- "How do you handle disconnected graphs?"
- "Does this work for both directed and undirected graphs?"
- "How do you prevent duplicate edges?"
Summary#
| Concept | Key Takeaway |
|---|---|
| Graph | Vertices connected by edges — models relationships |
| Directed vs Undirected | Edges may or may not have direction |
| Weighted | Edges have associated costs/distances |
| Adjacency List | Most common: O(V+E) space, good for sparse graphs |
| Adjacency Matrix | O(V²) space, O(1) edge lookup, good for dense graphs |
| Edge List | Simplest, O(E) space, good for edge-centric algorithms |
| Degree | Number of edges connected to a vertex |
| DAG | Directed Acyclic Graph — enables topological ordering |
Graphs underpin countless algorithms and real-world systems. With a clear grasp of representations, terminology, and trade-offs, you'll be well-equipped to tackle traversal, shortest paths, and more advanced graph problems — whether you're writing the code yourself or guiding an AI assistant to do it correctly.