PowerPoint Presentation
Graph Data Structures
Breadth First Search
Graphs
A graph is a pair G = (V, E):
directed graph: E is a set of ordered pairs of vertices (
undirected graph: E is a set of unordered pairs of vertices ( (u, v) is the same as (v, u) )
Nodes
Vertices
Edges
Arcs
Examples
z
a
z
b
z
c
z
e
z
d
z
g
z
f
Directed
V = {a, b, c, d, e, f, g}
E = {
Undirected
z
a
z
d
z
e
z
f
z
b
z
h
z
c
z
g
V = {a, b, c, d, e, f, g, h}
E = {(a,b), (b,c), (c,d), (d,e)
(a,e), (c,e), (f,g), (g,h), (h,f)}
Adjacency List
z
a
z
b
z
c
z
e
z
d
z
g
z
f
a
b
c
d
e
f
g
b
c
e
d
e
c
g
f
z
a
z
d
z
e
z
b
z
c
a
b
c
d
e
b
e
a
c
b
d
e
e
c
a
c
d
Time to check if (u,v) is in E:
O(# neighbors of u)
Space Used:
O(|V| + |E|)
Each edge contributes to O(1)
linked list entries.
Adjacency Matrix
z
a
z
b
z
c
z
e
z
d
z
g
z
f
z
a
z
d
z
e
z
b
z
c
Time to check if (u,v) is in E: O(1)
Space Used: O(|V|2)
a b c d e f g
a 0 1 0 0 0 0 0
b 0 0 1 0 1 0 0
c 0 0 0 1 0 0 0
d 0 0 0 0 1 0 0
e 0 0 1 0 0 0 0
f 0 0 0 0 0 0 1
g 0 0 0 0 0 1 0
a b c d e
a 0 1 0 0 1
b 1 0 1 0 0
c 0 1 0 1 1
d 0 0 1 0 1
e 1 0 1 1 0
s
b
c
d
e
f
g
node parent d
s Null 0
b Null ∞
c Null ∞
d Null ∞
e Null ∞
f Null ∞
g Null ∞
Q = (s)
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b Null ∞
c Null ∞
d Null ∞
e Null ∞
f Null ∞
g Null ∞
Q = ()
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c Null ∞
d Null ∞
e Null ∞
f Null ∞
g Null ∞
Q = (b)
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c Null ∞
d Null ∞
e Null ∞
f Null ∞
g Null ∞
Q = ()
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c Null ∞
d Null ∞
e Null ∞
f Null ∞
g Null ∞
Q = ()
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d Null ∞
e Null ∞
f Null ∞
g Null ∞
Q = (c)
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d Null ∞
e b 2
f Null ∞
g Null ∞
Q = (c, e)
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d Null ∞
e b 2
f Null ∞
g Null ∞
Q = (e)
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d Null ∞
e b 2
f Null ∞
g Null ∞
Q = (e)
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d c 3
e b 2
f Null ∞
g Null ∞
Q = (e, d)
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d c 3
e b 2
f Null ∞
g Null ∞
Q = (d)
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d c 3
e b 2
f Null ∞
g Null ∞
Q = (d)
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d c 3
e b 2
f Null ∞
g Null ∞
Q = (d)
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d c 3
e b 2
f Null ∞
g Null ∞
Q = ()
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d c 3
e b 2
f Null ∞
g Null ∞
Q = ()
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d c 3
e b 2
f Null ∞
g Null ∞
Q = ()
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d c 3
e b 2
f Null ∞
g d 4
Q = (g)
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d c 3
e b 2
f Null ∞
g d 4
Q = ()
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d c 3
e b 2
f g 5
g d 4
Q = (f)
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d c 3
e b 2
f g 5
g d 4
Q = ()
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d c 3
e b 2
f g 5
g d 4
Q = ()
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
s
b
c
d
e
f
g
node parent d
s Null 0
b s 1
c b 2
d c 3
e b 2
f g 5
g d 4
Q = ()
s
b
c
d
e
f
g
b
s, c, e
b, d
c, e, g
b, d
g
f
/docProps/thumbnail.jpeg