Data Structures and Algorithms

Lecture 07

Bushra Bashir Chaoudhry

Graphs
 All tree structures are hierarchical. This
means that each node can only have one
parent node. Trees can be used to store data
which has a definite hierarchy; for example a
family tree or a computer file system.
 Some data need to have connections between

items which do not fit into a hierarchy like

this.
◦ Graph data structures can be useful in these
situations.
What is a Graph?
 A graph G = (V,E) is composed of:
V: set of vertices
E: set of edges connecting the vertices in V
 An edge e = (u,v) is a pair of vertices
 Example:
a b
V= {a,b,c,d,e}

E= {(a,b),(a,c),(a,d),
c (b,e),(c,d),(c,e),
(d,e)}

d e
Some Problems that can be
Represented by a Graph
 computer networks
 airline flights
 road map
 course prerequisite structure
 tasks for completing a job
 flow of control through a program
 many more
Adjacent and Incident

 If (v0, v1) is an edge in an undirected graph,

◦ v0 and v1 are adjacent
◦ The edge (v0, v1) is incident on vertices v0 and v1
 If <v0, v1> is an edge in a directed graph
◦ v0 is adjacent to v1, and v1 is adjacent from v0
◦ The edge <v0, v1> is incident on v0 and v1
 Degree of a Vertex

 The degree of a vertex is the number of edges

incident to that vertex
 For directed graph,
 the in-degree of a vertex v is the number of edges
that have v as the head
 the out-degree of a vertex v is the number of
edges
that have v as the tail
 if di is the degree of a vertex i in a graph G with n
n 1
vertices and e edges, the number of edges is
e(  0
di ) / 2 Why? Since adjacent vertices each
count the adjoining edge, it will be
counted twice
Examples
0
3 2
0 1 2
3 3
3 1 23 3 4 5 6
3G1 1 1 G2 1 1
3
0 in:1, out: 1
directed graph
in-degree
out-degree 1 in: 1, out: 2

2 in: 1, out: 0
G3
Graph Variations
 Undirected graph (graph)
 Directed graph (digraph)

◦ For either type, edges may be weighted or un-

weighted
undirected graph.
 An undirected graph is a graph in which the
nodes are connected by undirected arcs.
 An undirected arc is an edge that has no

arrow. Both ends of an undirected arc are

equivalent--there is no head or tail.
◦ Edges do not have a direction
 (V1, V2) and (V2, V1) are the same edge
A graph

E
B

D
C

V = [A, B, C, D, E]
E = [<A,B>, <B,C>, <A,C>, <A,E>, <C,D>]
Path
 Path: Sequence
a b
of vertices
v1,v2,. . .vk such
c
that consecutive
vertices vi and vi+1 d e
are adjacent.
a b a b

c c

d e d e
abedc bedc
11
 More Terminology
 Simple Path: no repeated vertices
a b

bec
c

d e
 Cycle: simple path, except that the last vertex
is the same as the
a first vertex b

acda
c

d e
Directed Graphs
 In a directed graph, or digraph, each edge is
an ordered pair of vertices – it has a direction
defined. The direction is indicated by an
arrow.
 A path in a directed graph must follow the
direction of the arrows.
 A directed graph is connected if, for any pair
of vertices, there is a path between them.
◦ edges have a direction
 <V1, V2> and <V2, V1> are different edges
A Digraph

B E

C D

V = [A, B, C, D, E]
E = [<A,B>, <B,C>, <C,B>, <A,C>, <A,E>, <C,D>]
A Graph ADT: Operations
 Need to define
◦ Operations for modifying and inspecting graph.
◦ Data structure for graph itself.
 For simple undirected, unlabelled graph, a
small set of operations is enough, to:
◦ Create a graph.
◦ Add and remove edges to the graph.
◦ Check if an edge exists.
Implementing a Graph
 Storing the vertices
◦ each vertex has a unique identifier and, maybe,
other information
◦ for efficiency, associate each vertex with a number
that can be used as an index
 Storing the edges
◦ adjacency matrix – represent all possible edges
◦ adjacency lists – represent only the existing edges
Storing the Vertices
 When a vertex is added to the graph, assign
it a number
◦ vertices are numbered between 0 and n-1
 Graph operations start by looking up the
number associated with a vertex
 Many data structures to use
◦ any of the associative data structures
◦ for small graphs a vector can be used
 search will be O(n)
Graph Traversal
How to visit all vertices in a graph in some systematic order?
 Graph traversal may start at an arbitrary vertex. (Tree
traversal generally starts at root vertex.)
 Two difficulties in graph traversal, but not in tree traversal:
 The graph may contain cycles;
 The graph may not be connected.
 There are two important traversal methods:
 Breadth-first traversal, based on breadth-first search
(BFS).
 Depth-first traversal, based on depth-first search (DFS).
Breadth-First Search Traversal
Breadth-first traversal of a graph:
 Is roughly analogous to level-by-level traversal
of an ordered tree
 Start the traversal from an arbitrary vertex;
 Visit all of its adjacent vertices;
 Then, visit all unvisited adjacent vertices of
those visited vertices in last level;
 Continue this process, until all vertices have
been visited.
0 8 0 8
source
2 9 source
2 9
1 7 1 7
4 4
3 3
5 6 5 6
Breadth-First Traversal
The pseudocode of breadth-first traversal algorithm:

BFS(G,s)
for each vertex u in V
do visited[u] = false

Report(s)
visited[s] = true

initialize an empty Q
Enqueue(Q,s)
Breadth-First Traversal
While Q is not empty
do u = Dequeue(Q)
for each v in Adj[u]
do if visited[v] = false
then Report(v)
visited[v] = true
Enqueue(Q,v)
An Example

1 2 6 5

7 4 3
Breadth-First Search Traversal
Example of breadth-first traversal
 Visit the first vertex (in this example 0)
 Visit its adjacent nodes in Adj[0] :7 5 2 1 6
 Visit adjacent unvisited nodes of the those visited in
last level
- Visit adjacent nodes of 7 in Adj[7] : 4
- Visit adjacent nodes of 5 in Adj[5] : 3
- Visit adjacent nodes of 2 in Adj[2] : none
- Visit adjacent nodes of 1 in Adj[1] : none
- Visit adjacent nodes of 6 in Adj[6] : none
 Visit adjacent unvisited nodes of the those visited in
last level 0
0
- Visit adjacent nodes of 4 in Adj[4] : none
- Visit adjacent nodes of 3 in Adj[3] : none 1
1 2
2 6
6 5
5
 Done

7
7 4
4 3
3
Breadth-First Traversal
Breadth-first traversal of a graph:
 Implemented with queue;
 Visit an adjacent unvisited vertex to the current

vertex, mark it, insert the vertex into the queue,

visit next.
 If no more adjacent vertex to visit, remove a

vertex from the queue (if possible) and make it

the current vertex.
 If the queue is empty and there is no vertex to

insert into the queue, then the traversal process

finishes.
Depth-First Search
1. From the given vertex, visit one of its
adjacent vertices and leave others;
2. Then visit one of the adjacent vertices of the
previous vertex;
3. Continue the process, visit the graph as
deep as possible until:
◦ A visited vertex is reached;
◦ An end vertex is reached.
Depth-First Traversal
1. Start the traversal from an arbitrary vertex;
2. Apply depth-first search;
3. When the search terminates, backtrack to
the previous vertex of the finishing point,
4. Repeat depth-first search on other adjacent
vertices, then backtrack to one level up.
5. Continue the process until all the vertices
that are reachable from the starting vertex
are visited.
6. Repeat above processes until all vertices are
visited.
0 8 0 8
source
2 9 source
2 9
4 1 7 4 1 7
3 3
5 6 5 6
Depth-First Traversal
The pseudocode of depth-first traversal algorithm:

Boolean visited[V.size];

void DepthFirst(Graph G) {
Vertex u;
for each vertex u in V
do visited[u] = false;
for each vertex u in V
do if visited[u] = false
then RDFS(u);
}
Depth-First Traversal
void RDFS(Vertex u)
{ visited[u] = true;
Visit(u);
for each vertex w in Adj[u]
do if visited[w] = false
then RDFS(w);
}
Example: Depth-First Traversal
An adjacent list of a graph:

1 2 6 5

7 4 3
Example: Depth-First Traversal
Function calls of depth-first traversal of the graph

visit 0
visit 7 (first on 0’s list)
visit 1 (first on 7’s list)
check 7 on 1’s list
check 0 on 1’s list
visit 2 (second on 7’s list)
check 7 on 2’s list 0
check 0 on 2’s list
check 0 on 7’s list
visit 4 (fourth on 7’s list)
1 2 6 5
visit 6 (first on 4’s list)
check 4 on 6’s list
check 0 on 6’s list

7 4 3
Example: Depth-First Traversal
visit 5 (second on 4’s list)
check 0 on 5’s list
check 4 on 5’s list
visit 3 (third on 5’s list)
check 5 on 3’s list
check 4 on 3’s list
check 7 on 4’s list
check 3 on 4’s list
check 5 on 0’s list 0
check 2 on 0’s list
check 1 on 0’s list
check 6 on 0’s list 1 2 6 5

End recursive calls

7 4 3
Depth-First Traversal
 Depth-first traversal of a graph:
◦ Can be implemented with stack, since recursion and
programming with stacks are equivalent;
◦ Visit a vertex v
◦ Push all adjacent unvisited vertices of v onto a stack
◦ Pop a vertex off the stack until it is unvisited
◦ Repeat these steps
◦ If the stack is empty and there is no vertex to push
onto the stack, then the traversal process finishes.
◦ Applications: eliminate cycle in a graph, and keep
the graph connected
Weighted Graphs
 In a weighted graph, each edge has an associated
numerical value, called the weight of the edge
 Edge weights may represent, distances, costs,
etc.
 Example:
◦ In a flight route graph, the weight of an edge
represents the distance in miles between the endpoint
airports

849 PSH
1843 ISB 2
LHR 14

802
KOH

1205
43
17
337

7
MUL 2555 138 10
99
1233
GUJ DGHK 1120
KHI
Shortest Path Problem
 Given a weighted graph and two vertices u and v, we want
to find a path of minimum total weight between u and v.
◦ Length of a path is the sum of the weights of its edges.
 Example:
◦ Shortest path between Peshawar and Multan
 Applications
◦ Internet packet routing
◦ Flight reservations
◦ Driving directions
3 849 PSH
18 4 ISB
142
LHR
802

1205
7 43 KOH
337

1 87 10
2555 13
MUL 1233 99
GUJ DGHK 1120
KHI
Dijkstra’s Algorithm
 The distance of a vertex v from a vertex s is
the length of a shortest path between s and v
 Dijkstra’s algorithm computes the distances

of all the vertices from a given start vertex s

 Assumptions:

◦ the graph is connected

◦ the edges are undirected
◦ the edge weights are nonnegative
Dijkstra’s Algorithm
 We grow a “cloud” of vertices, beginning with
s and eventually covering all the vertices
 We store with each vertex v a label d(v)

representing the distance of v from s in the

subgraph consisting of the cloud and its
adjacent vertices
 At each step

◦ We add to the cloud the vertex u outside the cloud

with the smallest distance label, d(u)
◦ We update the labels of the vertices adjacent to u