(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:
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.
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.
We will discuss graphs in much more detail this week.
You are expected to follow the Stanford Honor Code.
If this is an assignment that allows pairs, the same rules apply to each team. For example, do not look at assignment solutions that do not belong to your team, and do not give your solution to anyone outside of your team.
Remember that we run similarity-detection software over all solutions, including this quarter and past quarters, as well as any solutions we find on the web.
If you need help solving an assignment, we are happy to help you. You can go to the LaIR, or the course message forum, or email your section leader, or visit the instructor / head TA during office hours. You can do it!