跳转至

20 Graphs

What do social networks have in common with booking cheap flights around the world? You can represent both of these real-world models as graphs.

A graph is a data structure that captures relationships between objects. It’s made up of vertices connected by edges.

Circles in the graph below represent the vertices, and the edges are the lines that connect them.

A graph

Types of Graphs

Graphs come in a few different flavors. The following sections will describe their characteristics.

Weighted Graphs

In a weighted graph, every edge has a weight associated with it that represents the cost of using this edge. These weights let you choose the cheapest or shortest path between two vertices.

Take the airline industry as an example. Here’s a network with varying flight paths:

$50TokyoDetroitWashington, DCAustin, TexasSeattleSan FranciscoSingapore$300$600$300$500$450$250$292$277$337$218$297Hong KongA weighted graph

In this example, the vertices represent cities, while the edges represent a route from one city to another. The weight associated with each edge represents the airfare between the two cities. Using this network, you can determine the cheapest flights from San Francisco to Singapore for all those budget-minded digital nomads out there!

Directed Graphs

As well as assigning a weight to an edge, your graphs can also have direction. Directed graphs are more restrictive to traverse because an edge may only permit traversal in one direction. The diagram below represents a directed graph.

TokyoWashington, DCAustin, TexasSan FranciscoSingaporeHong KongA directed graph

You can tell a lot from this diagram:

  • There’s a flight from Hong Kong to Tokyo.
  • There’s no direct flight from San Francisco to Tokyo.
  • You can buy a roundtrip ticket between Singapore and Tokyo.
  • There is no way to get from Tokyo to San Francisco.

Undirected Graphs

You can think of an undirected graph as a directed graph where all edges are bi-directional.

In an undirected graph:

  • Two connected vertices have edges going back and forth.
  • The weight of an edge applies to both directions.

TokyoWashington, DCAustin, TexasSan FranciscoSingaporeHong KongAn undirected graph

Common Operations

There are a number of common operations that any graph needs to implement. Before you get to those, though, you need the basic building blocks, that is, the vertices and edges.

Open up the starter project for this chapter. Create a new lib folder in the root of the project, and create a file in there named graph.dart.

Defining a Vertex

The image below shows a collection of vertices. They’re not yet a graph:

TokyoWashington, DCDetroitSan FranciscoSingaporeHong KongUnconnected vertices

To represent those vertices, add the following class inside graph.dart:

class Vertex<T> {
  const Vertex({
    required this.index,
    required this.data,
  });

  final int index;
  final T data;

  @override
  String toString() => data.toString();
}

Here, you’ve defined a generic Vertex class. A vertex has a unique index within its graph and holds a piece of data.

Defining an Edge

To connect two vertices, there must be an edge between them. These are the lines in the image below:

TokyoWashington, DCDetroitSan FranciscoSingaporeHong KongEdges added to the collection of vertices

Add an Edge class to graph.dart:

class Edge<T> {
  const Edge(
    this.source,
    this.destination, [
    this.weight,
  ]);

  final Vertex<T> source;
  final Vertex<T> destination;
  final double? weight;
}

Edge connects two vertices and has an optional weight. Not too complicated, is it?

Defining a Graph Interface

Now it’s time to define the common operations that the various flavors of graphs all share.

Start by creating an EdgeType enum and adding it to graph.dart:

enum EdgeType { directed, undirected }

This will allow you to specify whether the particular graph you’re constructing has directed or undirected edges.

Now add the following Graph interface below EdgeType:

abstract class Graph<E> {
  Iterable<Vertex<E>> get vertices;

  Vertex<E> createVertex(E data);

  void addEdge(
    Vertex<E> source,
    Vertex<E> destination, {
    EdgeType edgeType,
    double? weight,
  });

  List<Edge<E>> edges(Vertex<E> source);

  double? weight(
    Vertex<E> source,
    Vertex<E> destination,
  );
}

This interface describes the common operations for a graph:

  • vertices: Returns all of the vertices in the graph.
  • createVertex: Creates a vertex and adds it to the graph.
  • addEdge: Connects two vertices in the graph with either a directed or undirected edge. The weight is optional.
  • edges: Returns a list of outgoing edges from a specific vertex.
  • weight: Returns the weight of the edge between two vertices.

In the following sections, you’ll implement this interface in two ways, first using what’s called an adjacency list, and second an adjacency matrix. Keep reading to find out what these terms mean.

Adjacency List

The first graph implementation that you’ll learn uses an adjacency list. For every vertex in the graph, the graph stores a list of outgoing edges.

Take the flight network you saw earlier as an example:

