Transcript Directed Graphs

Directed Graphs
Chapter 8
1
Objectives
You will be able to:

Say what a directed graph is.

Describe two ways to represent a directed graph:



Describe two ways to traverse a directed graph:



Adjacency matrix.
Adjacency lists.
Depth first search
Breadth first search
Manually perform each kind of traversal on a
directed graph on paper.
2
Directed Graphs
A directed graph

A finite set of elements



A finite set of directed



Called vertices or nodes
Can hold values
Arcs or edges
Connect pairs of vertices
Often called a digraph.
3
Directed Graphs

Applications of directed graphs




Analyze electrical circuits
Find shortest routes
Develop project schedules
State diagrams
4
Graph Terminology

Multigraph


Pseudograph


A digraph in which there can be more than
one arc between a given pair of nodes.
A multigraph in which there can be an arc
from a node back to itself.
Graph

Arcs are bidirectional
5
Directed Graphs

Trees are a special kind of directed graph.



One node (the root) has no incoming edge.
Every other node can be reached from the root
by a unique path.
Graphs differ from trees as ADTs

Insertion of a node does not require an
incoming edge … or may have multiple edges.
6
Directed Graph as an ADT

A directed graph is defined as a collection of
data elements:


Called nodes or vertices
And a finite set of direct arcs or edges


Ordered pairs of nodes.
Operations include




Constructors
Insert node, edge
Delete node, edge
Search for a value in a node, starting from a given
node
7
Directed Graph Terminology

Weighted digraph



Each arc has a "cost" or "weight"
Example: Distance between cities connected
by highways.
Classic problem:

Find the shortest route from one city to
another.
8
Directed Graph Terminology

A complete digraph

Has an edge between each pair of vertices.


(Each direction)
N nodes will have N * (N – 1) edges
9
Directed Graph Representation

Adjacency matrix representation

Identify nodes with consecutive integers
1, 2, … n

The adjacency matrix is an n by n matrix.


Call it adj
Direction matters!
adj[i,j] is
• 1 (true) if vertex j is adjacent to vertex i
•
•
There is a directed arc from i to j
0 (false) otherwise
10
Graph Representation
columns j
“To” Vertex
1 2 3 4 5
rows i
“From” Vertex
1
2
3
4
5
0
0
0
0
0
1
0
1
0
0
0
1
1
0
0
1
0
0
0
1
1
0
0
1
0
0
0
0
• Entry [ 1, 5 ] set to true
• Edge from vertex 1 to
vertex 5
11
Adjacency Matrix Terminology

Out-degree of ith vertex (node)



Number of arc emanating from that node
Sum of 1's in row i
In-degree of jth vertex (node)


Number of arcs coming into that node
Sum of the 1's in column j
12
Adjacency Matrix

Consider the sum of the products of the
pairs of elements from row i and column j
adj 2
adj
1 2 3 4 5
1 2 3 4 5
1
2
3
4
5
0
0
0
0
0
1
0
10
0
0
1
1
0
0
1
0
0
0
1
10
0
1
0
0
0
0
1
2
3
4
5
1
This is the number of
paths of length 2 from
node 1 to node 3
13
Adjacency Matrix


This is matrix multiplication
3
 What is adj ?
The value in each entry would represent



The number of paths of length 3
From node i to node j
Consider the meaning of the
generalization of adj n
14
Adjacency Matrix

Deficiencies in adjacency matrix
representation


Data must be stored in
separate matrix
data =
When there are few edges the matrix is
sparse.

Wasted space
15
Adjacency List Representation

Solving problem of wasted space


Better to use an array of pointers to linked row-lists.
This is called an Adjacency List representation.
16
Searching a Graph

Recall that with a tree we search from the root.

But with a digraph …



There is no distinguished vertex.
There may not be a vertex from which every other
vertex can be reached.
May not be possible to traverse entire digraph
(regardless of starting vertex.)
17
Searching a Graph


We must determine which nodes are
reachable from a given node
Two standard methods of searching:


Depth first search
Breadth first search
18
Depth-First Search





Start from a given vertex v
Visit first neighbor w, of v
Then visit first neighbor of w which has not
already been visited.
Continue descent until we reach a node with no
unvisited neighbors.
When no unvisited neighbors


Back up to last visited node
Visit next unvisited neighbor of that node
19
Depth-First Search

Same as pre-order traversal of a tree except
we have to keep track of nodes visited and
avoid going back to them.
20
Depth-First Search


Start from node A.
What is the sequence of nodes that
would be visited in depth first search?
Click for answer
A, B, E, F, H, C, D, G
Same as pre-order traversal of the tree.
21
Depth-First Search


Start from node A.
What is the sequence of nodes that
would be visited in DFS?
Click for answer
A, B, F, G, C, D, H, I, E
22
Depth-First Search

DFS uses backtracking to return to vertices
that were seen earlier and



already processed or
skipped over on an earlier pass
Recursion is a natural technique for this task.
23
Depth-First Search
Algorithm to perform DFS search of digraph from
a specified starting vertex
1. Visit the start vertex, v
2. For each vertex w adjacent to v do:
If w has not been visited,
apply the depth-first search algorithm
with w as the start vertex.
Note the recursion
24
Breadth-First Search


A different search technique
At each point in the search, visit all previously
unvisited neighbors of current node before
advancing to their neighbors.
25
Breadth-First Search





Start from a given vertex v
Visit all neighbors of v
Then visit all previously unvisited neighbors of
first neighbor w of v.
Then visit all previously unvisited neighbors of
second neighbor x of v … etc.
Continue, visiting all vertices at distance N from
starting vertex before moving on to vertices at
distance N+1.
26
Breadth-First Search


Start from node containing A
What is a sequence of nodes which
would be visited in BFS?
Click for answer
A, B, D, E, F, C, H, G, I
27
Breadth-First Search

Notice distances from starting node.
A
BDE
FCH
GI
0
1
2
3
28
Breadth-First Search
Breadth-First Search defines a tree consisting
of nodes reachable from the starting node.

A
BDE
FCH
GI
0
1
2
3
29
Breadth-First Search Algorithm

While visiting each node on a given level

store its ID so that we can return to it after
completing this level.


So that nodes adjacent to it can be visited.
First node visited on given level should be
first node to which we return upon completion of
that level.
What data structure does this imply?
A queue
30
Breadth-First Search Algorithm
Algorithm for BFS search of a digraph from a
given starting vertex:

Visit the start vertex.
Initialize queue to contain only the start vertex.
While queue not empty do
1.
2.
3.
a.
b.
Remove a vertex v from the queue.
For all vertices w adjacent to v do:
If w has not been visited then:
i.
Visit w.
ii.
Add w to queue.
End while
End of section
31
Directed Graph Traversal
Algorithm to traverse digraph must:



1.
2.
Visit each vertex exactly once.
BFS or DFS forms basis of traversal.
Mark vertices when they have been visited.
Initialize an array (vector) visited.
visited[i] = false for each vertex i
While some element of visited is false
a.
Select an unvisited vertex v.
b.
Set visited[v] to true.
c.
Use BFS or DFS to visit all vertices reachable from v
End while
32