Tutorial Solutions Week 05 - Graph Implementations

Exercise 1

In lectures we have looked at two different implemtations of graphs. Adjacency matrices and adjacency lists. See representations below:

//Graph.h definitions
// vertices denoted by integers 0..N-1 
typedef struct graphRep * Graph;
typedef int Vertex; 
typedef struct edge Edge;

// edges are pairs of vertices (end-points) 
struct edge { 
    Vertex v; 
    Vertex w; 
} ;

//Adjacency matrix unweighted graph representation

struct graphRep { 
    int nV;        // #vertices 
    int nE;       // #edges 
    int **adj; // matrix of booleans (0 or 1)
}; 

//Adjacency list graph representation
typedef struct vNode *VList;
struct vNode { 
    Vertex v; 
    VList next; 
}; 

struct graphRep { 
    int nV; // #vertices 
    int nE; // #edges VList 
    VList *adj; // array of lists 
};

Exercise 2

Implement a function that tests whether a given graph edge is present in the graph. The function should return 1 if the edge exists in the graph and 0 otherwise. Use the following prototype. Implement the function for both the adjacency-matrix and the adjacency-list representations.

 int isEdgeInGraph (Graph G, Edge e); 

Exercise 3

How could you change the implementations in Exercise 1 to represent a weighted graph with weights of type int? Would your implementations of isEdgeInGraph need to change?

Excercise 4

Edge *edges(Graph g, int *nE) { ... }
// which would be used as ...
Edge *es;  int n;   es = edges(g, &n);

Implement this edges() function for each of the two Graph representations. It should return the edges in normalised/canonical form (e.v < e.w), so that each edge appears exactly once in the result array.

Exercise 5

Consider the adjacency matrix and adjacency list representations for graphs. Analyse the storage costs for the two representations in terms of the number of vertices V and the number of edges E and determine roughly the point at which it is more storage efficient to use an adjacency matrix representation vs the adjacenty list representation.

For the purposes of the analysis, ignore the cost of storing the GraphRep structure. Assume that: each pointer is 4 bytes long, a Vertex value is 4 bytes a linked-list node is 8 bytes long, that the adjacency matrix is a complete V×V matrix, and each adjacency matrix element is 1 byte long (bool).

Exercise 6

For the following graph:

give examples of the smallest and largest of each of the following:

1. path
2. cycle
3. spanning tree
4. clique