9/3/2013

Graph Algorithms

Graphs
A graph G = (V, E) consists of a set of vertices V, and a set
of edges E, such that each edge in E is a connection
between a pair of vertices in V.

The number of vertices is written |V| called Order, and the

number edges is written |E| called Size.

● A graph G = (V, E)
■ V = set of vertices
■ E = set of edges = subset of V  V (unordered pair of vertices)
■ Thus |E| = O(|V|2)

1
9/3/2013

Graphs

A graph G is a set V(G) of vertices (nodes) and a set E(G) of

edges which are pairs of vertices.

a b c d

e f g h

i j k l

V = { a, b, c, d, e, f, g, h, i, j, k, l }
E = { (a, b), (a, e), (b, e), (b, f), (c, j), (c, g), (c, h), (d, h), (e, j),
(g, k), (g, l), (g, h), (i, j) } 3

A Directed Graph
In a directed graph (digraph), edges are ordered pairs.
TW 45
NW 35
BOS
ORD
SFO DL 247
JFK AA 903
DL 335

AA 1387
UA 877

MIA
AA 49 AA 523
LAX DFW

AA 411
4

2
9/3/2013

Directed Graph (Con’t)

■In a directed graph:
○Edge (u,v) goes from vertex u to vertex v, notated uv
○Consist of finite set V of vertices and a set A of ordered pair
of distinct vertices called arcs.

- In a Mixed graph there will be at least one edge and at least

one arc.

Undirected Graph
■ In an undirected graph:
○ Edge (u,v) = edge (v,u)
○ No self-loops
●An undirected graph is connected if there is at least one path
from any vertex to any other.

3
9/3/2013

Connected Graph

G is connected if there is a path between every pair of vertices.

a d

b c
f
e
If G is not connected, the maximal connected subgraphs are the
connected components of G.
C3
C2
a
C1 d e f g

b c
7

Connected Graph
■ A connected graph has a path from every vertex to
every other
Complete Graph
■ A graph G is said to be complete if every node u
in G is adjacent to every other node v in G.
■ A complete graph with n nodes have n(n-1)/2
edges
a
d f g

b c
8

4
9/3/2013

Property of Connectivity

Let G = (V, E) be an undirected graph.

If G is connected, then | E | ≥ | V | – 1.

If G is a tree, then | E | = | V | – 1.

If G is a forest, then | E | ≤ | V | – 1.
An acyclical
undirected graph is
forest
9

More General Graphs

A multipgraph allows multiple edges between two vertices.

a c

b d f

A pseudograph is a multigraph that allows self-loops (edges

from a vertex to itself).

1 2 3

4 5 6
10

5
9/3/2013

Simple Graph

A graph is simple when

• it is non-directed
• there is at most one edge between two vertices
• there is no loop of length one..

11

Edges & Degrees

deg(w) = 1
e2 w
u u and v are adjacent
degree(u) = 2 endpoint
e1
v
incident on in-degree(b) = 3
u and v out-degree(b) = 4

source c
b

a e
destination
d
12

6
9/3/2013

Handshaking Theorem

Let G = (V, E) be an undirected simple graph.

∑ deg(v) = 2 | E | | E | ≤ | V | · (| V | – 1) / 2
vV
4
K4 has ( 2) = 6 edges

If G is directed:

∑ indeg(v) = ∑ outdeg(v) = | E |
vV vV

| E | ≤ | V | · (| V | – 1)
13

Path
A path of length k is a sequence v 0 , v 1 , …, v k of vertices such
that (vi , vi+1 ) for i = 0, 1, …, k – 1 is an edge of G.
b, c, d not a path
a b c d
Simple path:
a, e, k, p, l, q
m, h, d, c, g
e f g h
(no repeated Non-simple path:
vertices) a, b, e, f, g, b, g, l
j k l m

n o p q
14

7
9/3/2013

Cycle
A cycle is a path that starts and ends at the same vertex.

A simple cycle has no repeated vertices.

a b c d

e f g h

k, j, n, k, p, o,k j k l m
is not simple.

n o p q
15

Hamiltonian Cycle (HC)

A Hamiltonian cycle (or Hamiltonian circuit) is a simple cycle
In an undirected graph which visits each vertex exactly
once and also returns to the starting vertex.
.

8
9/3/2013

Hamiltonian Cycle

● Hamiltonian cycle: simple cycle containing all

vertices w
a c
b
z
d
x
y
e f
no hamiltonian cycle

hamiltonian cycle:
a,b,c,d,f,e,(then back to a)

