Overview

There are many problems that can’t be represented and solved using the linear or tree structures that we’ve seen so far. To tackle these problems, we need a more general structure that allows us to have nodes connected to any number of other nodes. This kind of structure is called a graph. Today we’ll be focused on the two main ways that we can implement a graph in programming.

Basic Learning Objectives

Before class, you should be able to:

  • Explain what nodes and vertices (plural of vertex) are in a graph
  • Explain the difference between an adjacency matrix and adjacency list

Advanced Learning Objectives

After class, you should be able to:

  • Explain how to add nodes/vertices and edges to a graph & how to check if nodes/vertices and edges are in a graph
  • Demonstrate how to represent graphs in both adjacency matrix and list form
  • Decide whether to use a matrix or list implementation of a graph based on the constraints of a given problem

Reading

You should read the following:

Checks

Submit your answers to the following on Moodle.

Given the following graph:

Graph

  1. Draw out the graph represented as an adjacency matrix.
  2. Draw out the graph represented as an adjacency list.