C++UCS301
Graphs & ApplicationsC++17

Graph Representation

Adjacency lists use O(V+E) space and suit sparse graphs; matrices use O(V²) space and give O(1) edge tests.

Open this in the visual lab

What to understand

  • Adjacency list
  • Adjacency matrix
  • Edge list
  • Weighted representation

Remember this

  1. 1Most real graphs are sparse
  2. 2MST edge sorting naturally uses an edge list
  3. 3Choose representation from operations

Detailed notes

An adjacency matrix stores every possible vertex pair and answers edge existence in constant time, but consumes Θ(V²) space. An adjacency list stores only actual neighbours and is usually preferred for sparse graphs.

An edge list is minimal and ideal when algorithms process globally sorted edges, as Kruskal does. Weighted lists store destination-cost pairs; undirected edges normally appear twice.

How it works

  1. 1Estimate density relative to V² possible edges.
  2. 2List the operations the algorithm performs most often.
  3. 3Store both directions only for undirected models.
  4. 4Represent absent matrix edges with a safe sentinel distinct from valid weights.

Where it is used

  • Adjacency lists for BFS, DFS, Dijkstra, and Prim
  • Matrices for Floyd–Warshall and dense graphs
  • Edge lists for Kruskal and input formats

Common mistakes

  • Using zero to mean no edge when zero-weight edges are valid
  • Counting every undirected stored pair as two logical edges
  • Using a V² matrix for a massive sparse network

Complexity analysis

OperationBestAverageWorstExtra space
List storageO(V+E)O(V+E)O(V+E)O(V+E)
Matrix storageO(V²)O(V²)O(V²)O(V²)

C++ implementation

C++17 reference
main.cpp

Weighted adjacency list

For an undirected graph, store each edge in both endpoint lists.

#include <utility>
#include <vector>
using namespace std;

int vertices, edges;
cin >> vertices >> edges;
vector<vector<pair<int, int>>> graph(vertices);

for (int i = 0; i < edges; ++i) {
    int from, to, weight;
    cin >> from >> to >> weight;
    graph[from].push_back({to, weight});
    graph[to].push_back({from, weight});
}
14 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.