ADT vs Datastructure:
Lecture 9: Graphs 1
Felipe Vicencio-Heap July 28, 2020
1
READING: Sections 22.1, 22.2, Appendix B.4
SELF-TEST: Exercises 22.1-1, 22.1-2, 22.2-1.
Graph G = (V, E). An ordered pair of a set of vertices and a set of edges. Graphs can be directed or undirected, and edges can be weighted. Standard operations:
• add and remove vertices and edges • edge query
• (in/out) neighbourhood
• (in/out) degree
• traversal
• many others!
2
Definitions:
• Path: a sequece of vertices P = v0…vk such that ∀i ∈ N,i < k ⇒
(vi, vi+1) ∈ E
P has length k.
P goes from v0 to vk.
P contains the vertices v0,...,vk.
vk is reachable from v0 (via P).
Zero length paths are permitted: P = v0 v0 is reachable from v0
• Simple path: a path in which all vertices are distinct.
• Cycle: a path of with at least 3 edges and v0 = vk.
• Simple cycle: A cycle in which all vertices are distinct.
• Connected graph: For any two vertices a path exists connecting them.
• Connected component: equivalence class of vertices under the relation ”is reachable from”
A maximal subset C of V in which for each pair of vertices vi, vj ∈ C, vj is reachable from vi.
• Acyclic graph: a graph with no cycles
• Tree: a connected acyclic graph
• Forest: a graph consisting of at least 2 disjoint trees.
3
There are two main data structures for graphs: adjacency matrices and adjacency lists.
4
Adjacency matrix:
5
Adjacency list:
6
Breadth first search:
BFS(G=(V,E),s):
# Initialization.
for all v in V:
colour[v] <- white
d[v] <- oo
pi[v] <- NIL
initialize empty queue Q
colour[s] <- gray
d[s] <- 0
pi[s] <- NIL # not necessary because of loop above
ENQUEUE(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] <- gray
d[v] <- d[u] + 1
pi[v] <- u
ENQUEUE(Q,v)
colour[u] <- black
7