Introduction
Ch.22.Elementary Graph Algorithms
Read all sections
Omit theorems, corollaries, lemmas and their proofs (but learn the results described in the slides)
2
Conventions
V – set of vertices or nodes
E – set of edges
|V| = # of vertices or nodes = n
|E| = # of edges = m
3
22.1 Representations of graphs
types: undirected, directed & weighted graphs
what is the max # of edges in a n-node undirected graph?
adjacency matrix representation (for dense graphs)
adjacency-list representation (for sparse graphs)
4
Understand these examples!
5
22.2 Breadth-first search
An algorithm for searching a graph
Starting from a vertex s, visits every vertex that is reachable from s
Called breadth-first because it visits all vertices reachable from s in 1 step (by 1 edge) first, then those reachable in 2 steps, and so on.
Produces a breadth-first tree
6
22.2 Breadth-first search
Complexity: Θ(|V|+|E|)
7
The operation of BFS
Thinking Assignment: Work out and understand this example yourself
8
The operation of BFS
9
The operation of BFS
Thinking Assignment: Draw the breadth-first tree created by BFS
Thinking Assignment: What are the distances & shortest paths from s to every other node?
10
Thinking Assignment
PRINT_PATH(G, source, destination )
1 if source = destination
2 then print source
3 else if π[destination ]=NIL
4 then print “no path from” source “to” destination
5 else PRINT-PATH(G, source, π[destination])
6 print destination
Understand and simulate this recursive algorithm on the previous graph with source=s and destination=y
11
22.3 Depth-First Search
Another graph search algorithm
Depth-first: Go as deep as possible from s, then backtrack to find unvisited nodes
Builds a depth-first forest (several depth-first trees) in the process
Places two time stamps on each vertex: d[v] the time at which a vertex is “discovered” and f[v] when it’s processing is finished; Each timestamp is an integer between 1 and 2n
12
22.3 Depth-First Search
Complexity: Θ(|V|+|E|)
13
The operation of DFS
Thinking Assignment: Work out and understand this example yourself
14
The progress of DFS
15
The progress of DFS
16
The progress of DFS
17
Depth-first forest
Depth-first forest consists of trees that represent the edges of the original graph that the DFS algorithm traversed
These edges are called tree edges
The remaining edges in the original graph can be classified as back, forward, or cross edges
DFS of an undirected graph will produce only tree and back edges
DFS of a directed graph may produce tree, back, forward, or cross edges
18
Example: Graph, its depth-first forest and other edges
Thinking Assignment: Work out and understand this example yourself
19
To check if a graph has a cycle or not: a graph is acyclic if and only if the depth-first forest trees have no back edges
To check if the graph has one or more nodes whose removal will split the graph into separate pieces: if there are no such nodes (called articulation points) the graph is said to be biconnected.
To sort the nodes of the graph so that constraints modeled by the graph edges are satisfied: topological sort.
Depth-first search applications
20
22.4 Topological sort
21
Complexity: Θ(|V|+|E| )
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
22
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
Thinking Assignment
Come up with a different Topological Algorithm using this strategy:
In-degree of a node is the # of edges coming into it; if a node has in-degree zero, then it means that it is not dependent on any other nodes;
therefore, determine the in-degree of all nodes in the graph and store those;
if there is at least one such node (what does it mean if there are no such nodes?), output that as the first node in TO;
then remove all outgoing edges from it by decrementing the in-degrees of all nodes connected by those outgoing edges;
if that makes the in-degree of any node to be zero, output that as the first node in TO (what does it mean if there are no such nodes?);
repeat steps 2-4 until all nodes have been output to the TO
23
1534
24
253
412
25
1
2
3
4
5
1
54
2
3
01001
10111
01010
01101
11010
1
2
3
4
5
12345
5
65
2
4
24
1
2
3
4
5
6
6
1
45
23
6
010100
000010
000011
010000
000100
000001
1
2
3
4
5
12345
6
6
BFS(G, s)
1 for each vertex
uVG s (){}
2
whiteucolor ][
3
][ud
4
NILu][
5
grayscolor ][
6
0][sd
7
NILs][
8
}{sQ
9 while
Q
10
][Qheadu
11 for each
][uadjv
12 if
color v white[]
13 then
grayvcolor ][
14
1][][ udvd
15
uv][
16 ENQUEUE(Q, v)
17 DEQUEUE(Q)
18
BLACKucolor ][
white
u
color
=
]
[
¥
=
]
[
u
d
NIL
u
=
]
[
p
gray
s
color
=
]
[
0
]
[
=
s
d
NIL
s
=
]
[
p
}
{
s
Q
=
BFS(G, s)
1
for each vertex
2
3
4
5
6
7
8
9
while
_1413089611.unknown
_1413089662.unknown
_1413089733.unknown
_1413089759.unknown
_1413089698.unknown
_1413089638.unknown
_931259556.unknown
_1413089586.unknown
_931259297.unknown
]
[
Q
head
u
=
]
[
u
adj
v
=
gray
v
color
=
]
[
1
]
[
]
[
+
=
u
d
v
d
u
v
=
]
[
p
BLACK
u
color
=
]
[
10
11
for each
12
if
13
then
14
15
16
ENQUEUE(Q, v)
17
DEQUEUE(Q)
18
_1413089819.unknown
_1413089885.unknown
_1413090045.unknown
_1413090046.unknown
_1413090044.unknown
_1413089853.unknown
_931259654.unknown
DFS(G)
1 for each vertex
uVG[]
2
whiteucolor ][
3
NILu][
4
0time
5 for each vertex
uVG[]
6 if
color u white[]
7 then DFS-VISIT(u)
DFS-VISIT(u)
1
color u gray[]
2
1][ timetimeud
3 for each
vadj u []
4 if
whitevcolor ][
5 then
uv][
6 DFS-VISIT(v)
7
color u black[]
8
1][ timetimeuf
white
u
color
=
]
[
NIL
u
=
]
[
p
0
=
time
DFS(G)
1
for each vertex
2
3
4
5
for each vertex
6
if
7
then DFS-VISIT(u)
_931281985.unknown
_1413090085.unknown
_1413090103.unknown
_1413090121.unknown
_931282000.unknown
_931281853.unknown
1
]
[
+
=
=
time
time
u
d
white
v
color
=
]
[
u
v
=
]
[
p
1
]
[
+
=
=
time
time
u
f
DFS-VISIT(u)
1
2
3
for each
4
if
5
then
6
DFS-VISIT(v)
7
8
_931282104.unknown
_1270379603.unknown
_1413090340.unknown
_1413090341.unknown
_1413090205.unknown
_931282252.unknown
_931282068.unknown
A topological sort of a directed acyclic graph G = (V, E) is a linear
ordering of all its vertices such that if G contains an edge ( u, v), then
u appears before v in the ordering.
A topological sort of a directed acyclic graph G = (V, E) is a linear ordering of all its vertices such that if G contains an edge (u, v), then u appears before v in the ordering.
TOPOLOGICAL_SORT( G)
1 call DFS(G) to compute finishing time f( v) for each
vertex v.
2 as each vertex is finished, insert it onto the front of a
link list.
3 return the link list of vertices
TOPOLOGICAL_SORT(G)
1
call DFS(G) to compute finishing time f(v) for each vertex v.
2
as each vertex is finished, insert it onto the front
of a link list.
3
return the link list of vertices
/docProps/thumbnail.jpeg