GRAPH THEORY

Prof S Sameen Fatima

Dept of Computer Science
and Engineering
Osmania University College of
Engineering
Hyderabad
500007
sameenf@gmail.com
Graph Theory 1
 BASICS

1. What Is a Graph?

2. Kinds of Graphs
3. Vertex Degree
4. Paths and

Cycles
Graph Theory 3
 The KÖnigsberg Bridge Problem
• Königsber is a city on the Pregel river in
Prussia
• The city occupied two islands plus areas on
both banks
• Problem:
Whether they could leave home, ever
y
cross
X
bridge exactly once, and return
W Y
home.

Graph Theory 4
 A Model

• A vertex : an island
• An edge : a path(bridg betwee tw
islands e) n o
X
e1
X
e2 e6
W Y
W Y e5
e4
e3 e7
Z
Z

Graph Theory 5
 General Model

• A vertex : an
object
• An edge : a between object
relation two s
Committee 1 Committee 2

common
member

Graph Theory 6
 What Is a Graph?

• A graph G is ordered (V, E)

pair
an
– A vertex set V = {W, X, Y, Z}
consisting
– An edge setof:
E = {e1, e2, e3, e4, e5, e6, e7}

X
e1
e2 e6
W
e5 Y
e4
e3 e7

Graph Theory
Z 7
 What Is a Graph?

• A graph, G is an ordered triple (V,

E, f)
– V is a set of
consisting of nodes, points, or vertices.
– E is a set, whose elements are as
known
– edges that maps each element of E to
or lines.
f is a function
an pai of vertices in V.
unordered r

Graph Theory 8
 Loop, Multiple edges

•
Loop : An edge whose endpoints are
equal
• Multiple edges : have sam
Edges
pai of endpoint the e
r s
Multiple
edges
loop

Graph Theory 9
 Simple Graph

Simple : A graph no loops multipl edge

graph has or e s

Multiple
edges loop

It is not simple. It is a simple graph.

Graph Theory 10
 Adjacent, neighbors
• Two vertices are and
neighbors are
adjacent if they are the endpoint of an
edge s
• Example:
– A and B are adjacent
– A and D are not adjacent
A B

C D
Graph Theory 11
 Finite Graph, Null Graph

• Finite graph : an graph whose se

vertex
and edge set are t
finite
• Null graph : the whos verte se
an edge graph
areempt e x t
d s y

Graph Theory 12
 Connected and Disconnected
• Connected : There exists leas on
path between two vertices t
at e
• Disconnecte : Otherwise
•d
– H1 and H2 are connecte
Example:
d
– H3 is disconnected
a b a b
H1 c
H2 H3 c
e
d d
e d

Graph Theory 13
 Complete Graph

• Complete Graph: A simple graph in which

every
• If no of
pair of vertice
vertices=n,
arethe ther ar n(n- edge
adjacent
s n e e 1) s

Graph Theory 14
 Sparse/Dense Graph

• A graph is sparse if | E | |V|

• A graph is dense if | E | | V |2.

Graph Theory 15
 Directed Graph (digraph)

In a digraph edges have directions

Graph Theory 16
 Weighted Graph

Weighted graph is a graph for which each edg

has an associated usuall give e
by a
weight ,
weig functio w: E R. y n
ht n
1.2 2
1 1 2 3
2
5 3
3 1
.2
.5 .3 4 5 6

1.5

4
Graph Theory 17
5
 Planar Graph

• Can be drawn on a plane such that no two edges intersect

Graph Theory 18
 Complement
Complement of G: The compleme G’ of
a simple graph G : nt
– A simple graph
– V(G’) = V(G)
– E(G’) = { uv | uv E(G) }
u
u
y
y v v
G
G’
w x w
x

Graph Theory 19
 Subgraphs

• A subgraph of a graph G is a graph H

such that:
– V(H) V(G) and E(H) E(G) and
– The assignment endpoint to edge in H is
of
th sam as in G. s s
e e

Graph Theory 21
 Subgraphs

• Example H1, H2, and H3 are subgraph

:of G s
a b

G c

e d

a b
a b
c H3 c
H1 H2
d e d
e d

Graph Theory 22
 Bipartite Graphs
• A graph G is bipartite if V(G) is the union of
two disjoint independent sets called partite
Also: The vertices can be partitioned
sets of G
into
• two sets such that each set is
• Job Assignme Proble
independent
nt m
Workers
Matching
Boys Problem

Girls Jobs

Graph Theory 23
 Chromatic Number

• The chromatic of a graph G,

