=============================================================================
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.