COS 212
9.1: Graphs
Lecture Outline
Graph Data Structure
• Terminology
Graph Representations
• List
• Matrix
Graph Traversals
• Depth-First
• Breadth-First
Limitations of Trees and other ADTs
Linear ADTs such as arrays and linked lists are not efficiently
searchable, and encode only one relationship between the
elements: order of elements
Trees add the capacity for hierarchical relationship between
data elements, and introduce efficient O(lg n) search
What if the data that we want to store is neither linear nor
hierarchical?
Suppose you are hired by Google, and you are asked to re-
invent Google maps
How are you going to store the different destinations?
How are you going to store the distance between different points on
the map?
If a list/tree is used, which point will be the head/root?
When data gets complex, simple structures may fail you
Simple (undirected) graph
edge deg = vertex
3 Vertex i is
adjacent to
vertex j if
there is an
edge(i,j)
Edge(i,j) is
incident with
vertices i and j
degree of
vertex i,
A set of vertices interconnected by edges deg(i), is the
number of
Every vertex represents a data element edges
Every edge between vertices i and j represents incident with i
the relationship between vertices i and j
If the graph is undirected, edge(i, j) == edge(j, i)
Directed graph (Digraph)
directed edge
Every edge between i and j represents the relationship
between i and j
In a digraph, every pair of adjacent (connected) vertices is
ordered
edge(i, j) != edge(j, i)
Multigraph
Can be directed or undirected
Multiple edges between i and j are allowed
Pseudograph
An edge may connect vertex i to itself
Such a connection is referred to as a loop
Weighted graph
23 5
3
3
15
4 8 7 15
5 2 9
51
43
5 1
A graph where every edge bears a value (weight, or cost)
Based on the application, the value can represent length,
cost, distance, etc.
Paths in a graph If a graph does not contain
cycles, it is called an
acyclic graph
A What kind of graph is a
binary tree?
N D B Binary tree:
O C
directed, acyclic,
unweighted graph
M Z E F G
Y H I
A path from i to j is a set of edges connecting vertices i and j
A path from A to H: (A,C), (C,G), (G,H)
Simple path: a path on which each vertex is unique
Circuit: a path that does a full circle and arrives back at the
start (From O to O: [O,N],[N,M],[M,O])
Cycle: a circuit where every vertex is unique
Complete graph
6 vertices,
15 edges
A
D B C
E F
Each vertex is connected to every other vertex with exactly
one edge
Number of edges = number of 2 vertex combinations
# edges = ½ * #vertices *(#vertices - 1)
½ * 6(6 - 1) = ½ * 30 = 15
Which representation is
Representing graphs better?
a b c a b c d e f
a 0 0 0 0 1 0
adjacency matrix
d e f
b 0 0 0 1 0 1
c 0 0 0 0 0 0
a e d 0 1 0 0 1 1
e 1 0 0 1 0 0
b d f f 0 1 0 1 0 0
c ae bd bf de df
a 1 0 0 0 0
incidence matrix
d b e f b 0 1 1 0 0
c 0 0 0 0 0
e a d
d 0 1 0 1 1
e 1 0 0 1 0
f b d
f 0 0 1 0 1
adjacency list
Graph VS Tree
A tree is a simple acyclic graph
Tree traversal: visit every node exactly once
Graph traversal: visit every vertex exactly once
Can we use tree traversal algorithms to traverse a graph?
NO, because graphs may have cycles, and unmodified tree
traversal algorithms will result in infinite recursion
We have to keep track of the vertices that have already
been visited
Depth-first search graph traversal algorithm
Formalised by J Hopcroft and R Tarjan (1974)
Visit each vertex v
For each vertex v, visit its unvisited adjacent vertices
If a vertex v has no unvisited adjacent vertices, backtrack to v’s
predecessor
Every visited vertex must be labelled as visited for the method to
work
Depth-first Traversal: Simple Graph
depthFirst()
For every vertex,
for all vertices v
store the order of
num(v) = 0;
Store the visiting; 0 =
edges = null;
path unvisited.
i = 1;//visit order count
while there is a vertex v such that num(v) is 0 Why do we need
DFS(v); // initiate recursion the while loop?
output edges;
DFS(v) // recursive function
num(v) = i++; // visit
for all vertices u adjacent to v a (1) b(2) c (7)
if num(u) is 0 //unvisited
attach edge(uv) to edges;
d(4) e(3) f (8)
DFS(u); // recursion
g (5) h(6)
edges: ab, be, ed, dg, gh, ac, cf
Depth-first Traversal: Digraph (directed graph)
depthFirst()
for all vertices v
num(v) = 0;
The while loop
edges = null;
ensures that the entire
i = 1;
graph is traversed,
while there is a vertex v such that num(v) is 0
even if the graph is
DFS(v);
not fully connected
output edges;
DFS(v)
num(v) = i++; // visit a (1) b (2) c(6)
for all vertices u adjacent to v
if num(u) is 0
attach edge(uv) to edges; d(5) e (3) f (7)
DFS(u);
g h (8)
(4)
Breadth-first Traversal
a (1) b (2) c (3)
Depth-first: use a stack
Breadth-first: use a queue
d(7) e(5) f (4)
breadthFirst()
for all vertices u
num(u) = 0; // visited # g(6) h (8)
edges = null; // path
i = 1;
while there is a vertex v such that num(v) is 0
num(v) = i++;
iteration v queue
enqueue(v); // add to queue
while queue is not empty init a
v = dequeue(); // visit 1 a b c f
for all vertices u adjacent to v 2 b c f e g
if num(u) is 0 // unvisited 3 c f e g
num(u) = i++;
enqueue(u); 4 f e g
attach edge(vu) to edges; 5 e g d
output edges; 6 g d
7 d h
8 h
Summary A
Graphs:
ADT consisting of vertices connected
D B C
by edges
Directed VS undirected
Weighted VS unweighted
Cyclic VS acyclic E F
Implementation:
Adjacency list VS Adjacency matrix
a b c d e f
Graph traversals: a 0 0 0 0 1 0
Depth-first: recursive b 0 0 0 1 0 1
Breadth-first: iterative, uses a queue c 0 0 0 0 0 0
d 0 1 0 0 1 1
Next lecture: Topological Sort e 1 0 0 1 0 0
f 0 1 0 1 0 0
