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. Each node of a list represents an edge (destination and edge pair).

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():

EDGES_IN_MST: the vertex count.
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 < EDGES_IN_MST)
    edge = edgeQueue.dequeue()
    if (!wasVisited[edge.destination])
      mstEdges.enqueue(edge)
      ++edgeCount
    totalCost += edge.weight
    enqueueEdges (edge.destination, wasVisited, edgeQueue)
  return (edgeCount != EDGES_IN_MST) ? -1 : totalCost

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

// Iterate over all edges going outward from the current node.
// Add edges to unvisited nodes the queue
for (const auto &edge : AdjacencyMatrix[nodeIdx])
  if (!wasVisited[edge.destination])
    edgeQueue. enqueue({fromVertex, edge.destination, edge.weight});

Performance

What operations are faster with an Adjacency Matrix?

What operations are faster with an Adjacency List?

When would each implementation be more memory efficient?

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 ​