Source: CS 225 Lecture (Graph Implementations), UIUC
Difficulty: Intermediate | Prerequisites: Familiarity with arrays, linked lists, and basic Big-O notation (CS 225 up to trees).
Graphs are one of the most general-purpose data structures in computer science. Where trees enforce a strict parent-child hierarchy, graphs allow any vertex to connect to any other, making them the natural model for networks, maps, social connections, and dependency chains. This unit introduces the abstract data type (the operations every graph must support) and the first concrete way to store one in memory: the edge list. You should already be comfortable with lists, arrays, and asymptotic analysis before reading on.
A graph stores vertices (nodes) and edges (connections between them). The Graph ADT defines a standard set of operations: insert, remove, and query vertices and edges. The edge list is the simplest implementation, storing vertices in one list and edges in another, but most query operations require scanning the entire edge list, giving O(m) time where m is the number of edges.
Graph
A data structure consisting of a set of vertices and a set of edges connecting pairs of vertices. Think of it as a map of relationships: cities connected by roads, people connected by friendships.
Vertex (node)
A single entity in a graph, identified by a key. In simple terms, a dot on the diagram.
Edge
A connection between two vertices, optionally carrying a label or weight. In simple terms, a line drawn between two dots.
Incident edge
An edge is incident to a vertex if that vertex is one of the edge's endpoints. Think of it as "which roads touch this city."
Adjacent vertices
Two vertices are adjacent if an edge directly connects them. In simple terms, they are neighbours.
Graph ADT (Abstract Data Type)
The formal specification of the data a graph holds (vertices, edges, structure) and the operations it supports, independent of how it is stored in memory. Think of it as the interface, not the implementation.
Edge list
A graph implementation that stores all vertices in one list and all edges in a separate list, where each edge entry records its two endpoint vertices and an optional key. The simplest possible storage scheme.
Vertex collection
The list (or array) holding all vertex entries in an edge-list implementation.
Edge collection
The list (or array) holding all edge entries, each recording (vertex1, vertex2, label).
The Graph ADT defines the contract that any graph implementation must honour. The data consists of vertices, edges, and some internal structure linking them. The standard operations are:
insertVertex(K key) – add a new vertex with the given key
insertEdge(Vertex v1, Vertex v2, K key) – add an edge between v1 and v2, labelled with key
removeVertex(Vertex v) – remove a vertex and all its incident edges
removeEdge(Vertex v1, Vertex v2) – remove the edge between v1 and v2
incidentEdges(Vertex v) – return all edges touching v
areAdjacent(Vertex v1, Vertex v2) – return whether v1 and v2 share an edge
origin(Edge e) – return the starting vertex of a directed edge
destination(Edge e) – return the ending vertex of a directed edge
The last two (origin, destination) are relevant for directed graphs. For undirected graphs, an edge simply connects two vertices with no direction implied.
The edge list is the most straightforward way to store a graph.
Structure:
A vertex collection (array or list) holds every vertex, indexed 0 through n-1.
An edge collection (array or list) holds every edge as a triple: (source vertex, destination vertex, label).
For example, a graph with vertices {0, 1, 2, 3} and edges {a, b, c, d} is stored as:
Vertex list: [0, 1, 2, 3]
Edge list: [(0,1,a), (1,2,b), (0,2,c), (2,3,d)]
How operations work on an edge list:
insertVertex: Append to the vertex list. O(1) amortised.
removeVertex: Remove from the vertex list, then scan the entire edge list to remove every edge incident to that vertex. O(m).
insertEdge: Append a new triple to the edge list. O(1) amortised.
removeEdge: Scan the edge list to find the matching triple and remove it. O(m).
incidentEdges: Scan the entire edge list, collecting every entry where the given vertex appears as either endpoint. O(m).
areAdjacent: Call incidentEdges on one vertex, then check whether the other vertex appears. O(m).
The core weakness of the edge list is clear: nearly every interesting query requires a full scan of the edge collection, because edges are not organised by vertex.
Let n = number of vertices, m = number of edges.
Edge List Runtime Complexities:
Operation | Edge List |
|---|---|
insertVertex | O(1) |
removeVertex | O(m) |
insertEdge | O(1) |
removeEdge | O(m) |
incidentEdges | O(m) |
areAdjacent | O(m) |
Space complexity: O(n + m). The vertex list uses O(n) and the edge list uses O(m).
Students often assume that areAdjacent is O(1) on an edge list because you are "just checking two vertices." It is not. The edge list has no index by vertex, so you must scan all m edges.
Students sometimes confuse the edge list with the adjacency list. The edge list is a flat collection of (v1, v2, label) triples. The adjacency list groups edges by their source vertex, which is a different (and generally faster) structure.
removeVertex is easily underestimated. Removing the vertex entry itself is quick, but you must also find and remove every edge that touches it, which means scanning the full edge list.
The edge list does not store the graph "twice" for undirected graphs. Each undirected edge appears once in the edge list; both endpoints are recorded in the same triple.
⚠️ Know the runtime of every Graph ADT operation on an edge list. This is a classic table-comparison exam question.
⚠️ Be able to trace insertVertex, insertEdge, removeVertex, incidentEdges, and areAdjacent on a small example graph. The lecture slides use a four-vertex graph (0, 1, 2, 3) with edges (a, b, c, d) for exactly this purpose.
⚠️ Understand why the edge list is space-efficient but time-expensive for queries. Exams will ask you to justify choosing one implementation over another for a given workload.
⚠️ areAdjacent can be expressed in terms of incidentEdges: G.incidentEdges(v1).contains(v2). Know this reduction.
True or False: In an edge list, areAdjacent(v1, v2) runs in O(1) time.
Fill in the blank: The edge list stores each edge as a triple of ______, ______, and ______.
True or False: removeVertex on an edge list only requires removing the vertex from the vertex collection.
Fill in the blank: The space complexity of an edge list is O(______).
True or False: incidentEdges must scan the entire edge collection because there is no per-vertex index.
Answers: 1. False (it is O(m)). 2. source vertex, destination vertex, label/key. 3. False (you must also remove all incident edges). 4. n + m. 5. True.
Q: Given a graph with 5 vertices and 8 edges stored as an edge list, what is the worst-case runtime of calling incidentEdges on a single vertex?
A: O(8), or more generally O(m). You must scan every edge in the edge collection to find those incident to the vertex.
Q: You need to build a graph that will be constructed once and then queried thousands of times for areAdjacent. Is the edge list a good choice? Why or why not?
A: No. areAdjacent on an edge list is O(m) per query. For heavy querying, an adjacency matrix (O(1) lookup) or adjacency list (O(deg(v))) would be far better.
Q: Describe what happens, step by step, when removeVertex(2) is called on an edge list containing vertices {0,1,2,3} and edges {(0,1,a), (1,2,b), (0,2,c), (2,3,d)}.
A: First, scan the edge list and remove every edge that has vertex 2 as an endpoint: (1,2,b), (0,2,c), and (2,3,d) are all removed. Then remove vertex 2 from the vertex collection. The resulting graph has vertices {0,1,3} and edges {(0,1,a)}.
Q: What is the key advantage of the edge list over the adjacency matrix?
A: Space. The edge list uses O(n + m) space. The adjacency matrix uses O(n^2) space regardless of how many edges exist, which is wasteful for sparse graphs.
Q: Write the expression that implements areAdjacent using incidentEdges, as shown in lecture.
A: G.incidentEdges(v1).contains(v2)
This material connects directly to the adjacency matrix (covered in Part 2 of these notes), which trades space for faster query time. It also connects to the adjacency list, a third implementation that tends to be the default choice in practice.
Graph traversals (BFS, DFS) and algorithms (Dijkstra, Kruskal, Prim) build on whichever implementation you choose. The runtime of those algorithms depends on the underlying implementation, so knowing the cost of incidentEdges and areAdjacent for each structure is essential.
The Graph ADT is also a generalisation of the Tree ADT you studied earlier: a tree is a connected, acyclic graph.
Graph, graph ADT, graph abstract data type, vertex, node, edge, arc, incident edge, adjacent vertices, neighbours, edge list, edge list implementation, graph implementation, insertVertex, insertEdge, removeVertex, removeEdge, incidentEdges, areAdjacent, origin, destination, directed graph, undirected graph, sparse graph, dense graph, CS 225, data structures, UIUC, graph storage, graph representation