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 };Show how the following graph could be stored using the given representations.
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);
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?
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.
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).
For the following graph:
give examples of the smallest and largest of each of the following: