The document discusses graph algorithms and data structures. It introduces breadth-first search (BFS) and depth-first search (DFS) algorithms for traversing graphs. BFS can be modified to find the shortest paths from a source vertex by tracking distances and predecessors. DFS numbers nodes by discovery and finish times to provide information about the search order. Adjacency lists and matrices are also presented as ways to represent graphs.
The document discusses graph algorithms and data structures. It introduces breadth-first search (BFS) and depth-first search (DFS) algorithms for traversing graphs. BFS can be modified to find the shortest paths from a source vertex by tracking distances and predecessors. DFS numbers nodes by discovery and finish times to provide information about the search order. Adjacency lists and matrices are also presented as ways to represent graphs.
The document discusses graph algorithms and data structures. It introduces breadth-first search (BFS) and depth-first search (DFS) algorithms for traversing graphs. BFS can be modified to find the shortest paths from a source vertex by tracking distances and predecessors. DFS numbers nodes by discovery and finish times to provide information about the search order. Adjacency lists and matrices are also presented as ways to represent graphs.
The document discusses graph algorithms and data structures. It introduces breadth-first search (BFS) and depth-first search (DFS) algorithms for traversing graphs. BFS can be modified to find the shortest paths from a source vertex by tracking distances and predecessors. DFS numbers nodes by discovery and finish times to provide information about the search order. Adjacency lists and matrices are also presented as ways to represent graphs.
A graph G = (V, E): V is a finite set of vertices. E is a set of vertex pairs called edges. directed edge (arc): (u, v), u, v V undirected edge: {u, v}, u, v V, u v 2/14/02 Introduction to Algorithms CLRS16.2
Array Adj of |V| lists. Space requirement is (V + E). Query (u, v) E? takes O(E) time. Suitable for sparse graphs: |E| = o(V2). 2/14/02 Introduction to Algorithms CLRS16.3
|V| |V| matrix A. Space requirement is (V2). Query (u, v) E? takes (1) time. Suitable for dense graphs: |E| = (V2). 2/14/02 Introduction to Algorithms CLRS16.4
Breadth-first search rr vv ss tt w w u u x x BFS(G, s) for each vertex u V[G] {s} do state[u] undiscovered state[s] discovered Q ENQUEUE(Q, s) while Q do u DEQUEUE(Q) for each v Adj[u] do if state[v] = undiscovered then state[v] discovered ENQUEUE(Q, v) state[u] completely explored
the closer the earlier can be modified to find shortest-paths from a source vertex. Denote by (s, v) the shortest-path distance from source s to vertex v V. 2/14/02 Introduction to Algorithms
CLRS16.5
Shortest paths with BFS
BFS(G, s) for each vertex u V[G] {s} do state[u] undiscovered state[s] discovered vv w x Q w x ENQUEUE(Q, s) Use arrays d and to store shortest while Q do u DEQUEUE(Q) distances and predecessors. for each v Adj[u] do Initialize: d[u] + for all if state[v] = undiscovered then nonsource vertices u, d[s] 0. state[v] discovered ENQUEUE(Q, v) As vertex v is discovered from state[u] completely explored
rr
ss
tt
u u
vertex u, set d[v] d[u] + 1.
Theorem. d[v] = (s, v) for all v V upon termination of BFS.
2/14/02 Introduction to Algorithms CLRS16.6
Shortest paths with BFS
r: r: vv: : s:0 s:0 t: t: w: w: s:0 u: u: x: x: BFS(G, s) for each vertex u V[G] {s} do state[u] undiscovered d[u] , [u] NIL state[s] discovered d[s] 0, [s] NIL Q ENQUEUE(Q, s) while Q do u DEQUEUE(Q) for each v Adj[u] do if state[v] = undiscovered then state[v] discovered d[v] d[u] + 1, [v] u ENQUEUE(Q, v) state[u] completely explored CLRS16.7
2/14/02
Introduction to Algorithms
Shortest paths with BFS
r: r: vv:1 :1 s:0 s:0 t:1 t:1 w: w: t:1 v:1 u: u: x: x: BFS(G, s) for each vertex u V[G] {s} do state[u] undiscovered d[u] , [u] NIL state[s] discovered d[s] 0, [s] NIL Q ENQUEUE(Q, s) while Q do u DEQUEUE(Q) for each v Adj[u] do if state[v] = undiscovered then state[v] discovered d[v] d[u] + 1, [v] u ENQUEUE(Q, v) state[u] completely explored CLRS16.8
2/14/02
Introduction to Algorithms
Shortest paths with BFS
r: r: vv:1 :1 s:0 s:0 t:1 t:1 w:2 w:2 v:1 w:2 u: u: x: x: BFS(G, s) for each vertex u V[G] {s} do state[u] undiscovered d[u] , [u] NIL state[s] discovered d[s] 0, [s] NIL Q ENQUEUE(Q, s) while Q do u DEQUEUE(Q) for each v Adj[u] do if state[v] = undiscovered then state[v] discovered d[v] d[u] + 1, [v] u ENQUEUE(Q, v) state[u] completely explored CLRS16.9
2/14/02
Introduction to Algorithms
Shortest paths with BFS
r:2 r:2 vv:1 :1 s:0 s:0 t:1 t:1 w:2 w:2 w:2 r:2 u: u: x: x: BFS(G, s) for each vertex u V[G] {s} do state[u] undiscovered d[u] , [u] NIL state[s] discovered d[s] 0, [s] NIL Q ENQUEUE(Q, s) while Q do u DEQUEUE(Q) for each v Adj[u] do if state[v] = undiscovered then state[v] discovered d[v] d[u] + 1, [v] u ENQUEUE(Q, v) state[u] completely explored CLRS16.10
2/14/02
Introduction to Algorithms
Shortest paths with BFS
r:2 r:2 vv:1 :1 s:0 s:0 t:1 t:1 w:2 w:2 r:2 u:3 x:3 u:3 u:3 x:3 x:3 BFS(G, s) for each vertex u V[G] {s} do state[u] undiscovered d[u] , [u] NIL state[s] discovered d[s] 0, [s] NIL Q ENQUEUE(Q, s) while Q do u DEQUEUE(Q) for each v Adj[u] do if state[v] = undiscovered then state[v] discovered d[v] d[u] + 1, [v] u ENQUEUE(Q, v) state[u] completely explored CLRS16.11
2/14/02
Introduction to Algorithms
Shortest paths with BFS
r:2 r:2 vv:1 :1 s:0 s:0 t:1 t:1 w:2 w:2 u:3 x:3 u:3 u:3 x:3 x:3 BFS(G, s) for each vertex u V[G] {s} do state[u] undiscovered d[u] , [u] NIL state[s] discovered d[s] 0, [s] NIL Q ENQUEUE(Q, s) while Q do u DEQUEUE(Q) for each v Adj[u] do if state[v] = undiscovered then state[v] discovered d[v] d[u] + 1, [v] u ENQUEUE(Q, v) state[u] completely explored CLRS16.12
2/14/02
Introduction to Algorithms
Shortest paths with BFS
r:2 r:2 vv:1 :1 s:0 s:0 t:1 t:1 w:2 w:2 x:3 u:3 u:3 x:3 x:3 BFS(G, s) for each vertex u V[G] {s} do state[u] undiscovered d[u] , [u] NIL state[s] discovered d[s] 0, [s] NIL Q ENQUEUE(Q, s) while Q do u DEQUEUE(Q) for each v Adj[u] do if state[v] = undiscovered then state[v] discovered d[v] d[u] + 1, [v] u ENQUEUE(Q, v) state[u] completely explored CLRS16.13
2/14/02
Introduction to Algorithms
Shortest paths with BFS
BFS(G, s) for each vertex u V[G] {s} do state[u] undiscovered d[u] , [u] NIL vv:1 w:2 x:3 state[s] discovered :1 w:2 x:3 d[s] 0, [s] NIL Q ENQUEUE(Q, s) while Q do u DEQUEUE(Q) for each v Adj[u] do if state[v] = undiscovered then G = (V, E) where state[v] discovered V = {vV: [v] NIL} {s} d[v] d[u] + 1, [v] u ENQUEUE(Q, v) E = {([v], v): vV {s}} state[u] completely explored r:2 r:2 s:0 s:0 t:1 t:1 u:3 u:3
Q Breadth-first search tree
Running time: O(V + E)
2/14/02
Introduction to Algorithms
CLRS16.14
Depth-first search rr vv ss tt w w u u x x DFS(G) for each vertex u V[G] do state[u] undiscovered [u] NIL time 0 for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1 CLRS16.15
search deeper, backtrack when stuck produces a DFS forest makes recursive calls to DFS-VISIT 2/14/02
Introduction to Algorithms
Depth-first search r:1/ r:1/
ss
tt w w
u u x x
vv
For each node u, compute d[u]: time of first visit f[u]: time when all adjacent nodes have been visited 2/14/02
DFS(G) for each vertex u V[G] do state[u] undiscovered [u] NIL time 0 for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1 CLRS16.16
Introduction to Algorithms
Depth-first search r:1/ r:1/
ss
tt w w
u u x x
v:2/ v:2/
DFS(G) for each vertex u V[G] do state[u] undiscovered [u] NIL time 0 for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1
2/14/02
Introduction to Algorithms
CLRS16.17
Depth-first search r:1/ r:1/ s:3/ s:3/
tt w w
u u x x
v:2/ v:2/
DFS(G) for each vertex u V[G] do state[u] undiscovered [u] NIL time 0 for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1
2/14/02
Introduction to Algorithms
CLRS16.18
Depth-first search r:1/ r:1/ s:3/ s:3/ t:4/ t:4/
u u x x
v:2/ v:2/
w w
DFS(G) for each vertex u V[G] do state[u] undiscovered [u] NIL time 0 for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1
DFS(G) for each vertex u V[G] do state[u] undiscovered [u] NIL time 0 for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1
DFS(G) for each vertex u V[G] do state[u] undiscovered [u] NIL time 0 for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1
DFS(G) for each vertex u V[G] do state[u] undiscovered [u] NIL time 0 for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1
DFS(G) for each vertex u V[G] do state[u] undiscovered [u] NIL time 0 for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1
DFS(G) for each vertex u V[G] do state[u] undiscovered [u] NIL time 0 for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1
DFS(G) for each vertex u V[G] do state[u] undiscovered [u] NIL time 0 for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1
DFS(G) u:11/ for each vertex u V[G] do u:11/ state[u] undiscovered [u] NIL time 0 x x for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1
DFS(G) u:11/ for each vertex u V[G] do u:11/ state[u] undiscovered [u] NIL time 0 x:12/ x:12/ for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1
DFS(G) u:11/ for each vertex u V[G] do u:11/ state[u] undiscovered [u] NIL time 0 x:12/13 x:12/13 for each vertex u V[G] do if state[u] = undiscovered then DFS-VISIT(u) DFS-VISIT(u) state[u] discovered d[u] time time + 1 for each v Adj[u] do if state[v] = undiscovered then [v] u DFS-VISIT(v) state[u] completely explored f[u] time time + 1
Classification of edges tree edges: those on the DFS forest back edges: those that connect descendants to ancestors (self-loops, too) forward edges: non-tree edges connecting ancestors to descendants cross edges: all other edges 2/14/02 Introduction to Algorithms
Theorem. (Parenthesis structure) Let I[u] = [d[u], f[u]]. Then either I[u] and I[v] are disjoint or one is entirely contained within the other.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 (r (v (s (t t) s) (w w) v) r) (u (x x) u) 2/14/02 Introduction to Algorithms CLRS16.30
Topological sort u u x x vv yy w w zz TOPOLOGICAL-SORT(G) call DFS(G) to compute the finishing times f[v] for each vertex v as each vertex is finished, insert it onto the front of a linked list return the linked list of vertices
A topological sort of a dag G = (V, E) is a linear ordering p of V such that if (u, v) E then u p v. Lemma. A directed graph is acyclic if and only if a depth-first search of G yields no back edges. 2/14/02 Introduction to Algorithms CLRS16.31
TOPOLOGICAL-SORT(G) call DFS(G) to compute the finishing times f[v] for each vertex v as each vertex is finished, insert it onto the front of a linked list return the linked list of vertices
u u
vv
yy
zz
x x
w w
Topological sort: u p v p y p z p x p w Running time: (V + E)
2/14/02 Introduction to Algorithms CLRS16.32
Strongly connected components
Given a digraph G = (V, E). Write u v if there is a path from u to v in G. a a g g b b h h cc ii d d jj ee k k ff ll
A strongly connected component of G is a maximal set of vertices C V such that for every pair u, v V, both u v and v u, that is, u and v are reachable from each other. 2/14/02 Introduction to Algorithms CLRS16.33
Strongly connected components
A (V + E) algorithm: a:1/24 a:1/24 b:2/21 b:2/21 c:5/18 c:5/18 d:6/17 d:6/17 e:7/16 e:7/16 f:8/11 f:8/11
g:22/23 g:22/23
h:3/20 h:3/20
i:4/19 i:4/19
j:13/14 j:13/14
k:12/15 k:12/15
l:9/10 l:9/10
STRONGLY-CONNECTED-COMPONENTS(G) call DFS(G) to compute the finishing times f[u] for each vertex u compute GT call DFS(GT), but in the main loop of DFS, consider the vertices in order of decreasing f[u] output the vertices of each tree in the DFS forest as a separate strongly connected component 2/14/02 Introduction to Algorithms CLRS16.34
Strongly connected components
The transpose graph and its DFS trees: a:1/2 a:1/2 b:5/12 b:5/12 c:6/11 c:6/11 d:13/20 d:13/20 e:16/17 e:16/17 f:21/22 f:21/22
g:3/4 g:3/4
h:8/9 h:8/9
i:7/10 i:7/10
j:14/19 j:14/19
k:15/18 k:15/18
l:23/24 l:23/24
The strongly connected components are therefore {a}, {g}, {b, c, h, i}, {d, e, j, k}, {f}, {l}. 2/14/02 Introduction to Algorithms CLRS16.35
