Graph Representations
Adjacency lists:
- Array $Adj$ of $|V|$ linked lists
- for each vertex $u∈V$, $Adj[u]$ stores $u$’s neighbors, i.e., ${v∈V|(u,v)∈E}$
Implicit Graphs:
- $Adj(u)$ is a function — compute local structure on the fly
Object-oriented Variations:
- object for each vertex $u$
- u.neighbors = list of neighbors i.e. $Adj[u]$
Incidence Lists:
- can also make edges objects
- u.edges = list of (outgoing) edges from u.
- advantage: store edge data without hashing
Graph traversal means visiting every vertex and edge exactly once in a well-defined order. BFS is the most commonly used approach.
Breadth-First Search
Explore graph level by level from $s$ (that is to say, you will not move to another layer until you visit all the nodes of the current layer):
- level 0 = {s}
- level i = vertices reachable by path of i edges but not fewer
- build level $i > 0$ from level $i − 1$ by trying all outgoing edges, but ignoring vertices from previous levels
Breadth-First-Search Algorithm1
2
3
4
5
6
7
8
9
10
11
12
13
14
15BFS (V,Adj,s):
level = {s: 0}
parent = {s: None}
i = 1
frontier = [s] # previous level, i − 1
while frontier:
next = [ ] # next level, i
for u in frontier:
for v in Adj[u]:
if v not in level: # not yet seen
level[v] = i # = level[u] + 1
parent[v] = u
next.append(v)
frontier = next
i + =1
Example:
Analysis:
- vertex $V$ enters next (& then frontier) only once (because level[v] then set)
- ⇒ $Adj[v]$ looped through only once
- ⇒ $O(E)$ time
- $O(V + E)$ (“LINEAR TIME”) to also list vertices unreachable from v (those still not assigned level)
Shortest Paths:
- for every vertex v, fewest edges to get from s to v is:
- level[v], if v assigned level
- $∞$, if no path
- parent pointers form shortest-path tree = union of such a shortest path for each v
- ⇒ to find shortest path, take v, parent[v], parent[parent[v]], etc., until s (or None)
Reference:
https://www.hackerearth.com/zh/practice/algorithms/graphs/breadth-first-search/tutorial/