Graph Algorithms (I)
COMP9024: Data Structures and
Algorithms
Graphs (I)
Contents
• Graph terminology
• Adjacency matrix representation
• Adjacency list representation
3
Graphs
ORD
DFW
SFO
LAX
4
Graphs
• A graph is a pair (V, E), where
• V is a set of nodes, called vertices
• E is a collection of pairs of vertices, called edges
• Vertices and edges are positions and store elements
• Example:
• A vertex represents an airport and stores the three-letter airport code
• An edge represents a flight route between two airports and stores the
mileage of the route
ORD PVD
MIA
DFW
SFO
LAX
LGA
HNL
5
Edge Types
• Directed edge
• ordered pair of vertices (u,v)
• first vertex u is the origin
• second vertex v is the destination
• e.g., a flight
• Undirected edge
• unordered pair of vertices (u,v)
• e.g., a flight route
• Directed graph
• all the edges are directed
• e.g., route network
• Undirected graph
• all the edges are undirected
• e.g., flight network
ORD PVD
flight
AA 1206
ORD PVD849miles
6
John
DavidPaul
brown.edu
cox.net
cs.brown.edu
att.net
qwest.net
math.brown.edu
cslab1bcslab1a
Applications
• Electronic circuits
• Printed circuit board
• Integrated circuit
• Transportation networks
• Highway network
• Flight network
• Computer networks
• Local area network
• Internet
• Web
• Databases
• Entity-relationship diagram
7
Terminology (1/5)
• End vertices (or endpoints) of an
edge
• U and V are the endpoints of a
• Edges incident on a vertex
• a, d, and b are incident on V
• Adjacent vertices
• U and V are adjacent
• Parallel edges
• h and i are parallel edges
• Self-loop
• j is a self-loop
XU
V
W
Z
Y
a
c
b
e
d
f
g
h
i
j
8
P1
Terminology (2/5)
• Path
• sequence of alternating vertices
and edges
• begins with a vertex
• ends with a vertex
• each edge is preceded and
followed by its endpoints
• Simple path
• path such that all its vertices and
edges are distinct
• Examples
• P1=(V,b,X,h,Z) is a simple path
• P2=(U,c,W,e,X,g,Y,f,W,d,V) is a path
that is not simple
XU
V
W
Z
Y
a
c
b
e
d
f
g
hP2
9
Terminology (3/5)
• Cycle
• circular sequence of alternating
vertices and edges
• each edge is preceded and
followed by its endpoints
• Simple cycle
• cycle such that all its vertices and
edges are distinct
• Examples
• C1=(V,b,X,g,Y,f,W,c,U,a,↵) is a simple
cycle
• C2=(U,c,W,e,X,g,Y,f,W,d,V,a,↵) is a
cycle that is not simple
C1
XU
V
W
Z
Y
a
c
b
e
d
f
g
hC2
10
Terminology (4/5)
• Degree of a vertex in an
undirected graph
• The number of edges
• for example, the degree of V is 3
• Indegree (outdegree) of a vertex
(directed graph)
• The number of incoming (outgoing)
edges
• For example, the indegree of V is 3
and its out degree is 0
XU
V
W
Z
a
c
b
e
d
h
XU
V
W
Z
a
c
b
e
d
h
Terminology (5/5)
• Tree: connected graph with no cycles
• Spanning tree: tree containing all vertices
• Clique: complete subgraph
12
Properties
Notation
n number of vertices
m number of edges
deg(v) degree of vertex v
Property 1
Σv deg(v) = 2m
Proof: each edge is counted
twice
Property 2
In an undirected graph with
no self-loops and no
multiple edges
m ≤ n (n − 1)/2
Proof: each vertex has
degree at most (n − 1)
What is the bound for a
directed graph?
Example
n = 4
m = 6
deg(v) = 3
Graph Representations
• Adjacency lists
• Adjacency matrix
• Both representations map vertices into integers in [0,
n-1], where n is the number of vertices.
Adjacency matrix (1/8)
• Edges represented by a n × n matrix
Adjacency matrix (2/8)
• Advantages
easily implemented as 2-dimensional array
can represent graphs, digraphs and weighted graphs
undirected graphs: symmetric boolean matrix
digraphs (directed graphs): non-symmetric boolean matrix
weighted graphs: non-symmetric matrix of weight values
• Disadvantages:
if few edges (sparse) ⇒ memory-inefficient
Adjacency matrix (3/8)
Graph initialization
newGraph(n):
Input: number of nodes n
Output: new empty graph
g.nV = n;
g.nE = 0;
allocate memory to g.edges[][]
for all i,j=0…n-1 do
g.edges[i][j]=0;
return g;
Adjacency matrix (4/8)
Edge insertion
insertEdge(g,(v,w))
Input: graph g, edge (v,w)
if ( g.edges[v][w]= 0 )
{ g.edges[v][w]=1;
g.edges[w][v]=1;
g.nE=g.nE+1;
}
Adjacency matrix (5/8)
Edge removal
removeEdge(g,(v,w))
Input graph g, edge (v,w)
if ( g.edges[v][w]≠0)
{
g.edges[v][w]=0;
g.edges[w][v]=0;
g.nE=g.nE-1;
}
Adjacency matrix (6/8)
show(g)
Input: graph g
for all i=0 to g.nV-1 do
for all j=i+1 to g.nV-1 do
if ( g.edges[i][j]≠0 )
print i”—”j;
Write an algorithm to output all edges of an undirected graph (no
duplicates!)
Adjacency matrix (7/8)
• Space complexity: O(n2)
if a graph is sparse, most storage is wasted.
• Time complexity:
initialisation: O(n2) (initialise n×n matrix)
insert an edge: O(1) (set two cells in matrix)
delete an edge: O(1) (unset two cells in matrix)
Adjacency matrix (8/8)
A space optimisation for undirected graphs: store only top-right
part of matrix.
New space complexity:
• n-1 int ptrs + n(n-1)/2 ints (but still O(n2))
Requires us to always use edges (v, w) such that v < w.
Adjacency List (1/6)
• For each vertex, store a linked
list of adjacent vertices:
Adjacency List (2/6)
• Advantages
relatively easy to implement in languages like C
memory efficient if E:V relatively small
• Disadvantages:
• one graph has many possible representations unless lists are ordered
by same criterion e.g. ascending
Adjacency List (3/6)
Graph initialization
newGraph(n)
Input: number of nodes n
Output: new empty graph
g.nV = n;
g.nE = 0;
allocate memory for g.edges[];
for all i=0..n-1 do
g.edges[i]=NULL;
return g
Adjacency List (4/6)
Edge insertion
insertEdge(g,(v,w))
Input: graph g, edge (v,w)
if ( inLL(g.edges[v],w) ) // inLL(g.edges[v],w) checks if w is in g.edges[v]
{ insertLL(g.edges[v],w); // insertLL(g.edges[v],w) inserts w into g.edges[v]
insertLL(g.edges[w],v);
g.nE=g.nE+1;
}
Adjacency List (5/6)
Edge removal
removeEdge(g,(v,w))
Input: graph g, edge (v,w)
if ( inLL(g.edges[v],w) )
{
deleteLL(g.edges[v],w); // deleteLL(g.edges[v],w) deletes w from g.edges[v]
deleteLL(g.edges[w],v);
g.nE=g.nE-1;
}
inLL, insertLL, deleteLL are standard linked list operations
Adjacency List (6/6)
Analyse space complexity and time complexity of adjacency list
representation:
• Space complexity: O(n+m), where m is the number of edges
• Time complexity:
initialisation: O(n) (initialise n lists)
insert an edge: O(1) for unsorted lists (insert one vertex into one list (digraph) or
two lists (undirected graph)) if don't check for duplicates
delete edge: O(degree(v)+degree(w))=O(m) (need to delete incident vertex
from two lists)
If vertex lists are sorted
insertion requires search of list ⇒ O(m)
deletion always requires a search, regardless of list order
Comparison of Graph Representations
adjacency matrix
adjacency
list
space usage n2 n+m
initialise n2 n
insert edge 1 1
remove edge 1 m
adjacency matrix
adjacency
list
disconnected(v)? n 1
isPath(x,y)? n2 n+m
copy graph n2 n+m
destroy graph n n+m
Graph Abstract Data Type (1/2)
Data:
• set of edges, set of vertices
Operations:
• insertion: create graph, add edge
• deletion: remove edge, delete whole graph
• search: check if graph contains a given edge
Things to note:
• the set of vertices is fixed when a graph is initialised
• we treat vertices as ints, but could be arbitrary Items
Graph Abstract Data Type (2/2)
Graph ADT interface graph.h
typedef struct GraphRep *Graph;
typedef int Vertex;
typedef struct Edge { Vertex v; Vertex w; } Edge;
Graph newGraph(int V);
void insertEdge(Graph, Edge);
void removeEdge(Graph, Edge);
bool adjacent(Graph, Vertex, Vertex);
void freeGraph(Graph);
Graph Implementation with Adjacency Matrix
(1/4)
Implementation of GraphRep (adjacency-matrix representation)
typedef struct GraphRep {
int **edges;
int nV;
int nE;
} GraphRep;
Graph Implementation with Adjacency Matrix
(2/4)
Implementation of graph initialisation (adjacency-matrix representation)
Graph newGraph(int n) {
assert(n >= 0);
int i;
Graph g = malloc(sizeof(GraphRep)); // allocate heap memory to g
assert(g != NULL); g->nV = n; g->nE = 0;
g->edges = malloc(n * sizeof(int *)); // allocate heap memory to g->edges
assert(g->edges != NULL);
for (i = 0; i < n; i++) { // allocate heap memory to g->edges[i]
g->edges[i] = calloc(n, sizeof(int)); assert(g->edges[i] != NULL);
}
return g;
}
Graph Implementation with Adjacency Matrix
(3/4)
Implementation of edge insertion/removal (adjacency-matrix representation)
bool validV(Graph g, Vertex v)
{ return (g != NULL && v >= 0 && v < g->nV);}
void insertEdge(Graph g, Edge e) {
assert(g != NULL && validV(g,e.v) && validV(g,e.w));
if (!g->edges[e.v][e.w]) {
g->edges[e.v][e.w] = 1; g->edges[e.w][e.v] = 1; g->nE++; }}
void removeEdge(Graph g, Edge e) {
assert(g != NULL && validV(g,e.v) && validV(g,e.w));
if (g->edges[e.v][e.w]) {
g->edges[e.v][e.w] = 0; g->edges[e.w][e.v] = 0; g->nE–; }}
Graph Implementation with Adjacency Matrix
(4/4)
Implement a function to check whether two vertices are directly
connected by an edge
bool adjacent(Graph g, Vertex x, Vertex y) {
assert(g != NULL && validV(g,x) && validV(g,y));
return (g->edges[x][y] != 0);
}
Graph Implementation with Adjacency Lists
(1/7)
Implementation of GraphRep (adjacency-list representation)
typedef struct GraphRep {
Node **edges;
int nV;
int nE;
} GraphRep;
typedef struct Node {
Vertex v;
struct Node *next;
} Node;
Graph Implementation with Adjacency Lists
(2/7)
Implementation of graph initialisation (adjacency-list representation)
Graph newGraph(int n) {
int i;
assert(n >= 0);
Graph g = malloc(sizeof(GraphRep));
assert(g != NULL);
g->nV = n; g->nE = 0;
g->edges = malloc(nV * sizeof(Node *));
assert(g->edges != NULL);
for (i = 0; i < n; i++)
g->edges[i] = NULL;
return g;
}
Graph Implementation with Adjacency Lists
(3/7)
Implementation of edge insertion/removal (adjacency-list
representation)
void insertEdge(Graph g, Edge e) {
assert(g != NULL && validV(g,e.v) && validV(g,e.w));
if (!inLL(g->edges[e.v], e.w)) {
g->edges[e.v] = insertLL(g->edges[e.v], e.w);
g->edges[e.w] = insertLL(g->edges[e.w], e.v);
g->nE++;
}
}
Graph Implementation with Adjacency Lists
(4/7)
void removeEdge(Graph g, Edge e) {
assert(g != NULL && validV(g,e.v) && validV(g,e.w));
if (inLL(g->edges[e.v], e.w)) {
g->edges[e.v] = deleteLL(g->edges[e.v], e.w);
g->edges[e.w] = deleteLL(g->edges[e.w], e.v);
g->nE–;
}
}
inLL, insertLL, deleteLL are standard linked list operations
Graph Implementation with Adjacency Lists
(5/7)
Assuming an adjacency list representation, implement a function to check
whether two vertices are directly connected by an edge
bool adjacent(Graph g, Vertex x, Vertex y) {
assert(g != NULL && validV(g,x));
return inLL(g->edges[x], y);
}
Graph Implementation with Adjacency Lists
(6/7)
Write a program that uses the graph ADT to
• build the graph depicted below
• print all the nodes that are incident to vertex 1 in ascending order
Graph Implementation with Adjacency Lists
(7/7)
#include
#include “Graph.h”
#define NODES 4
#define NODE_OF_INTEREST 1
int main(void) {
Graph g = newGraph(NODES); Edge e; int i;
e.v = 0; e.w = 1; insertEdge(g,e);
e.v = 0; e.w = 3; insertEdge(g,e);
e.v = 1; e.w = 3; insertEdge(g,e);
e.v = 3; e.w = 2; insertEdge(g,e);
for (i = 0; i < NODES; i++) {
if (adjacent(g, i, NODE_OF_INTEREST))
printf("%d\n", i);}
freeGraph(g);
return 0; }
Summary
• Graph terminology
vertices, edges, vertex degree, connected graph,
tree
path, cycle, clique, spanning tree, spanning
forest
• Graph representations
adjacency matrix
adjacency lists
• Suggested reading:
Sedgewick, Ch.17.1-17.5
COMP9024: Data Structures and Algorithms
Contents
Graphs
Graphs
Edge Types
Applications
Terminology (1/5)
Terminology (2/5)
Terminology (3/5)
Terminology (4/5)
Terminology (5/5)
Properties
Graph Representations
Adjacency matrix (1/8)
Adjacency matrix (2/8)
Adjacency matrix (3/8)
Adjacency matrix (4/8)
Adjacency matrix (5/8)
Adjacency matrix (6/8)
Adjacency matrix (7/8)
Adjacency matrix (8/8)
Adjacency List (1/6)
Adjacency List (2/6)
Adjacency List (3/6)
Adjacency List (4/6)
Adjacency List (5/6)
Adjacency List (6/6)
Comparison of Graph Representations
Graph Abstract Data Type (1/2)
Graph Abstract Data Type (2/2)
Graph Implementation with Adjacency Matrix (1/4)
Graph Implementation with Adjacency Matrix (2/4)
Graph Implementation with Adjacency Matrix (3/4)
Graph Implementation with Adjacency Matrix (4/4)
Graph Implementation with Adjacency Lists (1/7)
Graph Implementation with Adjacency Lists (2/7)
Graph Implementation with Adjacency Lists (3/7)
Graph Implementation with Adjacency Lists (4/7)
Graph Implementation with Adjacency Lists (5/7)
Graph Implementation with Adjacency Lists (6/7)
Graph Implementation with Adjacency Lists (7/7)
Summary
adjacency
matrix
adjacency
list
space usage
n2
n+m
initialise
n2
n
insert edge
1
1
remove edge
1
m