COMP2521
Data Structures & Algorithms
Week 5.2
Graph Implementations
1
In this lecture
Why?
Different graph implementations have different pros and
cons, and we should try and understand the difference
What?
Array of edges graph
Adjacency Matrix graph
Adjacency List graph
2
Properties of Graphs
Terminology: |V| and |E| (cardinality) normally written just as V and E
A graph with V vertices has at most V(V – 1) / 2 edges
The ratio E:V can vary considerably:
If E is closer to V^2, the graph is dense
If E is closer to V, the graph is sparse
Thinking about these things may help us decide on an appropriate data
structure
3
Graph Representations
There are many ways to represent the same graph. E.G. The same
graph could be represented these ways:
4 . 1
Graph Representations
There are 3 key different graph implementations we will discuss:
Array of Edges
Explicit representation as list of
(v,w) vertex pairs
Adjacency Matrix
Edges defined by presence value
in V*V matrix
Adjacency List
Edges defined by entries in
array of V lists
4 . 2
Array-of-edges
Stored as an array of Edges (i.e. array of vertex pairs)
Space efficient
Adding/deleting: Mildly complex
Lookup: Mildly complex
For directed graphs, the ordering of vertices within an edge pair denote direction
5 . 1
Array-of-edges Implementation
typedef struct GraphRep {
Edge *edges; // array of edges
int nV; // #vertices (numbered 0..nV-1)
int nE; // #edges
int n; // size of edge array
} GraphRep;
1
2
3
4
5
6
5 . 2
Array-of-edges Pseudocode
newGraph(V):
g = new Graph with V verticies
g.nV = V // #vertices (numbered 0..V-1)
g.nE = 0 // #edges
allocate enough memory for g.edges[]
return g
1
2
3
4
5
6
insertEdge(g,(v,w)):
i=0
while i < g.nE ∧ g.edges[i] ≠ (v,w):
i = i + 1
if i = g.nE: // (v,w) not found
g.edges[i] = (v,w)
g.nE = g.nE + 1
1
2
3
4
5
6
7
removeEdge(g,(v,w)):
i = 0
while i < g.nE ∧ g.edges[i] ≠ (v,w):
i = i + 1
if i < g.nE: // (v,w) found
g.edges[i] = g.edges[g.nE-1]
g.nE = g.nE - 1
1
2
3
4
5
6
7
showEdges(g):
for all i=0 to g.nE-1:
(v,w) = g.edges[i]
print v"—"w
1
2
3
4
5 . 3
Array-of-edges Implementation
Full implementation in Graph-array-edges.c
5 . 4
Array-of-edges, Cost Analysis
Storage: O(E)
Operations:
Initialisation: O(1)
Insert edge: O(E)
Delete edge: O(E)
Search: O(E)
Other factors:
If array is full on insert, realloc - still O(E) amortized
Maintaining edges in order will allow for O(log(E))
binary search lookup
5 . 5
Adjacency Matrix
Stored as a 2D array (i.e. table) of edges. Easy to implement. Not
memory efficient for sparse graphs.
For undirected graphs, the table is a mirror about the diagonal
6 . 1
Adjacency Matrix Implementation
typedef struct GraphRep {
int **edges; // adjacency matrix
int nV; // #vertices
int nE; // #edges
} GraphRep;
1
2
3
4
5
6 . 2
Adjacency Matrix Pseudocode
newGraph(V):
g.nV = V // #vertices (numbered 0..V-1)
g.nE = 0 // #edges
allocate memory for g.edges[][]
for all i,j=0..V-1:
g.edges[i][j] = 0 // false
return g
1
2
3
4
5
6
7
insertEdge(g,(v,w)):
if g.edges[v][w] = 0: // (v,w) not in graph
g.edges[v][w]=1 // set to true
g.edges[w][v]=1
g.nE=g.nE+1
1
2
3
4
5
removeEdge(g,(v,w)):
if g.edges[v][w] ≠ 0: // (v,w) in graph
g.edges[v][w]=0 // set to false
g.edges[w][v]=0
g.nE=g.nE - 1
1
2
3
4
5
showEdges(g):
for all i=0 to g.nV-1:
for all j=i+1 to g.nV-1:
if g.edges[i][j] ≠ 0 then
print i"—"j
1
2
3
4
5
6 . 3
Adjacency Matrix Implementation
Full implementation in Graph-adj-matrix.c
6 . 4
Adjacency Matrix, Cost Analysis
Storage: O(V^2)
If the graph is sparse, most space is wasted
Operations:
Initialisation: O(V^2)
Insert edge: O(1)
Delete edge: O(1)
Search: O(1)
Other factors:
For undirected graphs, the matrix is repeated about a
diagonal axis. We can have a coefficient improvement
in time complexity if we only store on one half of the
diagonal
6 . 5
Adjacency List
Stored as a 2D array (i.e. table) of edges. Easy to implement. Not
memory efficient for sparse graphs.
For undirected graphs, the table is a mirror about the diagonal
7 . 1
Adjacency List Implementation
typedef struct GraphRep {
Node **edges; // array of lists
int nV; // #vertices
int nE; // #edges
} GraphRep;
// Assumes we also have
typedef struct Node {
Vertex v;
struct Node *next;
} Node;
// with operations inLL, insertLL, deleteLL, freeLL
1
2
3
4
5
6
7
8
9
10
11
12
7 . 2
Adjacency List Pseudocode
newGraph(V):
g.nV = V // #vertices (numbered 0..V-1)
g.nE = 0 // #edges
allocate memory for g.edges[]
for all i=0..V-1:
g.edges[i]=newList() // empty list
return g
1
2
3
4
5
6
7
insertEdge(g,(v,w)):
if not ListMember(g.edges[v],w):
// (v,w) not in graph
ListInsert(g.edges[v],w)
ListInsert(g.edges[w],v)
g.nE=g.nE+1
1
2
3
4
5
6
removeEdge(g,(v,w)):
if ListMember(g.edges[v],w):
// (v,w) in graph
ListDelete(g.edges[v],w)
ListDelete(g.edges[w],v)
g.nE=g.nE-1
1
2
3
4
5
6
showEdges(g):
for all i=0 to g.nV-1:
for all v in g.edges[i]:
if i < v:
print i"—"v
1
2
3
4
5
7 . 3
Adjacency List Implementation
Full implementation in Graph-adj-list.c
7 . 4
Adjacency List, Cost Analysis
Storage: O(V + E)
Operations:
Initialisation: O(V)
Insert edge: O(V)
Delete edge: O(V)
Search: O(V)
Other factors:
Sorting vertex lists has no benefit
7 . 5
Comparison of Graph Implementations
Terminology: |V| and |E| (cardinality) normally written just as V and E
A graph with V vertices has at most V(V - 1) / 2 edges
Array of edges Adjacency Matrix Adjacency List
Space usage E V^2 V + E
Initialise 1 V^2 V
Insert edge E 1 V
Remove edge E 1 V
isPath(x,y) E*log(V) V^2 V + E
Copy graph E V^2 V + E
Destroy Graph 1 V V + E
Search E 1 V
8
Feedback
9