=============================================================================
CSC 263Lecture Summary for Week8Fall 2019
=============================================================================
READING: Sections 22.1, 22.2, Appendix B.4
SELF-TEST: Exercises 22.1-1, 22.1-2, 22.2-1.
——
Graphs
——
– Graph G = (V,E): “vertices”/”nodes” V, “edges”/”arcs” E.
Directed graph: E contains ordered pairs (u,v) in V^2; (u,v) != (v,u) and
(v,v) (self-loops) allowed.
Undirected graph: E contains unordered pairs {u,v} (_ V: {u,v} = {v,u}
and {v,v} = {v} disallowed.
Weighted graph: “weight”/”cost” w(e) in R for all e in E.
– Standard operations on graphs:
* Add a vertex; Remove a vertex; Add an edge; Remove an edge.
* Edge Query: given vertices u,v, does G contain edge (u,v) or {u,v}?
* Neighbourhood (undirected graph): given vertex u, return set of
vertices v such that {u,v} in E.
* In-neighbourhood/out-neighbourhood (directed graph): given vertex u,
return set of vertices v such that (u,v)/(v,u) in E.
* Degree/in-degree/out-degree: size of neighbourhood / in-neighbourhood
/ out-neighbourhood.
* Traversal: visit each vertex of a graph to perform some task.
* etc.
– Definitions:
* Path = sequence of vertices p =
(v_{i-1},v_i) in E
“Path p has length k” (counts number of edges)
“Path p goes from v_0 to v_k”
“Path p contains the vertices v_0, v_1, …, v_k”
“v_k is reachable from v_0 (via the path p)”
– zero length path is permitted, p =
– zero length path from a vertex always exists
* Simple path = path with distinct vertices
* Cycle = path with at least one edge and v_0 = v_k
* Simple cycle = cycle where v_1, …, v_k are distinct
* Connected graph = for any two vertices, a path exists connecting them
“every vertex is reachable (by a path) from every other vertex”
* Connected component = equivalence classes of vertices under the “is reachable from” relation
– maximal C subset V such that
every v_i in C is reachable from every v_j in C
* Acyclic graph = does not contain any cycles
* Tree = graph that is connected and acyclic
* Forest = acyclic graph (collection of disjoint trees, each one a
“connected component”)
Data Structures for Graphs:
– Two standard data structures: adjacency matrices, adjacency lists.
– Adjacency matrix: let V = {v_1,v_2,…,v_n}. Store edges in [n x n]
array:
{ 1if (v_i,v_j) in E
A[i,j] = {
{ 0if (v_i,v_j) not in E
Undirected graphs: matrix is symmetric (A[i,j] = A[j,i]).
Space? Theta(n^2) — but edge queries take time Theta(1).
Weighted graph: store w(v_i,v_j) in A[i,j] if (v_i,v_j) in E; special
value (-1/0/oo) otherwise (depending on application).
– Adjacency lists: let V = {v_1,v_2,…,v_n}. Store edges in a list of
lists: “main” list has positions 1,…,n (one for each vertex);
sub-list[i] contains j_1,…,j_{k_i} such that (v_i,v_{j_1}), …,
(v_i,v_{i_{k_i}}) are all edges from v_i.
Undirected graph: edge {u,v} stored twice (u in sub-list[v] and v in
sub-list[u]).
Space Theta(n+m) (where n = |V| and m = |E|).
Edge queries in time Theta(log n) (actually, Theta(log(max degree))) if
sub-lists stored in balanced trees.
– Examples:
Directed
s ——> a ——> b
| | / |V = {s,a,b,c,d,e,f}
| |v|
| |c|E = { (s,a), (s,f), (a,b), (a,e),
| |/ |(b,c), (b,d), (c,d), (c,e),
v v v v v(e,d), (e,f) }
f <—— e ——> d
Adj. matrix: Adj. lists:
| s a b c d e f
—|—————s: [a,f]
s | 0 1 0 0 0 0 1 a: [b,e]
a | 0 0 1 0 0 1 0 b: [c,d]
b | 0 0 0 1 1 0 0 c: [d,e]
c | 0 0 0 0 1 1 0 d: []
d | 0 0 0 0 0 0 0 e: [d,f]
e | 0 0 0 0 1 0 1 f: []
f | 0 0 0 0 0 0 0
Undirected
s ——- a ——- b
| | / |V = {s,a,b,c,d,e,f}
| |/|
| |c|E = { {s,a}, {s,f}, {a,b}, {a,e},
| |/ |{b,c}, {b,d}, {c,d}, {c,e},
| | / |{e,d}, {e,f} }
f ——- e ——- d
Adj. matrix: Adj. lists:
| s a b c d e f
—|—————s: [a,f]
s | 0 1 0 0 0 0 1 a: [s,b,e]
a | 1 0 1 0 0 1 0 b: [a,c,d]
b | 0 1 0 1 1 0 0 c: [b,d,e]
c | 0 0 1 0 1 1 0 d: [b,c,e]
d | 0 0 1 1 0 1 0 e: [a,c,d,f]
e | 0 1 0 1 1 0 1 f: [s,e]
f | 1 0 0 0 0 1 0
——————–
Breadth-First Search
——————–
– Starting from “source” s in V, BFS “visits” every vertex v reachable from
s. In the process, we find paths from s to v for each reachable v — “BFS
tree”. BFS works on directed or undirected graphs.
– Keeping track of progress: “colour” each vertex white (initially). First
time a vertex is discovered, colour it gray. Once a vertex has been
explored, colour it black. Difference between “discovered” and
“explored” will become clear in algorithm.
Also, for each vertex v, keep track of “predecessor” of v in BFS tree,
pi[v], and keep track of “distance” (length of path) from s to v, d[v].
– Intuitively, white vertices “undiscovered”, black vertices “discovered”
and fully “explored” (BFS has examined all neighbours), gray vertices
“discovered” but not fully explored: they represent “frontier”.
Distinction between white and other colours is how BFS keeps track of
vertices to explore next so that it really works “breadth-first”: gray
vertices stored in queue to handle in first-in, first-out order.
– BFS Tree – consider the source to be the root. Consider each ENQUEUE
operation below to be the creation of a child, i.e., when a vertex is visited,
the incident vertices that are consequently enqueued are its “children” in the
timeline of the search. Thus the BST order of traversal can be diagrammed
as a tree.
– Algorithm:
BFS(G=(V,E),s):
# Initialization.
for all v in V:
colour[v] <- whited[v] <- oopi[v] <- NILinitialize empty queue Qcolour[s] <- grayd[s] <- 0pi[s] <- NIL# not necessary because of loop aboveENQUEUE(Q,s)# Loop invariant: Q contains exactly the gray vertices.while Q not empty:u <- DEQUEUE(Q)for each edge (u,v) in E:if colour[v] == white:colour[v] <- grayd[v] <- d[u] + 1pi[v] <- uENQUEUE(Q,v)colour[u] <- blackExecution of BFS on directed example above:s ——> a ——> b
| | / |
| |v|
| |c|
| |/ |
v v v v v
f <—— e ——> d
– Queue: [s]
. Dequeue s — edges (s,a), (s,f)
. Enqueue a (d[a] = 1, pi[a] = s)
. Enqueue f (d[f] = 1, pi[f] = s)
– Queue: [a,f]
. Dequeue a — edges (a,b), (a,e)
. Enqueue b (d[b] = 2, pi[b] = a)
. Euqueue e (d[e] = 2, pi[e] = a)
– Queue: [f,b,e]
. Dequeue f — no edge
– Queue: [b,e]
. Dequeue b — edges (b,c), (b,d)
. Enqueue c (d[c] = 3, pi[c] = b)
. Enqueue d (d[d] = 3, pi[d] = b)
– Queue: [e,c,d]
. Dequeue e — edges (e,d), (e,f)
– Queue: [c,d]
. Dequeue c — edges (c,d), (c,e)
– Queue: [d]
. Dequeue d — no edge
– Queue: []
Reviews
There are no reviews yet.