17

Eulerian Tour

An Euler tour, Eulerian cycle, or Eulerian circuit of a

connected directed/undirected graph is a cycle that
traverses each edge of G exactly once, although it may
visits a vertex more than once.
c
a d
b

f
e

Euler tour: c,d,f,e,a,b,e,c

18

9
9/3/2013

Euler Tour (2)

● Some graphs do not have euler tours

■ specifically those with vertices whose degree (# of
neighbors) is odd

a c
b

d e

f g

f,c,d and e have odd degree

19

Subgraph
A subgraph H of G
is a graph;
its edges and vertices are subsets of those of G.

a b c d

e f g h

j k l m

n o p q
V(H) = {b, d, e, f, g, h, l, p, q} E(H) = {(b,
20 e), (b, g), (e, f), (d, h), (l, p), (l, q)}

10
9/3/2013

Tree Graph/Tree

● A connected graph T without any cycles is

called a tree graph or free tree or a tree
● There is a unique simple path p between any
two nodes U and V in T

21

Free Tree and Forest

11
9/3/2013

Graphs

● We will typically express running times in

terms of |E| and |V| (often dropping the |’s)
■ If |E|  |V|2 the graph is dense
■ If |E|  |V| the graph is sparse
● If you know you are dealing with dense or
sparse graphs, different data structures(List,
Matrix) may make sense

23

Representing Graphs

Two techniques are available:

1. Adjacency matrix
2. Adjacency List
● Assume V = {1, 2, …, n}
● An adjacency matrix represents the graph as
a n x n matrix A:
■ A[i, j] = 1 if edge (i, j)  E (or weight of edge)
= 0 if edge (i, j)  E

24

12
9/3/2013

Graphs: Adjacency Matrix

● Example:
A 1 2 3 4
1
a 1

2 d
4 2
3
b c
??
3 4

25

Graphs: Adjacency Matrix

● Example:
A 1 2 3 4
1
a 1 0 1 1 0

2 d
4 2 0 0 1 0
b c 3 0 0 0 0
3 4 0 0 1 0

26

13
9/3/2013

Graphs: Adjacency Matrix

2 A = (a ij )
1 if (i, j)  E(G)
1 3 a ij =
0 otherwise
5 4 1 2 3 4 5
1 0 1 1 0 1
2 1 0 1 0 0
3 1 1 0 1 1
4 0 0 1 0 1
5 1 0 1 1 0

Space: (|V| 2 ).
Preferred when the graph is small or dense.
27

Graphs: Adjacency Matrix

● How much storage does the adjacency matrix

require?
● A: O(V2)

28

14
9/3/2013

Graphs: Adjacency Matrix

● The adjacency matrix is a dense representation

■ Usually too much storage for large graphs
■ But can be very efficient for small graphs
● Most large interesting graphs are sparse
■ E.g., planar graphs, in which no edges cross, have
|E| = O(|V|) by Euler’s formula
■ For this reason the adjacency list is often a more
appropriate representation

29

Graphs: Adjacency List

● Adjacency list: for each vertex v  V, store a

list of vertices adjacent to v
● Example:
1
■ Adj[1] = {2,3}
■ Adj[2] = {3}
2 4
■ Adj[3] = {}
■ Adj[4] = {3}
3
● Variation: can also keep
a list of edges coming into vertex
30

15
9/3/2013

Graphs: Adjacency List

Adj
2 1 2 3 5
2 1 3
1 3
3 1 2 4 5
4 3 5
5 4
5 1 3 4

If G is directed, the total length of all the adjacency lists is | E |.

If G is undirected, the total length is 2 | E |.
Space requirement: (|V| + |E|). Preferable representation.
31

Adjacency List and Matrix of undirected Graph

32

16
9/3/2013

Adjacency List and Matrix of Directed Graph

33

Graphs: Adjacency List

● How much storage is required?

■ The degree of a vertex v = # incident edges
○ Directed graphs have in-degree, out-degree
■ For directed graphs, # of items in adjacency lists is
 out-degree(v) = |E|
takes (V + E) storage (Why?)
■ For undirected graphs, # items in adj lists is
 degree(v) = 2 |E| (handshaking lemma)
also (V + E) storage
● So: Adjacency lists take O(V+E) storage
34

17
9/3/2013

Operation Time

Operation Adjacency List Adjacency Matrix

Scan incident edges (deg(v)) (|V|)

Scan outgoing edges (outdeg(v)) (|V|)

Scan incoming edges (indeg(v)) (|V|)

Test adjacency (min(deg(u), deg(v)) O(1)

of u and v

Space (|V|+|E|) (|V| 2)

35

Graph Searching/ Traversals

● Given: a graph G = (V, E), directed or undirected

● Goal: explore every vertex and every edge
● Some applications require visiting every vertex in the
graph exactly once
● Ultimately: build a tree on the graph
■ Pick a vertex as the root
■ Choose certain edges to produce a tree
■ Note: might also build a forest if graph is not
connected
36

18
9/3/2013

Graph Searching/ Traversals

Two methods
1- Breath-first Search
- Use a queue as an auxiliary structure to hold
nodes for future processing
2- Depth-first Search
- Use stack to handle traversing

37

Breadth-First Search
“Explore” a graph, turning it into a tree
■One vertex at a time
■Pick a source vertex to be the root
■Find (“discover”) its children, then their children, etc.
Shortest Path
■It computes the distance (smallest number of edges) from s
(source vertex) to each reachable vertices.
■For every vertex v reachable from s the path in the breath-first
tree from s to v corresponds to a “shortest path” from s to v in
G, that is the path containing the smallest number of edges.
Discovery (discovers all vertices at distance k from s before
discovering any vertices at distance k +1)

38

19
9/3/2013

Breadth-First Search

● To keep track of progress, breath-first search

colors each vertex white, gray, or black.
■ White vertices have not been discovered
○ All vertices start out white
■ Grey vertices are discovered but not fully explored
○ They may be adjacent to white vertices
■ Black vertices are discovered and fully explored
○ They are adjacent only to black and gray vertices

● Explore vertices by scanning adjacency list of

grey vertices
39

Breadth-First Search: Example

r s t u

   

   
v w x y

40

20
9/3/2013

Breadth-First Search: Example

r s t u

 0  

   
v w x y

Q: s
41

Breadth-First Search: Example

r s t u

1 0  

 1  
v w x y

Q: w r

42

21
9/3/2013

Breadth-First Search: Example

r s t u

1 0 2 

 1 2 
v w x y

Q: r t x

43

Breadth-First Search: Example

r s t u

1 0 2 

2 1 2 
v w x y

Q: t x v

44

22
9/3/2013

Breadth-First Search: Example

r s t u

1 0 2 3

2 1 2 
v w x y

Q: x v u

45

Breadth-First Search: Example

r s t u

1 0 2 3

2 1 2 3
v w x y

Q: v u y

46

23
9/3/2013

Breadth-First Search: Example

r s t u

1 0 2 3

2 1 2 3
v w x y

Q: u y

47

Breadth-First Search: Example

r s t u

1 0 2 3

2 1 2 3
v w x y

Q: y
48

24
9/3/2013

Breadth-First Search: Example

r s t u

1 0 2 3

2 1 2 3
v w x y

Q: Ø
49

Breadth-First Search (from Book)

// set distance (d) of every node to 0

//Set parent of every vertex to nil

// Set distance of source s to 0

//set predecessor/parent of the source to be nil

//consider each vertex

//v in Adj of u

50

25
9/3/2013

Breadth-First Search
(slightly different form book)

BFS(G, s) {
initialize vertices;
Q = {s}; // Q is a queue (duh); initialize to s
while (Q not empty) {
u = RemoveTop(Q);
for each v  u->adj {
if (v->color == WHITE)
v->color = GREY;
v->d = u->d + 1; What does v->d represent?
v->p = u; What does v->p represent?
Enqueue(Q, v);
}
u->color = BLACK;
}
}
51

From Book Page 533

52

26
9/3/2013

Analysis BFS
● The operation of enqueuing and dequeuing take O(1)
time. (i.e each vertex is enqueued at most once and thus
dequeued at most once) so the total time devoted to queue
operation is O(V).
● Adjacency list of each vertex is scanned only when the
vertex is dequeued, each adjacency list is scanned at
most once.
● Sum of length of the lengths of all the adjacency list is
O(E), the total time spent in scanning adjacency lists is
O(E).
● The overhead for initialization is O(V)
● So the total running time of BFS is O(V+E)
53

BFS: The Code Again

BFS(G, s) {
initialize vertices; Touch every vertex: O(V)
Q = {s};
while (Q not empty) {
u = RemoveTop(Q); u = every vertex, but only once
for each v  u->adj { (Why?)
if (v->color == WHITE)
So v = every vertex v->color = GREY;
that appears in v->d = u->d + 1;
some other vert’s v->p = u;
adjacency list Enqueue(Q, v);
}
u->color = BLACK; What will be the running time?
} Total running time: O(V+E)
}
54

27
9/3/2013

Breadth-First Search: Properties

● BFS calculates the shortest-path distance to

the source node
■ Shortest-path distance (s,v) = minimum number
of edges from s to v, or  if v not reachable from s
■ Proof given in the book (p. 472-5)
● BFS builds breadth-first tree, in which paths to
root represent shortest paths in G
■ Thus can use BFS to calculate shortest path from
one vertex to another in O(V+E) time

55

Print Shortest Path

The following procedure prints out the vertices on a shortest path from s to v
assuming that BFS has already been run to compute the shortest-path tree

This procedure runs in time linear in the number of vertices in the

path printed, since each recursive call is for a path one vertex
shorter.
56

28
9/3/2013

Depth-First Search

● Depth-first search is another strategy for

exploring a graph
■ Explore “deeper” in the graph whenever possible
■ Edges are explored out of the most recently
discovered vertex v that still has unexplored edges
■ When all of v’s edges have been explored, backtrack
to the vertex from which v was discovered
■ The process continues until we have discovered all the
vertices that are reachable from the original source
vertex.
57

Depth-First Search
● If any undiscovered vertices remain, then one
of them is selected as a new source and the
search is repeated from the source.
● The entire process is repeated until all the
vertices are discovered.
● Vertices initially colored white
● Then colored gray when discovered
● Then black when finished

58

29
9/3/2013

DFS Example
source
vertex

59

DFS Example
source
vertex
d f
1 | | |

| |

| | |

60

30
9/3/2013

DFS Example
source
vertex
d f
1 | | |

2 | |

| | |

61

DFS Example
source
vertex
d f
1 | | |

2 | |

3 | | |

62

31
9/3/2013

DFS Example
source
vertex
d f
1 | | |

2 | |

3 | 4 | |

63

DFS Example
source
vertex
d f
1 | | |

2 | |

3 | 4 5 | |

64

32
9/3/2013

DFS Example
source
vertex
d f
1 | | |

2 | |

3 | 4 5 | 6 |

65

DFS Example
source
vertex
d f
1 | 8 | |

2 | 7 |

3 | 4 5 | 6 |

66

33
9/3/2013

DFS Example
source
vertex
d f
1 | 8 | |

2 | 7 |

3 | 4 5 | 6 |

67

DFS Example
source
vertex
d f
1 | 8 | |

2 | 7 9 |

3 | 4 5 | 6 |

What is the structure of the grey vertices?

What do they represent?
68

34
9/3/2013

DFS Example
source
vertex
d f
1 | 8 | |

2 | 7 9 |10

3 | 4 5 | 6 |

69

DFS Example
source
vertex
d f
1 | 8 |11 |

2 | 7 9 |10

3 | 4 5 | 6 |

70

35
9/3/2013

DFS Example
source
vertex
d f
1 |12 8 |11 |

2 | 7 9 |10

3 | 4 5 | 6 |

71

DFS Example
source
vertex
d f
1 |12 8 |11 13|

2 | 7 9 |10

3 | 4 5 | 6 |

72

36
9/3/2013

DFS Example
source
vertex
d f
1 |12 8 |11 13|

2 | 7 9 |10

3 | 4 5 | 6 14|

73

DFS Example
source
vertex
d f
1 |12 8 |11 13|

2 | 7 9 |10

3 | 4 5 | 6 14|15

74

37
9/3/2013

DFS Example
source
vertex
d f
1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15

Vertices are timestamped by discovery time/finishing time

75

76

38
9/3/2013

Depth-First Search: The Code

DFS(G) DFS_Visit(u)

for each vertex u  V[G] color[u] = GREY;

time = time+1;
color[u] = WHITE; d[u] = time;
Π[u]= NIl for each v  Adj[u]

time = 0; if (color[v] == WHITE)

for each vertex u  V[G] Π[v]= u
DFS_Visit(v);
if (color[u] == WHITE)
DFS_Visit(u); color[u] = BLACK;
time = time+1;
f[u] = time;

77

Depth-First Search: The Code

78

39
9/3/2013

Depth-First Search (Analysis)

● The loops on line 1-3 and lines 5-7 of DFS take time
O(V), exclusive DFS call.

● The procedure DFS-Visit is called exactly once for

each vertex v  V.

79

Depth-First Search: The Code

80

40
9/3/2013

Depth-First Search (Analysis)

■ Since DFS-Visit is invoked only on white vertices and
the first thing it does is paint the vertex gray.
■ During an execution of DFS-Visit(v), the loop on lines
4-7 is executed |Adj[v]| times.
■ The total cost of executing lines 4-7 of DFS-Visit is
O(E). The running time of DFS is O(V+E).
○Each loop in DFS_Visit can be attributed to an edge in the
graph
○Runs once/edge if directed graph, twice if undirected
○Thus loop will run in O(E) time, algorithm O(V+E)

81

DFS: Kinds of edges

● DFS introduces an important distinction

among edges in the original graph:
■ Tree edge: encounter new (white) vertex
○ The tree edges form a spanning forest
○ Can tree edges form cycles? Why or why not?

82

41
9/3/2013

DFS Example
source
vertex
d f
1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15

Tree edges

83

DFS: Kinds of edges

● DFS introduces an important distinction

among edges in the original graph:
■ Tree edge: encounter new (white) vertex
■ Back edge: from descendent to ancestor
○ Encounter a grey vertex (grey to grey)

84

42
9/3/2013

DFS Example
source
vertex
d f
1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15

Tree edges Back edges

85

DFS: Kinds of edges

● DFS introduces an important distinction

among edges in the original graph:
■ Tree edge: encounter new (white) vertex
■ Back edge: from descendent to ancestor
■ Forward edge: from ancestor to descendent
○ Not a tree edge, though
○ From grey node to black node

86

43
9/3/2013

DFS Example
source
vertex
d f
1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15

Tree edges Back edges Forward edges

87

DFS: Kinds of edges

● DFS introduces an important distinction

among edges in the original graph:
■ Tree edge: encounter new (white) vertex
■ Back edge: from descendent to ancestor
■ Forward edge: from ancestor to descendent
■ Cross edge: between a tree or subtrees
○ From a grey node to a black node

88

44
9/3/2013

DFS Example
source
vertex
d f
1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15

Tree edges Back edges Forward edges Cross edges

89

DFS: Kinds of edges

● DFS introduces an important distinction

among edges in the original graph:
■ Tree edge: encounter new (white) vertex
■ Back edge: from descendent to ancestor
■ Forward edge: from ancestor to descendent
■ Cross edge: between a tree or subtrees
● Note: tree & back edges are important; most
algorithms don’t distinguish forward & cross

90

45
9/3/2013

Properties of DFS

● Structure of DFS shows forest of trees

● DFS exactly mirrors the structure of recursive calls

of DFS-Visit.

● Discovery and finishing time have parenthesis

structure (i.e. discovery of vertex u with a left parenthesis “(u” and
represent its finishing time by a right parenthesis “u)”)

91

Properties of depth First search

92

46
9/3/2013

DFS: Kinds Of Edges

● Thm 23.9: If G is undirected, a DFS produces

only tree and back edges
● Proof by contradiction: source
■ Assume there’s a forward edge F?

○ But F? edge must actually be a

back edge (why?)

93

DFS: Kinds Of Edges

● Thm 23.9: If G is undirected, a DFS produces

only tree and back edges
● Proof by contradiction: source
■ Assume there’s a cross edge
○ But C? edge cannot be cross:
○ must be explored from one of the
vertices it connects, becoming a tree
vertex, before other vertex is explored
○ So in fact the picture is wrong…both
lower tree edges cannot in fact be C?
tree edges
94

47
9/3/2013

DFS And Graph Cycles

● Thm: An undirected graph is acyclic if a DFS

yields no back edges
■ If acyclic, no back edges (because a back edge
implies a cycle
■ If no back edges, acyclic
○ No back edges implies only tree edges (Why?)
○ Only tree edges implies we have a tree or a forest
○ Which by definition is acyclic

● Thus, can run DFS to find whether a graph has

a cycle
95

DFS And Cycles

● How would you modify the code to detect cycles?
DFS(G) DFS_Visit(u)
{ {
for each vertex u  G->V u->color = GREY;
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v  u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u  G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}
96

48
9/3/2013

DFS And Cycles

● What will be the running time?
DFS(G) DFS_Visit(u)
{ {
for each vertex u  G->V u->color = GREY;
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v  u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u  G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}
97

DFS And Cycles

● What will be the running time?

● A: O(V+E)
● We can actually determine if cycles exist in
O(V) time:
■ In an undirected acyclic forest, |E|  |V| - 1
■ So count the edges: if ever see |V| distinct edges,
must have seen a back edge along the way

98

49