number
written x(G), is the minimum number of
colors needed to label the vertices so
adjacen vertice receiv different
that
t s e colors
Blue Green
x(G) = 3

Red Blue

Graph Theory S Sameen Fatima 24

 Maps and coloring
• A map is a partition of the plane into
connected regions
•
Can we color the regions of every
map
using at most four colors so that
• Map graph coloring
Coloring
neighboring
– A region A regions
vertex have
– Adjacenc An edge
different
y
colors?
Graph Theory S Sameen Fatima 25
 Scheduling and Graph Coloring
• Two committees can not hold meetings
at the same time if two hav
common committees e
member
Committee 1 Committee 2

common
member

Graph Theory S Sameen Fatima 26

 Scheduling and Graph Coloring
• Model:
– One committee being represented by a
vertex
–
An edge between two vertices if two
corresponding committees have
– Two adjacent vertices can not th
common
same color receive e
member Committee 1 Committee 2

common
member

Graph Theory S Sameen Fatima 27

 Scheduling and Graph Coloring

• Scheduling problem is to
equivalent
grap coloring
h problem
Committee 2 Common
Common Member
Member Different Color
Committee 1
Committee 3

No Common Member
Same Color OK
Same time slot OK

Graph Theory S Sameen Fatima 28

 Degree

Degree Numbe of edge inciden on a nod

: r s t e

A B C

D E F

The degree of B is 2.

Graph Theory S Sameen Fatima 29

 Degree (Directed Graphs)
• In degree: Number of edges entering a node
• Out degree: of edges leaving a nod
• Number
Degre =Indegre +Outdegree e
e e
1 2

4 5

The in degree of 2 is 2 and

the out degree of 2 is 3.

Graph Theory S Sameen Fatima 30

 Degree: Simple Facts

• If G is a digraph with m edges, then

indeg(v) = outdeg(v) = m = |E |

• If G is a graph with m edges, then

deg(v) = 2m = 2 |E |

– Number of Odd degree Nodes is even

Graph Theory S Sameen Fatima 31

 Path
• is
A path is a sequence of
• vertices
A path issuch that there
if each vertex is
• simple
A is a distinct.
in which the terminal verte
an edge from each
coincidepath
circuit wit the initial vertex x
vertex
s tohits successor.
1 3 2

4 5 6

Simple path: [ 1, 2, 4, 5 ]
Path: [ 1, 2, 4, 5, 4]
Circuit: [ 1, 2, 4, 5, 4, 1]

Graph Theory S Sameen Fatima 32

 Cycle

• A path from a vertex to itself

• is calledisacalled
A graph cycle.cyclic if it contains a cycle;
– otherwise it is called acyclic

1 3
2

4 5 6

Cycle

Graph Theory S Sameen Fatima 33

 Other Paths
• Geodesic path: shortest path
– Geodesic paths are not necessarily unique: It is quite
possible to
have more than one path of equal length between a given
any pair of vertices in the network for which a path actually exists
pair of
• Eulerian path: a path that traverses each edge in a network exactly once
vertices
– Diameter of a graph: the length of the longest geodesic path
between

The Königsberg bridge problem

• Hamilton path: a path that visits each vertex in a network exactly once
34
 Euclerian Path
• An undirected graph possesses an Euclerian Path
if and only if it is connected and has either zero or
two vertices of odd degree
OR
• An undirected graph possesses an Euclerian Path
if and only if it is connected and its vertices are all
of even degree

There is no Euclerian Path for the Konigsberg Bridge

Problem

Graph Theory S Sameen Fatima 35

 GRAPH REPRESENTATION

• Adjacency Matrix
• Incidence Matrix
• Adjacency List

Graph Theory S Sameen Fatima 36

 Adjacency, Incidence, and Degree

• Assume ei is an edge whose endpoints are (vj,vk)

• The vertices vj and vk are said to be adjacent
• The edge ei is said to be incident upon vj
• Degree of a vertex vk is the number of edges
incident vk . It is as d(vk)
upon denoted

ei
vj vk

Graph Theory S Sameen Fatima 37

 Adjacency Matrix

• Let G = (V, E), |V| = n and |E|=m

• The adjacency matrix of G written is
|V| x |V| matrix in which entry ai,j is the
A(G),
numbe of edge in G wit endpoints the{vi, vj}.
r s h
w x y z
w w 0 1 1 0
b x 1 0 2 0
y z
a c e y 1 2 0 1
x d z 0 0 1 0

Graph Theory S Sameen Fatima 38

 Adjacency Matrix
• Let G = (V, E), |V| = n and |E|=m
• The adjacency matrix of G written A(G), is the |V| x |V|
matrix in which entry ai,j is 1 if an edge exists otherwise it
is 0

1 2 1 2 3 4 5

3 1 0 1 0 0 1
5 4 2 1 0 1 1 1
3 0 1 0 1 0
4 0 1 1 0 1
5
1 1 0 1 0

Graph Theory S Sameen Fatima 39

Adjacency Matrix (Weighted Graph)
• Let G = (V, E), |V| = n and |E|=m
• The adjacency matrix of G written A(G), is the |V| x |V|
matrix in which entry ai,j is weight of the edge if it exists
otherwise it is 0

5
1 2 1 2 3 4 5
4
1 3 6 3 1 0 5 0 0 1
5 4 2 2 5 0 4 6 3
7
3 0 4 0 2 0
4 0 6 2 0 7
5
1 3 0 7 0

Graph Theory S Sameen Fatima 40

 Incidence Matrix

• Let G = (V, E), |V| = n and |E|=m

• The incidence M(G) is the | x |E|
mi,j is 1 if vi is an endpoi
matrix V|
of ei and otherwise is 0. nt
matrix in which
entry
w a b c d e
b w
y 1 1 0 0 0
a c e
z x 1 0 1 1 0
d y 0 1 1 1 1
x
z 0 0 0 0 1

Graph Theory S Sameen Fatima 41

 Adjacency List Representation

• Adjacency-list representation
– an array of |V | elements, one for each vertex in V
– For each u V , ADJ [ u ] points to all its adjacent
vertices.

Graph Theory S Sameen Fatima 42

 Adjacency List Representation
for a Digraph

1
2 5
1 2 2 5 3 4

3 3 4
5 4 4 5

5
5

Graph Theory S Sameen Fatima 43

 Minimum Spanning Tree

Graph Theory S Sameen Fatima 55

 Minimu Spannin Tree
m g
• What is MST?

• Kruskal's Algorithm

• Prim's Algorithm

Graph Theory S Sameen Fatima 56

 Spanning Trees

A spanning tree of a graph is just a subgraph that

contains all the vertices and is a tree.

A graph may have many spanning trees.

Graph A Some Spanning Trees from Graph A

o o o
r r r

Graph Theory S Sameen Fatima 57

Complete Graph All 16 of its Spanning Trees

Graph Theory S Sameen Fatima 58

 Minimum Spanning Trees

The Minimum Spanning Tree for a given graph is the Spanning Tree of minimum cost for that
graph.

Complete Graph Minimum Spanning Tree

2 2
5 3 3

1 1

Graph Theory S Sameen Fatima 59

 Kruskal's Algorithm

This algorithm creates a forest of trees. Initially the forest consists of n single
node trees (and no edges). At each step, we add one edge (the cheapest
one) so that it joins two trees together. If it were to form a cycle, it would
simply link two nodes that were already part of a single connected tree, so
that this edge would not be needed.

Graph Theory S Sameen Fatima 60

 The steps are:

1. The forest is constructed - with each node in a separate tree.

2. The edges are placed in a priority queue.
3. Until we've added n-1 edges,
1. Extract the cheapest edge from the queue,
2. If it forms a cycle, reject it,
3. Else add it to the forest. Adding it to the forest will join two trees together.

Every step will have joined two trees in the forest together, so that at the end,
there will only be one tree in T.

Graph Theory S Sameen Fatima 61

 Complete Graph

4
B C
4
2 1

A 4 E
1 F

D 2 3
10
G 5

5 6 3

4
I
H

2 3
J

Graph Theory S Sameen Fatima 62

 A 4 B A 1 D

B 4 C B 4 D

4 10 2
B C B J C E
4
2 1
C 1 F D 5 H
A 4 E
1 F

2 D 6 J E 2 G
D 3
10
G 5
F 3 G F 5 I
5 6 3

4
I G 3 I G 4 J
H

2 3
J H 2 J I 3 J

Graph Theory S Sameen Fatima 63

 Sort Edges 1 1
A D C F

(in reality they are

placed in a priority 2 2
C E E G
makes
queuethe- algorithm
not sorted - easier
but to visualize)
sorting them
4 2 3
B C H J F G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

Graph Theory S Sameen Fatima 64

 Add Edge 1 1
A D C F

C 2 E E 2 G

4 2 3
B C H J F G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

Graph Theory S Sameen Fatima 65

 Add Edge 1 1
A D C F

C 2 E E 2 G

4 2 3
B C H J F G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