TokyoWashington, DCDetroitSan FranciscoSingaporeHong Kong

You can describe the relationship between the cities in this graph by listing out the adjacent cities for each location:

TokyoTokyoTokyoTokyoSingaporeSingaporeSan FranciscoDetroitHong KongWashington DCWashington DCHong KongSan FranciscoHong KongSingaporeHong KongTokyoDetroitWashington DCSan FranciscoVerticesAdjacency listsAn adjacency list

There’s a lot you can learn from this adjacency list:

  1. Singapore’s vertex has two outgoing edges, one to Tokyo and another to Hong Kong.
  2. Detroit has the smallest number of outgoing flights.
  3. Tokyo is the busiest airport, with the most outgoing flights.

In the next section, you’ll create an adjacency list by storing a map of lists. Each key in the map is a vertex, and the value is the corresponding list of edges.

Implementation

An adjacency list is a graph, so you need to implement the Graph interface that you created earlier. Add the following code to graph.dart:

class AdjacencyList<E> implements Graph<E> {

  final Map<Vertex<E>, List<Edge<E>>> _connections = {};
  var _nextIndex = 0;

  @override
  Iterable<Vertex<E>> get vertices => _connections.keys;

  // more to come ...
}

You’ve defined an AdjacencyList class that uses a map to store the outgoing edges for each vertex. You’ll use _nextIndex to assign a unique index to each new vertex. If you need the vertices, you can obtain them from the vertices getter.

You still need to implement the various other methods of the Graph interface. You’ll do that in the following sections.

Creating a Vertex

Add the missing createVertex method to AdjacencyList:

@override
Vertex<E> createVertex(E data) {
  // 1
  final vertex = Vertex(
    index: _nextIndex,
    data: data,
  );
  _nextIndex++;
  // 2
  _connections[vertex] = [];
  return vertex;
}

Here’s what’s happening:

  1. You first create a new vertex with a unique index.
  2. Then you add the vertex as a key in the _connections map. You haven’t connected it to any other vertices in the graph yet, so the list of outgoing edges is empty.

Adding an Edge

To connect two vertices, you need to add an edge. Recall that there are directed and undirected edges:

DirectedUndirected

Every edge in an undirected graph can be traversed in both directions. So if it’s an undirected graph, you need to add two edges, one from the source to the destination and another from the destination to the source.

Add the following method to AdjacencyList:

@override
void addEdge(
  Vertex<E> source,
  Vertex<E> destination, {
  EdgeType edgeType = EdgeType.undirected,
  double? weight,
}) {
  // 1
  _connections[source]?.add(
    Edge(source, destination, weight),
  );
  // 2
  if (edgeType == EdgeType.undirected) {
    _connections[destination]?.add(
      Edge(destination, source, weight),
    );
  }
}

Here’s what’s happening in the method body:

  1. Since source is a vertex, check if it exists in the _connections map. If it does, create a new directed edge from the source to the destination. Then add it to the vertex’s list of edges.
  2. If this is an undirected graph, then also add an edge going the other direction.

Retrieving the Outgoing Edges From a Vertex

Continue your work on implementing Graph by adding the edges method to AdjacencyList:

@override
List<Edge<E>> edges(Vertex<E> source) {
  return _connections[source] ?? [];
}

This gets the stored outgoing edges for the provided vertex. If source is unknown, the method returns an empty list.

Retrieving the Weight of an Edge

Recall that the weight is the cost of going from one vertex to another. For example, if the cost of a ticket between Singapore and Tokyo is $500, the weight of this bidirectional edge is 500:

TokyoSingapore$300$250$500Hong Kong

Implement the missing weight method in AdjacencyList by adding the following code to the class:

@override
double? weight(
  Vertex<E> source,
  Vertex<E> destination,
) {
  final match = edges(source).where((edge) {
    return edge.destination == destination;
  });
  if (match.isEmpty) return null;
  return match.first.weight;
}

Here, you search for an edge from source to destination. If it exists, you return its weight.

Making Adjacency List Printable

The required methods for AdjacencyList are complete now, but it would also be nice to be able to print a description of your graph. To do that, override toString like so:

@override
String toString() {
  final result = StringBuffer();
  // 1
  _connections.forEach((vertex, edges) {
    // 2
    final destinations = edges.map((edge) {
      return edge.destination;
    }).join(', ');
    // 3
    result.writeln('$vertex --> $destinations');
  });
  return result.toString();
}

Here’s what’s going on in the code above:

  1. You loop through every key-value pair in _connections.
  2. For every vertex, find all of the destinations and join them into a single, comma-separated string.
  3. Put each vertex and its destinations on a new line.

