Kotlin
Java

Graphs
Kotlin

Created By: Geoffrey Challen
/ Updated: 2021-10-31

This lesson introduces a new data structure: graphs. Graphs are extremely useful, both for modeling certain types of data, and for enabling certain algorithms. In fact, trees, which we've been studying previously, are themselves a type of graph. Graphs are also great for practice with recursion, and you'll also work a bit with them on the MP. So let's get started!

What is a Graph?

Wikipedia defines a graph as:

A graph data structure consists of a finite (and possibly mutable) set of vertices (also called nodes or points), together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges (also called links or lines), and for a directed graph are also known as edges but also sometimes arrows or arcs. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.

Let's look at some diagrams that will help visualize this new data structure, and introduce some important terminology.

Show a diagram of a graph and review various terminology: node, edge, weight. This explanation should be language agnostic!

What Are Graphs For?

Graphs can be used to model a variety of real-world entities, which is part of what makes them so useful to computer scientists. Some examples include:

  • Social graphs, where each node is a person, edges represent friendships or acquaintances, and understanding the graph helps better understand the structure of human relationships.
  • Internet routing, where each node is a machine connected to the internet, edges represent connections between machines, and understanding the graph helps data travel around the world.
  • Transit graphs, where each node is a place on Earth, edges represent transit connections between different locations, and understanding the graph help you travel around the world.

Let's look at these example a bit more:

Go through various examples of graphs in real life, including (but not limited to) the examples listed above. This explanation should be language agnostic.

Types of Graph

Depending on the properties of their edges, graphs can be directed or undirected, weighted or unweighted. We'll focus our attention on undirected unweighted graphs. But let's discuss the differences briefly.

Discuss the various types of graphs and difference between directed and undirected, weighted and unweighted graphs. This explanation should be language agnostic.

Trees v. Graphs

We've discussed trees previously, and it turns out that trees are one specific type of graph. Now that we have been introduced to graphs, we can define a tree more precisely.

Present the definition of a tree as an undirected graph with only one path between any two nodes. This explanation should be language agnostic.

Graph Recursion

Previous we introduced recursion, a problem solving technique that works by breaking down large problems into smaller pieces, solving them, and then combining the results. Graphs are another data structure that we frequently will examine recursively. Let's see why:

Explain why recursion can be a good approach to use with graphs as well as trees. Emphasize the non-linearity of graphs and why that makes them hard to traverse using a loop. This explanation should be language agnostic.

In addition, like trees, compared to lists and arrays and Strings, graphs can be hard to work with using iterative solutions! Recursion is a much better approach...

Recursive Graph Size

To help you prepare for our next homework problem, let's discuss the recursive approach to counting the number of nodes in a graph. Specifically, we'll review the idea of graph traversal, and how not to get stuck along the way.

Use a diagram to show how to count the nodes in a binary tree. This explanation should be language agnostic.

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough