Graphs

Objectives

  • Explain common terms used when discussing graphs
  • Create and use graphs to solve problems
  • Use C++ to implement graph algorithms

Graph terminology

Graphs consist of a set of vertices (singular is vertex) and a set of edges. A vertex is basically the same abstract concept as a node. A vertex often represents a location, a state, or a phase. Vertices are connected by edges. Usually an edge connects two vertices, but an edge may be a loop back to the same vertex it started from. Parallel edges are those edges, if any, that both start on the same vertex as each other and lead to the same vertex as each other.

Each vertex will typically have a label (name). The edges may represent a connection that can be travelled in either direction, or they may be directed, such as going from vertex A to vertex B, but not from B to A. The edges may also be weighted, where the weights stand for distance, time, cost, etc. Graphs with non-weighted edges may be represented in the more general graph that allows weights by automatically setting all edges to the same weight (typically 1).

A graph which contains directed edges is called a directed graph. A graph without directed edges is called an undirected graph. Graphs made be made up of one or more connected components, where a connected component consists of a set of nodes which are all connected to each other through edges. Some graphs contain two or more connected components (the separate components do not connect to each other).

Vertex B is said to be a neighbor of vertex A if an edge exists in the graph that allows travel from vertex A to vertex B. The degree of a vertex is the number of neighbors that it has.

A path is a series of edges that connect two vertices. A path that begins and ends with the same vertex is called a cycle. A path which does not visit the same vertex more than once is called a simple path. A DAG (directed acyclic graph) is a directed graph which contains no cycles.

Computer representations

There are numerous ways of representing graphs within computer storage. We will create our own classes to represent a vertex and an edge. Once you have those represented, it is fairly easy to create a list of vertices and a list of edges. The list concept makes a lot of sense for vertex and edge lists since it is quite common to not know how many there are until the data has been read in.

There are a couple of other standard representations of graphs that can be quite useful for solving problems. One is called an adjacency list. An adjacency list has one element corresponding to each vertex. Each of those elements is a linked list of edge descriptions, one per edge leading away from that vertex. To find all the neighbors of a vertex, you just have to traverse that node's list in the adjacency list.

Another standard representation is an adjacency matrix. It is a two dimensional array-type structure which holds the weight of every edge in the graph. If you want to find out if there is an edge between node 5 and node 7, you just check out the value at adjacency_matrix[5][7]. If the value is 0, then there is no edge. Otherwise, the value gives the weight of the edge. This representation doesn't work if parallel edges exist.

Common graph tasks

Some of the most common graph tasks include searching/traversing a graph, finding a minimum spanning tree for a graph, and finding the shortest path between two vertices. We have already looked at traversing binary trees in class and seen that there are different methods for doing a simple traversal. For binary trees, we examined preorder, inorder, and postorder traversals. For graphs we will be looking at depth-first searches/traversals (DFS) and breadth-first searches/traversals (BFS). We will also discuss finding a shortest path and finding a minimal spanning tree of the graph.

Web References

Provided code

  • Specification code (.h)
  • Starting code
    • edge.cpp: implementation of an edge (starting place)
    • vertex.cpp: implementation of a vertex (starting place)
    • tovert.cpp: implementation of a "to vertex" (starting place)
    • graph.cpp: implementation of a graph (starting place)
  • Implementation
  • Test data for graph: grdata.txt
  • We will also need to write a test driver to make sure this all works when we are done.