This will produce output with lines in the following format:

Singapore --> Hong Kong, Tokyo

You’ve finally completed your first graph! Try it out by building a network in the next section.

Building a Network

For this example, you’ll go back to the diagram you saw earlier and construct a network of flights with the prices as weights:

$50TokyoDetroitWashington, DCAustin, TexasSeattleSan FranciscoSingapore$300$600$300$500$450$250$292$277$337$218$297Hong Kong

Open bin/starter.dart and replace the contents of the file with the following code:

import 'package:starter/graph.dart';

void main() {
  final graph = AdjacencyList<String>();

  final singapore = graph.createVertex('Singapore');
  final tokyo = graph.createVertex('Tokyo');
  final hongKong = graph.createVertex('Hong Kong');
  final detroit = graph.createVertex('Detroit');
  final sanFrancisco = graph.createVertex('San Francisco');
  final washingtonDC = graph.createVertex('Washington DC');
  final austinTexas = graph.createVertex('Austin Texas');
  final seattle = graph.createVertex('Seattle');

  graph.addEdge(singapore, hongKong, weight: 300);
  graph.addEdge(singapore, tokyo, weight: 500);
  graph.addEdge(hongKong, tokyo, weight: 250);
  graph.addEdge(tokyo, detroit, weight: 450);
  graph.addEdge(tokyo, washingtonDC, weight: 300);
  graph.addEdge(hongKong, sanFrancisco, weight: 600);
  graph.addEdge(detroit, austinTexas, weight: 50);
  graph.addEdge(austinTexas, washingtonDC, weight: 292);
  graph.addEdge(sanFrancisco, washingtonDC, weight: 337);
  graph.addEdge(washingtonDC, seattle, weight: 277);
  graph.addEdge(sanFrancisco, seattle, weight: 218);
  graph.addEdge(austinTexas, sanFrancisco, weight: 297);

  print(graph);
}

Run that and you should get the following output:

Singapore --> Hong Kong, Tokyo
Tokyo --> Singapore, Hong Kong, Detroit, Washington DC
Hong Kong --> Singapore, Tokyo, San Francisco
Detroit --> Tokyo, Austin Texas
San Francisco --> Hong Kong, Washington DC, Seattle, Austin Texas
Washington DC --> Tokyo, Austin Texas, San Francisco, Seattle
Austin Texas --> Detroit, Washington DC, San Francisco
Seattle --> Washington DC, San Francisco

This output shows a visual description of an adjacency list graph. You can see all the outbound flights from any city. Pretty nice, huh?

Finding the Weight

You can also obtain other helpful information such as the cost of a flight from Singapore to Tokyo. This is the weight of the edge between those two vertices.

Add the following code at the bottom of the main function:

final cost = graph.weight(singapore, tokyo)?.toInt();
print('It costs \$$cost to fly from Singapore to Tokyo.');
// It costs $500 to fly from Singapore to Tokyo.

Getting the Edges

Do you need to know what all the outgoing flights from San Francisco are? For that, you just call edges.

Add the code below at the bottom of main:

print('San Francisco Outgoing Flights: ');
print('-------------------------------- ');
for (final edge in graph.edges(sanFrancisco)) {
  print('${edge.source} to ${edge.destination}');
}

Running than will display the flights:

San Francisco Outgoing Flights:
--------------------------------
San Francisco to Hong Kong
San Francisco to Washington DC
San Francisco to Seattle
San Francisco to Austin Texas

You’ve just created an adjacency list graph, which uses a map to store the outgoing edges for every vertex. In the next section you’ll learn a different approach to store vertices and edges.

Adjacency Matrix

An adjacency matrix uses a two-dimensional grid or table to implement the graph data structure. Each vertex has its own row and column in the table. The cells where rows and columns intersect hold the edge weights. If any particular cell is empty, that is, if the weight is null, then that means there is no edge between the row vertex and the column vertex.

Below is an example of a directed graph that depicts a flight network. As before, the weight represents the cost of the airfare:

TokyoWashington, DCSan FranciscoSingaporeHong Kong$300$500$300$600$250

You can represent that network in matrix form by giving each of the five cities a row and a column in a table. Edges that don’t exist between two cities are shown with a weight of 0 in the cells where the rows and columns intersect:

SingaporeHong KongTokyoWashington DCSan FranciscoVertices01234DestinationSource00000$300000$250000$300$500$500$300000000$60000011223344

Notes:

  • As you recall, every vertex in a graph has its own index. These indices are used to label the rows and columns in the table.
  • Read the row number as the source vertex and the column number as the destination vertex.
  • There’s a red line going down the middle of the matrix. When the row and column are equal, this represents an edge between a vertex and itself, which isn’t allowed. You can’t fly from Singapore to Singapore, right?

