How is a graph defined in graph theory?
A graph is a mathematical structure used to model relationships between objects. It consists of vertices connected by edges, and it may be directed or undirected and weighted or unweighted.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Properties
A graph is commonly written as G = (V, E):
-
Vertices (
V): The nodes or objects in the model, such as people, cities, or web pages. -
Edges (
E): Connections between vertices, such as friendships, roads, or hyperlinks. -
Degree: The number of edges incident to a vertex.
-
Path: A sequence of vertices connected by edges.
-
Cycle: A path that starts and ends at the same vertex.
A graph can also be classified by several properties:
-
Undirected graph: Edges have no direction;
A—Bis equivalent toB—A. -
Directed graph: Edges have direction;
A→Bdoes not implyB→A. -
Unweighted graph: Every edge has equal cost, so BFS can find the path with the fewest edges.
-
Weighted graph: Each edge has a cost, distance, capacity, or other numeric value.
-
Simple graph: There are no self-loops, and each pair of vertices has at most one edge.
-
Multigraph: Multiple edges may connect the same pair of vertices.
The examples below use an undirected, unweighted graph represented by an adjacency list.
Common Representations
| Representation | Structure | Space including the graph | Main trade-off |
|---|---|---|---|
| Adjacency list | dict[node, list[neighbor]] |
O(V + E) |
Efficient for sparse graphs |
| Adjacency matrix | matrix[u][v] |
O(V²) |
Constant-time edge lookup but wasteful for sparse graphs |
| Edge list | List of (u, v) pairs |
O(V + E) |
Compact, but traversals usually require building an adjacency list |
An undirected adjacency list stores each edge twice, once in each endpoint’s neighbor list, but its asymptotic space remains O(V + E). A directed adjacency list stores each edge once and also uses O(V + E) space.
Typical Graph Algorithms
| Algorithm | Precondition | Best, average and worst time | Auxiliary space |
|---|---|---|---|
| BFS | Works on weighted and unweighted graphs | O(V + E) |
O(V) for the queue and visited set |
| DFS | Works on directed and undirected graphs | O(V + E) |
O(V) for the stack, visited set, and recursion stack |
| Dijkstra | Edge weights must be non-negative | O((V + E) log V) with a binary heap |
O(E) for a lazy priority queue |
| Bellman–Ford | Can handle negative edge weights | O(V × E) |
O(V) for distance values |
| Topological sort | The directed graph must be a DAG | O(V + E) |
O(V) for indegrees, the queue, and ordering |
| Floyd–Warshall | Suitable for relatively small dense graphs | O(V³) |
O(V²) for the distance matrix |
These bounds assume an adjacency-list representation. Including the stored graph, BFS and DFS use O(V + E) total space; Dijkstra and Bellman–Ford use O(V + E) total space.
Example Traversal
Consider the undirected edges:
A—B, B—C, B—D, D—E
A breadth-first traversal starting at A produces:
| Step | Visited vertices | Queue after processing |
|---|---|---|
| 1 | A |
B |
| 2 | A, B |
C, D |
| 3 | A, B, C |
D |
| 4 | A, B, C, D |
E |
| 5 | A, B, C, D, E |
Empty |
BFS discovers vertices in increasing distance from the starting vertex. The shortest path from A to E is A—B—D—E, containing three edges.
Common Pitfalls
-
Confusing
VandE:Vis the number of vertices, whileEis the number of edges. -
Ignoring disconnected graphs: Traversal algorithms must start another search from every unvisited vertex.
-
Forgetting the visited set: A visited set prevents repeated processing and infinite recursion in cyclic graphs.
-
Misusing cycle detection: Undirected graphs need parent tracking or union-find; directed graphs use three-color DFS or a recursion stack.
-
Ignoring direction and weights: An undirected shortest path is not necessarily valid in a directed graph, and Dijkstra is invalid with negative edge weights.
-
Recursion depth: Recursive DFS can exceed Python’s default recursion limit on large graphs; an iterative stack is safer.