Graph Theory S Sameen Fatima 66

 Add Edge 1 1
A D C F

C 2 E E 2 G

4 2 3
B C H J F G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

Graph Theory S Sameen Fatima 67

 Add Edge 1 1
A D C F

C 2 E E 2 G

4 2 3
B C H J F G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

Graph Theory S Sameen Fatima 68

 Add Edge 1 1
A D C F

C 2 E E 2 G

4 2 3
B C H J F G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

Graph Theory S Sameen Fatima 69

 Cycle 1 1
A D C F

Don’t Add
Edge 2 2
C E E G

4 2 3
B C H J F G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

Graph Theory S Sameen Fatima 70

 Add Edge 1 1
A D C F

C 2 E E 2 G

4 2 3
B C H J F G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

Graph Theory S Sameen Fatima 71

 Add Edge 1 1
A D C F

C 2 E E 2 G

4 2 3
B C H J F G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

Graph Theory S Sameen Fatima 72

 Add Edge 1 1
A D C F

C 2 E E 2 G

4 2 3
B C H J F G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

Graph Theory S Sameen Fatima 73

 Cycle 1 1
A D C F

Don’t Add
Edge 2 2
C E E G

4 2 3
B C H J F G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

Graph Theory S Sameen Fatima 74

 Add Edge 1 1
A D C F

C 2 E E 2 G

4 2 3
B C H J F G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

Graph Theory S Sameen Fatima 75

 Minimum Spanning Tree Complete Graph

4
B C B 4 C
4 4
2 1 2 1
A E A 4
1 F E F
1

D 2 2
D 3
10
G G 5

3 5 6 3

4
I I
H H
2 3 3
J 2 J

Graph Theory S Sameen Fatima 76

 Prim's Algorithm

This algorithm starts with one node. It then, one by one, adds a node that
is unconnected to the new graph, each time selecting the node whose
connecting edge has the smallest weight out of the available nodes’
connecting edges.

Graph Theory S Sameen Fatima 78

 The steps are:

1. The new graph is constructed - with one node from the old graph.
2. While new graph has fewer than n nodes,
1. Find the node from the old graph with the smallest connecting
edge to the new graph,
2. Add it to the new graph

Every step will have joined one node, so that at the end we will have one
graph with all the nodes and it will be a minimum spanning tree of the
original graph.

Graph Theory S Sameen Fatima 79

 Complete Graph

4
B C
4
2 1

A 4 E
1 F

D 2 3
10
G 5

5 6 3

4
I
H

2 3
J

Graph Theory S Sameen Fatima 80

 Old Graph New Graph

4
B C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J

Graph Theory S Sameen Fatima 81

 Old Graph New Graph

4
B C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J

Graph Theory S Sameen Fatima 82

 Old Graph New Graph

4
B C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J

Graph Theory S Sameen Fatima 83

 Old Graph New Graph

4
B C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J

Graph Theory S Sameen Fatima 84

 Old Graph New Graph

4
B C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J

Graph Theory S Sameen Fatima 85

 Old Graph New Graph

4
B C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J

Graph Theory S Sameen Fatima 86

 Old Graph New Graph

4
B C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J

Graph Theory S Sameen Fatima 87

 Old Graph New Graph

4
B C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J

Graph Theory S Sameen Fatima 88

 Old Graph New Graph

4
B C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J

Graph Theory S Sameen Fatima 89

 Old Graph New Graph

4
B C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A 4 E F
1
D 2 3
10 D 2 3
G 5 10
G 5
5 6 3
5 6 3
4
I 4
H I
3 H
2 J
2 3
J

Graph Theory S Sameen Fatima 90

 Complete Graph Minimum Spanning Tree

4
B C
4 B 4 C
2 1 4
2 1
A 4 E
1 F A E F
1
D 2 3
10 D 2
G 5
G
5 6 3
3
4
I
H I
3 H
2 J
2 3
J

Graph Theory S Sameen Fatima 91

 Examples

• Cost of wiring electronic components

• Shortest route between two cities.
• Shortest distance between all pairs of cities in
a road atlas.
• Matching / Resource Allocation
• Task scheduling

Graph Theory S Sameen Fatima 101

 Examples

• Flow of material
– liquid flowing through pipes
–
current through electrical networks
–
information through networks
–
communication parts through an
• In Operating systems to model resource handling
assembly line
(deadlock problems)
• In compilers for and optimizing the code.
parsing

Graph Theory S Sameen Fatima 102

 Graph Algorithms