Here are a few examples of data points that you can read from the table above:

  • [0][1] is 300, so there is a flight from Singapore to Hong Kong for $300.
  • [2][1] is 0, so there’s no flight from Tokyo to Hong Kong.
  • [1][2] is 250, so there is a flight from Hong Kong to Tokyo for $250.
  • [2][2] is 0 because there’s no flight from Tokyo to Tokyo!

You’ll implement an adjacency matrix graph next.

Implementation

Add a new class to graph.dart called AdjacencyMatrix:

class AdjacencyMatrix<E> implements Graph<E> {

  final List<Vertex<E>> _vertices = [];
  final List<List<double?>?> _weights = [];
  var _nextIndex = 0;

  @override
  Iterable<Vertex<E>> get vertices => _vertices;

  // more to come ...
}

In AdjacencyList you used a map to store the vertices and edges. Here, though, you store the vertices in a list. You don’t use Edge to store edges but rather a two-dimensional list of weights.

You’ve declared that you’re implementing Graph, and so far you’ve only finished vertices. The following sections will help you add the other missing methods.

Creating a Vertex

For every new vertex that you create, you have to add an additional column and row to the matrix.

The first step is to create a new column by adding an additional empty destination at the end of every row. The destination is empty because no other vertices have created an edge to the new vertex yet. In the following diagram you can see a new column 5 filled with empty weights:

Destination+Source00000$30000000$250000000$300$500$500$300000000$600000112233454

The next step is to add an additional row representing a new source vertex. The weights for this, too, are empty since you haven’t yet added any edges. Row 5 in the image below shows the newly added source row:

DestinationSource000000000000$3000000$2500000$300$5000$500$3000000000$60000011223345+45

To implement the description above, add the createVertex method to AdjacencyMatrix:

@override
Vertex<E> createVertex(E data) {
  // 1
  final vertex = Vertex(
    index: _nextIndex,
    data: data,
  );
  _nextIndex++;
  _vertices.add(vertex);
  // 2
  for (var i = 0; i < _weights.length; i++) {
    _weights[i]?.add(null);
  }
  // 3
  final row = List<double?>.filled(
    _vertices.length,
    null,
    growable: true,
  );
  _weights.add(row);
  return vertex;
}

To create a vertex in an adjacency matrix, you perform the following tasks:

  1. Add a new vertex to the list.
  2. Append a null value at the end of every row. This in effect creates a new destination column in the matrix.
  3. Add a new row to the matrix, again filled with null weight values.

Adding Edges

Creating edges is as simple as adding weights to the matrix. There’s no Edge class to worry about.

Add the missing addEdge method to AdjacencyMatrix:

@override
void addEdge(
  Vertex<E> source,
  Vertex<E> destination, {
  EdgeType edgeType = EdgeType.undirected,
  double? weight,
}) {
  // 1
  _weights[source.index]?[destination.index] = weight;
  // 2
  if (edgeType == EdgeType.undirected) {
    _weights[destination.index]?[source.index] = weight;
  }
}

The logic here is similar to how you implemented addEdge in AdjacencyList previously:

  1. Always add a directed edge.
  2. If the edge type for the graph is undirected, then also add another edge going from the destination to the source.

Retrieving the Outgoing Edges From a Vertex

Add the edges method to AdjacencyMatrix:

@override
List<Edge<E>> edges(Vertex<E> source) {
  List<Edge<E>> edges = [];
  // 1
  for (var column = 0; column < _weights.length; column++) {
    final weight = _weights[source.index]?[column];
    // 2
    if (weight == null) continue;
    // 3
    final destination = _vertices[column];
    edges.add(Edge(source, destination, weight));
  }
  return edges;
}

Remember that the columns represent destinations and that a source is a row:

  1. To find all the edges for some source, you loop through all the values in a row.
  2. Check for weights that aren’t null. Every non-null weight implies an outgoing edge.
  3. Use the column to look up the destination vertex.

Retrieving the Weight of an Edge

It’s easy to get the weight of an edge. Simply look up the value in the adjacency matrix.

Implement weight like so:

@override
double? weight(Vertex<E> source, Vertex<E> destination) {
  return _weights[source.index]?[destination.index];
}

Making an Adjacency Matrix Printable

Finally, override toString so you can print out a readable description of your graph:

@override
String toString() {
  final output = StringBuffer();
  // 1
  for (final vertex in _vertices) {
    output.writeln('${vertex.index}: ${vertex.data}');
  }
  // 2
  for (int i = 0; i < _weights.length; i++) {
    for (int j = 0; j < _weights.length; j++) {
      final value = (_weights[i]?[j] ?? '.').toString();
      output.write(value.padRight(6));
    }
    output.writeln();
  }
  return output.toString();
}

Here are the steps:

  1. You first create a list of the vertices.
  2. Then you build up a grid of weights, row by row.

Building a Network

You will reuse the same example from AdjacencyList:

$50TokyoDetroitWashington, DCAustin, TexasSeattleSan FranciscoSingapore$300$600$300$500$450$250$292$277$337$218$297Hong Kong

Go back to the main method in bin/starter.dart and replace this:

final graph = AdjacencyList<String>();

with the following:

final graph = AdjacencyMatrix<String>();

AdjacencyMatrix and AdjacencyList conform to the same Graph interface, so the rest of the code stays the same.

Run the code. The print(graph) portion of the code should give the following output:

0: Singapore
1: Tokyo
2: Hong Kong
3: Detroit
4: San Francisco
5: Washington DC
6: Austin Texas
7: Seattle
.     500.0 300.0 .     .     .     .     .     
500.0 .     250.0 450.0 .     300.0 .     .     
300.0 250.0 .     .     600.0 .     .     .     
.     450.0 .     .     .     .     50.0  .     
.     .     600.0 .     .     337.0 297.0 218.0
.     300.0 .     .     337.0 .     292.0 277.0
.     .     .     50.0  297.0 292.0 .     .     
.     .     .     .     218.0 277.0 .     .

Graph Analysis

This chart compares the cost of different graph operations for adjacency lists and adjacency matrices. V represents the number of vertices, and E represents the number of edges.

OperationsStorage SpaceAdd VertexAdd EdgeFinding Edges and Weight0(V + E)0(1)0(1)0(V)0(V )220(V )0(1)0(1)Adjacency ListAdjacency Matrix

An adjacency list takes less storage space than an adjacency matrix. An adjacency list simply stores the number of vertices and edges needed. As for an adjacency matrix, recall that the number of rows and columns equals the number of vertices. This explains the quadratic space complexity of O(V²).

Adding a vertex is efficient in an adjacency list: Simply create a vertex and set its key-value pair in the map. It’s amortized as O(1). When adding a vertex to an adjacency matrix, you must add a column to every row and create a new row for the new vertex. This is at least O(V), and if you choose to represent your matrix with a contiguous block of memory, it can be O(V²).

Adding an edge is efficient in both data structures since they are both constant time. The adjacency list appends to the list of outgoing edges. The adjacency matrix simply sets a value in the two-dimensional list.

Adjacency list loses out when trying to find a particular edge or weight. To find an edge in an adjacency list, you have to obtain the list of outgoing edges and loop through every edge to find a matching destination. This happens in O(V) time. With an adjacency matrix, finding an edge or weight is a constant-time lookup in the two-dimensional list.

So which data structure should you choose to construct your graph?

If there are few edges in your graph, it’s considered a sparse graph, and an adjacency list would be a good fit. An adjacency matrix would be a bad choice for a sparse graph because a lot of memory would be wasted since there aren’t many edges.

If your graph has lots of edges, it’s considered a dense graph, and an adjacency matrix would be a better fit since you’d be able to access your weights and edges far more quickly.

Note

A dense graph in which every vertex has an edge to every other vertex is called a complete graph.

In the next few chapters you’ll learn different algorithms for visiting the nodes of a graph.

Challenges

Here’s a challenge for you to apply your newfound knowledge of graphs. You can find the answer in the Challenge Solutions section as well as in the supplemental materials that accompany this book.

Challenge 1: Graph Your Friends

Megan has three friends: Sandra, Pablo and Edith. Pablo has friends as well: Ray, Luke, and a mutual friend of Megan’s. Edith is friends with Manda and Vicki. Manda is friends with Pablo and Megan. Create an adjacency list that represents this friendship graph. Which mutual friend do Pablo and Megan share?

Key Points

  • You can represent real-world relationships through vertices and edges.
  • Think of vertices as objects and edges as the relationships between the objects.
  • Weighted graphs associate a number with every edge.
  • Directed graphs have edges that traverse in one direction.
  • Undirected graphs have edges that point both ways.
  • An adjacency list is a graph that stores a list of outgoing edges for every vertex.
  • An adjacency matrix uses a two-dimensional list to represent a graph.
  • An adjacency list is generally good for sparse graphs, which have a low number of edges.
  • An adjacency matrix is generally suitable for dense graphs, which have lots of edges.