Lab Week 9: Graphs

Graphs are defined as consisting of a set V of vertices and a set E of edges. Edges are further defined as being either an ordered pair of vertices (in the case of a directed graph), or an unordered pair (in the case of an undirected graph).

Implementation

The two primary ways that graphs are implemented are as an adjacency matrix or as an adjacency list. An adjacency matrix consists of a two dimensional array where the indices map to the vertices and the intersections between every pair of vertices indicate whether there is an edge connecting them and if so what the weight of that edge is (in the case of a weighted graph). The image below should help to illustrate this.

This class definition should help give you an idea of where to start when implementing a graph as an adjacency matrix.

class AdjacencyMatrix{
    private:
        int n;
        int **adj;
        bool *visited;
    public:
        AdjacencyMatrix(int n);
        ~AdjacencyMatrix();
        void add_edge(int origin, int destin, int weight);
        void display();
        /* etc. */
};

Adjacency lists conserve more space by using lists of edges stored at each vertex to represent adjacencies instead of an n by n matrix. In an adjacency list we store a list for each node that contains the edges for that node. Each element in that list represents an edge in the graph and contains information such as the starting and ending vertices as well as the edge weight. The image below illustrates this.

Exercise 1

Implement a directed Graph class using the Adjacency Matrix approach. Feel free to use the code given above to help you get started.

Exercise 2

Add a member function BFS that returns an array of distance from a given node.

Exercise 3

A cycle is any point in a graph where it is possible to travel in a loop. For example; there is an edge from A to B, from B to C, and from C back to A. Write a member function that detects whether your graph contains any cycles and returns true or false respectively.

(Hint: How can you use/modifiy BFS to accomplish this?)

Exercise 4

Write a member function that, given a starting vertex and an ending vertex, prints out a list of vertices that connect a path between them.