Graph Theory S Sameen Fatima 106

 Search Algorithms

• Breadth First Search

• Depth Dirst Search

Graph Theory S Sameen Fatima 107

 Breadth-First Search(BFS)

1. open  (initial state).

2. If open is empty , report failure , stop.
3. s  pop ( open )
4. If s is a solution , report s, stop.
5. succs  successors(s).
6. Add succs to tail of open.
7. go to 2.

Graph Theory S Sameen Fatima 108

 Space for BFS

Space is calculated in terms of open list.

In the worst case:

The solution may be the rightmost node at the last level
At the last level (level d) the no. of nodes = bd
Therefore,
Total no: of nodes in the open list = bd

Space O (bd)

Graph Theory S Sameen Fatima 109

 Time for BFS
In the worst case, the solution will be the right most node depth
at
d, that is all the nodes would
st
be expanded upto depth d.
No. of nodes processed at 1 level = 1
No. of nodes processed at the 2nd level = b
No: of nodes processed at the 3rd level = b2
…………..
No. of nodes processed at the dth level = bd
Therefore,
Total no. of nodes processed = 1 + b + b2 +……..bd.
= b ( bd – 1 )
(b – 1 )

O ( bd )
(ignoring 1 in comparison to b)

Graph Theory S Sameen Fatima 110

 Depth-First Search(DFS)

1. open  ( initial state )

2. If open is empty , report ,stop.
3. failure
4. s  pop ( open )
5. If s is a solution, report s, stop.
6. succs  successors (s).
7. add succs to head of open
go to 2.
Graph Theory S Sameen Fatima 111
 Space for DFS

Space is calculated in terms of open list.

In the worst case:

At the last level (level d) the no. of nodes = b
At each of the preceding (d-1) levels i.e., 1, 2, 3, …., (d-1), the no. of nodes = b-1
Therefore,
Total no: of nodes at the preceding (d-1) levels = (d-1)(b-1)

Space b+ (d-1) ( b-1)

b + db – d – b + 1
d ( b – 1) + 1
bd
O(d)
( In terms of open list )

Graph Theory S Sameen Fatima 112

 Time for DFS
In the worst case, the solution will be the right most node depth
at
d, that is all the nodes would
st
be expanded upto depth d.
No. of nodes processed at 1 level = 1
No. of nodes processed at the 2nd level = b
No: of nodes processed at the 3rd level = b2
…………..
No. of nodes processed at the dth level = bd
Therefore,
Total no. of nodes processed = 1 + b + b2 +……..bd.
= b ( bd – 1 )
(b – 1 )

O ( bd )
(ignoring 1 in comparison to b)

Graph Theory S Sameen Fatima 113

 Depth-First Iterative Deepening
(DFID)
The depth-first iterative deepening algorithm combines the
advantage of low space requirement of depth first search (DFS) and
advantage of finding an optimal solution of the breadth first search
(BFS)
time requirement, which is the same for both BFS and DFS

1. d1
2. result  depth first (initial state, d)
3. (Comment: try to find a solution of length d using depth first
search)
4.
If result ≠ NIL, report it, stop
5.
d  d+ 1
6.
go to 2

Graph Theory S Sameen Fatima 114

 Time requirement for DFID
On a search to depth d =1, b nodes are visited. For d = 2 , b1 + b2 nodes are visited and so on.
At d = k, b1 + b2 + …….. + bk nodes are visited

Let’s define the cost of DFID as a recurrence relation

DFID(1) = b1
DFID(k) = + DFID(k-1)

This expands to

bk + bk-1 + bk-2 + ………………….. + b1

bk-1 + bk-2 + ………………….. + b1
bk-2 + ………………….. + b1
……
…….
……..

bk +2bk-1 +3bk-2 + ………………….. +kb1

= bk

For large k the above expression asymptotes to bk (as the expression in the parenthesis
asymptotes
Graph Theory to 1). Hence time required for DFIDFatima
S Sameen is O(bk) 115
 Examples

• Shortest route between two cities.

• Shortest distance between all of cities in
pairs
• a road atlas.
• Matching / Resource Allocation
• Task scheduling
Cost of wiring electronic components
• Visibility / Coverage

Graph Theory S Sameen Fatima 116

 Examples

• Flow of material
– liquid flowing through pipes
–
current through electrical networks
–
information through networks
–
communication parts through an
• In Operating systems to model resource handling
assembly line
(deadlock problems)
• In compilers for and optimizing the code.
parsing

Graph Theory S Sameen Fatima 117

 Thank you

Graph Theory S Sameen Fatima 118