Graphs via Adjacency Lists

Chapter 20

Review

Graph Data Structures

To process and manipulate graphs, we must store
graphs in computer memory.

A graph is commonly represented in one of two ways:

Adjacency matrices
Adjacency lists

Adjacency Matrix: Weighted Directed Example

A weighted directed graph and it's representation using adjacency matrix.

If the edges have weights, they are stored in the matrix.

Limitations of Adjacency Matrices

Wasted space, . It stores a weight for an edge
from every vertex to every other vertex.
Most graphs are sparse.
Slow iteration over edges.
Slow add/delete of vertices.
Cannot represent parallel edges.

Adjacency Lists

Implemented using a vector of lists (e.g., std::vector<std::list<Edge>>). Each node in a list represents an edge, storing the destination vertex and edge weight. This representation uses space, far better than for sparse graphs. Unlike adjacency matrices, adjacency lists can represent multiple parallel edges between vertices and support efficient edge iteration during traversals.

Minimal Spanning Trees

A Spanning Tree is a subset of the edges in the graph that connects all vertices without creating any cycles.

A Minimum Spanning Tree is a spanning tree that minimizes the total edge cost.

A graph has a spanning tree if and only if it is connected.

Spanning Tree: Examples

Suppose an airline’s connections are represented by the following graph. The edge weights are the costs. How can the airline minimize costs while still being able to fly to every city?

Example graph to find a spanning tree of.

Example spanning tree of a graph with cost .

The minimal spanning tree for the above graph is . See if you can manually identify which edges it would include ().

Minimal Spanning Tree Algorithms

Well-known algorithms to find a minimal spanning tree
of an undirected and connected graph.

Kruskal’s algorithm (published 1956)
Prim’s algorithm (rediscovered in 1957)
- Builds the tree iteratively by adding edges until a minimal spanning tree is obtained.
- Start with a designated vertex, called the source vertex.
- At each iteration, a new edge that does not complete a cycle is added to the tree.

Prim’s Minimal Spanning Tree Algorithm

1 / 1

Prim’s Algorithm: Pseudo Code

Local Variables in prims():

vertexCount: the number of vertices in the graph. A spanning tree has exactly vertexCount - 1 edges.
Priority Queue of Edges (initially empty). The Edge type contains from and to vertices and the weight.
wasVisited``[Node Count]: set to all false.
totalCost = 0
edgeCount = 0
List of Edges in MST (initially empty).

Function: prims(startIdx):
  enqueueEdges (startIdx, wasVisited, edgeQueue);
  while (!edgeQueue.empty() && edgeCount < vertexCount - 1)
    edge = edgeQueue.dequeue()
    if (!wasVisited[edge.destination])
      mstEdges.enqueue(edge)
      ++edgeCount
    totalCost += edge.weight
    enqueueEdges (edge.destination, wasVisited, edgeQueue)
  return (edgeCount != vertexCount - 1) ? -1 : totalCost

Function enqueueEdges (fromVertex, wasVisited[], edgeQueue):
  // Mark the current node as visited.
  wasVisited[fromVertex] = true;

  // Iterate over the edges of the current vertex.
  // Add edges to unvisited nodes the queue
  for (const auto &edge : mAdjacencyLists[fromVertex])
    if (!wasVisited[edge.destination])
      edgeQueue.enqueue({fromVertex, edge.destination, edge.weight});

Performance

Adjacency Matrix: Faster for checking if an edge exists between two specific vertices (O(1) lookup). Best for dense graphs where most vertices are connected.

Adjacency List: Faster for iterating over edges (O(V+E)), requires less space for sparse graphs (O(V+E) vs O(V²)), and supports parallel edges. Prim's algorithm runs in O((V + E) log E) time with adjacency lists.

Memory Efficiency: Adjacency lists are far more efficient for sparse graphs (few edges relative to vertices). Adjacency matrices always use O(V²) space regardless of edge count.

Summary

A graph is a pair, .
In an undirected graph ,
the elements of are unordered pairs.
In a directed graph ,
the elements of are ordered pairs.
is a subgraph of if every vertex of is a vertex of and every edge is an edge in .
Two vertices in an undirected graph are adjacent if there is an edge between them.
Loop: an edge incident on a single vertex.
Simple graph: no loops and no parallel edges.
Simple path: all the vertices, except possibly the first and last vertices, are distinct.
Cycle: a simple path in which the first and last vertices are the same.
An undirected graph is connected if there is a path from any vertex to any other vertex.
The shortest path algorithm gives the shortest distance for a given node to every other node in the graph.
In a weighted graph, every edge has a nonnegative weight.
A rooted tree is a tree in which a particular vertex is designated as a root.
A tree is called a spanning tree of graph if is a subgraph of G such that .

Lab 23: Graphs via Adjacency Lists

Let’s look at the lab based on today’s lecture.

Graphs via Adjacency Lists ​

Review ​

Graph Data Structures ​

Adjacency Matrix: Weighted Directed Example ​

Limitations of Adjacency Matrices ​

Adjacency Lists ​

Minimal Spanning Trees ​

Spanning Tree: Examples ​

Minimal Spanning Tree Algorithms ​

Prim’s Minimal Spanning Tree Algorithm ​

Prim’s Algorithm: Pseudo Code ​

Performance ​

Summary ​

Lab 23: Graphs via Adjacency Lists ​