Lecture Preview: Graphs

(Suggested book reading: Programming Abstractions in C++, Chapter 18 sections 18.1, 18.4)

Today we'll learn about a new abstract data type (ADT) called a graph. A graph is a generalization of a list or tree into a more flexible structure that contains a set of vertices (sometimes called nodes) and a set of edges (sometimes called arcs) from one vertex to another. In the figure below:

  • V = {a, b, c, d}
  • E = {(a, c), (b, c), (b, d), (c, d)}

graph

Graphs are extremely powerful and useful data structures. A wide variety of problems can be solved using graphs, such as finding friends in a social network, searching for paths in a maze, AI decision-making, finding the cheapest airline flights, and many, many more.

Some graphs are weighted, meaning that each edge has a certain cost associated with it. For example, in the graph below, the weights might represent the number of miles between various cities.

weighted graph

Some graphs are directed, meaning that each edge can be traversed in only one direction. For example, in the graph below, you can travel from vertex a to d but not vice versa.

directed graph

We will follow two different algorithm sfor searching for paths in graphs, depth-first search (DFS) and breadth-first search BFS. A breadth-first search (BFS) is guaranteed to find the shortest path between two vertices. A depth-first search (DFS) is not.

This document and its content are copyright © Marty Stepp and Julie Zelenski, 2019. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.