EE 232 Data Structures

& Algorithms
Session-18

Graph & BFS

Graphs, BFS, DFS 1

 Graphs
• Extremely useful tool in modeling problems
• Consist of:
– Vertices
Vertices can be
– Edges D considered “sites”
E or locations.
C
A Edges represent
F connections.
B
Vertex
Edge

Graphs, BFS, DFS 2

 Application 1
Air flight system

• Each vertex represents a city

• Each edge represents a direct flight between two cities
• A query on direct flights = a query on whether an edge exists
• A query on how to get to a location = does a path exist from A to B
• We can even associate costs to edges (weighted graphs), then
ask “what is the cheapest path from A to B”
Graphs, BFS, DFS 3
 Application 2
Wireless communication

• Represented by a weighted complete graph (every two vertices are

connected by an edge)
• Each edge represents the Euclidean distance dij between two stations
• Each station uses a certain power i to transmit messages. Given this
power i, only a few nodes can be reached (bold edges). A station
reachable by i then uses its own power to relay the message to other
stations not reachable by i.
• A typical wireless communication problem is: how to broadcast
between all stations such that they are all connected and the power
consumption is minimized.
Graphs, BFS, DFS 4
• Graph, also called network (particularly when a
weight is assgned to an edge)
• A tree is a connected graph with no loops.
• Graph algorithms might be very difficult!
– four color problem for planar graph!
• 171 only handles the simplest ones
– Traversal, BFS, DFS
– ((Minimum) spanning tree)
– Shortest paths from the source
– Connected components, topological sort

Graphs, BFS, DFS 5

 Definition
• A graph G=(V, E) consists a set of vertices, V, and a set of
edges, E.
• Each edge is a pair of (v, w), where v, w belongs to V
• If the pair is unordered, the graph is undirected; otherwise it
is directed

{a,b} {a,c}

{b,d} {c,d}

{b,e} {c,f}

{e,f}

Graphs, BFS, DFS 6

An undirected graph
 Terminology
1. If v1 and v2 are connected, they are said to be
adjacent vertices
• v1 and v2 are endpoints of the edge {v1, v2}

2. If an edge e is connected to v, then v is said to be

incident on e. Also, the edge e is said to be
incident on v.

If we are talking about directed graphs, where edges have direction. This
3.
means{v 1, v
that {v21},v2=} ≠{v
{v22,,vv }
1}1. Directed graphs are drawn with arrows (called arcs)
between edges. A B This means {A,B} only, not {B,A}

Graphs, BFS, DFS 7

 Graph Representation
• Two popular computer representations of a
graph. Both represent the vertex set and the
edge set, but in different ways.

1. Adjacency Matrix
Use a 2D matrix to represent the graph

2. Adjacency List
Use a 1D array of linked lists

Graphs, BFS, DFS 8

 Adjacency Matrix

• 2D array A[0..n-1, 0..n-1], where n is the number of vertices in the graph

• Each row and column is indexed by the vertex id
– e,g a=0, b=1, c=2, d=3, e=4
• A[i][j]=1 if there is an edge connecting vertices i and j; otherwise, A[i][j]=0
• The storage requirement is Θ(n2). It is not efficient if the graph has few edges.
An adjacency matrix is an appropriate representation if the graph is dense:
|E|=Θ(|V|2)
• We can detect in O(1) time whether two vertices are connected.

Graphs, BFS, DFS 9

 Adjacency List

• If the graph is not dense, in other words, sparse, a better solution is an

adjacency list
• The adjacency list is an array A[0..n-1] of lists, where n is the number
of vertices in the graph.
• Each array entry is indexed by the vertex id
• Each list A[i] stores the ids of the vertices adjacent to vertex i
Graphs, BFS, DFS 10
 Adjacency Matrix Example

0 0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 1 0
8
1 0 0 1 1 0 0 0 1 0 1
2 9 2 0 1 0 0 1 0 0 0 1 0
1 3 0 1 0 0 1 1 0 0 0 0
4 0 0 1 1 0 0 0 0 0 0
3 7
6 5 0 0 0 1 0 0 1 0 0 0
4 6 0 0 0 0 0 1 0 1 0 0
5
7 0 1 0 0 0 0 1 0 0 0
8 1 0 1 0 0 0 0 0 0 1
9 0 1 0 0 0 0 0 0 1 0

Graphs, BFS, DFS 11

 Adjacency List Example

0 8
0
1 2 3 7 9
8
2 1 4 8

2 3 1 4 5
9
1 4 2 3
5 3 6
3 7
6 5 7
6
4 7 1 6
5
8 0 2 9
9 1 8

Graphs, BFS, DFS 12

 Adjacency List vs. Matrix
• Adjacency List
– More compact than adjacency matrices if graph has few edges
– Requires more time to find if an edge exists

• Adjacency Matrix
– Always require n2 space
• This can waste a lot of space if the number of edges are sparse
– Can quickly find if an edge exists
– It’s a matrix, some algorithms can be solved by matrix computation!

Graphs, BFS, DFS 13

 Path between Vertices
• A path is a sequence of vertices (v0, v1, v2,… vk) such that:
– For 0 ≤ i < k, {vi, vi+1} is an edge
– For 0 ≤ i < k-1, vi ≠ vi+2
That is, the edge {vi, vi+1} ≠ {vi+1, vi+2}

Note: a path is allowed to go through the same vertex or the same edge any number of
times!

• The length of a path is the number of edges on the path

Graphs, BFS, DFS 14

 Types of paths

• A path is simple if and only if it does not contain a

vertex more than once.
• A path is a cycle if and only if v0= vk
• The beginning and end are the same vertex!

• A path contains a cycle as its sub-path if some vertex

appears twice or more

Graphs, BFS, DFS 15

Path Examples Are these paths?

Any cycles?

What is the path’s length?

1. {a,c,f,e}

2. {a,b,d,c,f,e}

3. {a, c, d, b, d, c, f, e}

4. {a,c,d,b,a}

5. {a,c,f,e,b,d,c,a}

Graphs, BFS, DFS 16

 Summary
• A graph G=(V, E) consists a set of vertices, V, and a set of
edges, E. Each edge is a pair of (v, w), where v, w belongs to V

• graph, directed and undirected graph

• vertex, node, edge, arc
• incident, adjacent
• degree, in-degree, out-degree, isolated
• path, simple path,
• path of length k, subpath
• cycle, simple cycle, acyclic
• connected, connected component
• neighbor, complete graph, planar graph

Graphs, BFS, DFS 17

 Graph Traversal
• Application example
– Given a graph representation and a vertex s in the graph
– Find all paths from s to other vertices
• Two common graph traversal algorithms
• Breadth-First Search (BFS)
– Find the shortest paths in an unweighted graph
• Depth-First Search (DFS)
– Topological sort
– Find strongly connected components

Graphs, BFS, DFS 18

• Two common graph traversal algorithms
• Breadth-First Search (BFS)  breadth first traversal of a tree
– Find the shortest paths in an unweighted graph
• Depth-First Search (DFS)  depth first traversal of a tree
– Topological sort
– Find strongly connected components

Graphs, BFS, DFS 19

 BFS and Shortest Path Problem
• Given any source vertex s, BFS visits the other vertices at increasing distances away
from s. In doing so, BFS discovers paths from s to other vertices
• What do we mean by “distance”? The number of edges on a path from s
• From ‘local’ to ‘global’, step by step.

Example
0
Consider s=vertex 1
8
2
Nodes at distance 1?
1 2 s 9 1 2, 3, 7, 9
1
1
Nodes at distance 2?
3 7 8, 6, 5, 4
1
6 2
4 Nodes at distance 3?
5
2 2 Graphs, BFS, DFS 0 20
 BFS Algorithm
Input: source vertex s
Output: all visited vertices from s

BFS (s)
FLAG: A ‘visited table’ to store the ‘visited’ information

Initialization:
s is visited
Q is empty

enqueue(Q,s)
while not-empty(Q)
v <- dequeue(Q)
W = {unvisited neighbors of v}
for each w in W
w is visited
enqueue(Q,w)
Graphs, BFS, DFS 21
BFS Example
Adjacency List Visited Table (T/F)
0 F
1 F
0
2 F
8 3 F
4 F
source 2 9 5 F

1 6 F
7 F
3 7 8 F
6 9 F
4
5
Initialize visited
table (all False)

Q= { }

Initialize Q to be empty
Graphs, BFS, DFS 22
 Adjacency List Visited Table (T/F)
0 F
1 F
0
2 T
8 3 F
4 F
source 2 9 5 F

1 6 F
7 F
3 7 8 F
6 9 F
4
5
Flag that 2 has
been visited

Q= { 2 }

Place source 2 on the queue

Graphs, BFS, DFS 23
 Adjacency List Visited Table (T/F)
0 F
1 T
0
2 T
Neighbors
8 3 F
4 T
source 2 9 5 F

1 6 F
7 F
3 7 8 T
6 9 F
4
5
Mark neighbors
as visited 1, 4, 8

Q = {2} → { 8, 1, 4 }
Dequeue 2.
Place all unvisited neighbors of 2 on the queue
Graphs, BFS, DFS 24
 Adjacency List Visited Table (T/F)
0 T
1 T
0
2 T
8 3 F
4 T
source 2 9 5 F

1 6 F
7 F
3 7 8 T
Neighbors
6 9 T
4
5
Mark new visited
Neighbors 0, 9

Q = { 8, 1, 4 } → { 1, 4, 0, 9 }

Dequeue 8.
-- Place all unvisited neighbors of 8 on the queue.
-- Notice that 2 is notGraphs,
placedBFS,on
DFS 25
the queue again, it has been visited!
 Adjacency List Visited Table (T/F)
0 T
1 T
0 Neighbors
2 T
8 3 T
4 T
source 2 9 5 F

1 6 F
7 T
3 7 8 T
6 9 T
4
5
Mark new visited
Neighbors 3, 7

Q = { 1, 4, 0, 9 } → { 4, 0, 9, 3, 7 }

Dequeue 1.
-- Place all unvisited neighbors of 1 on the queue.
-- Only nodes 3 andGraphs, BFS, DFS
7 haven’t been visited yet. 26
 Adjacency List Visited Table (T/F)
0 T
1 T
0
2 T
8 3 T
4 T
Neighbors
source 2 9 5 F

1 6 F
7 T
3 7 8 T
6 9 T
4
5

Q = { 4, 0, 9, 3, 7 } → { 0, 9, 3, 7 }

Dequeue 4.
-- 4 has no unvisited neighbors!
Graphs, BFS, DFS 27
 Adjacency List Visited Table (T/F)
0 T
Neighbors
1 T
0
2 T
8 3 T
4 T
source 2 9 5 F

1 6 F
7 T
3 7 8 T
6 9 T
4
5

Q = { 0, 9, 3, 7 } → { 9, 3, 7 }

Dequeue 0.
-- 0 has no unvisited neighbors!
Graphs, BFS, DFS 28
 Adjacency List Visited Table (T/F)
0 T
1 T
0
2 T
8 3 T
4 T
source 2 9 5 F

1 6 F
7 T
3 7 8 T
6 Neighbors 9 T
4
5

Q = { 9, 3, 7 } → { 3, 7 }

Dequeue 9.
-- 9 has no unvisited neighbors!
Graphs, BFS, DFS 29
 Adjacency List Visited Table (T/F)
0 T
1 T
0
2 T
8 3 T
Neighbors
4 T
source 2 9 5 T

1 6 F
7 T
3 7 8 T
6 9 T
4
5
Mark new visited
Vertex 5

Q = { 3, 7 } → { 7, 5 }

Dequeue 3.
-- place neighbor 5 on the queue.
Graphs, BFS, DFS 30
 Adjacency List Visited Table (T/F)
0 T
1 T
0
2 T
8 3 T
4 T
source 2 9 5 T

1 6 T
Neighbors 7 T
3 7 8 T
6 9 T
4
5
Mark new visited
Vertex 6

Q = { 7, 5 } → { 5, 6 }

Dequeue 7.
-- place neighbor 6 on the queue
Graphs, BFS, DFS 31
 Adjacency List Visited Table (T/F)
0 T
1 T
0
2 T
8 3 T
4 T
source 2 9 Neighbors 5 T

1 6 T
7 T
3 7 8 T
6 9 T
4
5

Q = { 5, 6} → { 6 }

Dequeue 5.
-- no unvisited neighbors of 5
Graphs, BFS, DFS 32
 Adjacency List Visited Table (T/F)
0 T
1 T
0
2 T
8 3 T
4 T
source 2 9 5 T
1 Neighbors 6 T
7 T
3 7
8 T
6
4 9 T
5

Q= {6}→{ }

Dequeue 6.
-- no unvisited neighbors of 6
Graphs, BFS, DFS 33
 Adjacency List Visited Table (T/F)
0 T
1 T
0
2 T
8 3 T
4 T
source 2 9 5 T

1 6 T
7 T
3 7 8 T
6 9 T
4
5

What did we discover?

Look at “visited” tables.

Q= { } STOP! Q is empty!
There exists a path from source
vertex 2 to all vertices in the graph
Graphs, BFS, DFS 34
 Time Complexity of BFS
(Using Adjacency List)
• Assume adjacency list
– n = number of vertices m = number of edges

O(n + m)

Time Complexity of BFS

(Using Adjacency Matrix)

O(n2)

Graphs, BFS, DFS 35

 Shortest Path Recording
• BFS we saw only tells us whether a path exists from
source s, to other vertices v.
– It doesn’t tell us the path!
– We need to modify the algorithm to record the path

• How can we do that?

– Note: we do not know which vertices lie on this path until
we reach v!
– Efficient solution:
• Use an additional array pred[0..n-1]
• Pred[w] = v means that vertex w was visited from v

Graphs, BFS, DFS 36

 Application of BFS
• One application concerns how to find
connected components in a graph

• If a graph has more than one connected

components, BFS builds a BFS-forest (not just
BFS-tree)!
– Each tree in the forest is a connected component.

Graphs, BFS, DFS 37

Depth-First Search

Graphs, BFS, DFS 38

 Depth-First Search (DFS)
• DFS is another popular graph search strategy
– Idea is similar to pre-order traversal (visit node,
then visit children recursively)

• DFS can provide certain information about

the graph that BFS cannot
– It can tell whether we have encountered a cycle or
not

Graphs, BFS, DFS 39

 DFS Algorithm
• DFS will continue to visit neighbors in a
recursive pattern
– Whenever we visit v from u, we recursively visit all
unvisited neighbors of v. Then we backtrack
(return) to u.

– Note: it is possible that w2 was unvisited when we

recursively visit w1, but became visited by the u
time we return from the recursive call. v w3
w1 w2
Graphs, BFS, DFS 40
DFS Algorithm

RDFS(v)

v is visited
W = {unvisited neighbors of v}
for each w in W
RDFS(w)

Graphs, BFS, DFS 41

Example
Adjacency List Visited Table (T/F)
0 0 F -

8 1 F -

2 F -

source 2 9
3 F -

4 F -
1
5 F -

3 7 6 F -

6 7 F -
4
5 8 F -

9 F -

Pred
Initialize visited
table (all False)

Initialize Pred to -1

Graphs, BFS, DFS 42

 Adjacency List Visited Table (T/F)
0 0 F -

1 F -
8 2 T -

3 F -
source 2 9 4 F -

1 5 F -

6 F -
3 7
7 F -
6
4 8 F -
5
9 F -

Pred
Mark 2 as visited

RDFS( 2 )
Now visit RDFS(8)
Graphs, BFS, DFS 43
 Adjacency List Visited Table (T/F)
0
0 F -
8 1 F -

2 T -
source 2 9 3 F -

1 4 F -

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 F -

Pred
Mark 8 as visited
Recursive RDFS( 2 )
calls RDFS(8) mark Pred[8]
2 is already visited, so visit RDFS(0)

Graphs, BFS, DFS 44

 Adjacency List Visited Table (T/F)
0
0 T 8
8 1 F -

2 T -
source 2 9 3 F -

1 4 F -

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 F -

Pred
Mark 0 as visited
Recursive RDFS( 2 )
calls RDFS(8) Mark Pred[0]
RDFS(0) -> no unvisited neighbors, return
to call RDFS(8)
Graphs, BFS, DFS 45
 Back to 8
Adjacency List Visited Table (T/F)
0
0 T 8
8 1 F -

2 T -
source 2 9 3 F -

1 4 F -

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 F -

Pred

Recursive RDFS( 2 )
calls RDFS(8)
Now visit 9 -> RDFS(9)

Graphs, BFS, DFS 46

 Adjacency List Visited Table (T/F)
0
0 T 8
8 1 F -

2 T -
source 2 9 3 F -

1 4 F -

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 T 8

Pred
Mark 9 as visited
Recursive RDFS( 2 )
calls RDFS(8) Mark Pred[9]
RDFS(9)
-> visit 1, RDFS(1)
Graphs, BFS, DFS 47
 Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 F -

1 4 F -

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 T 8

Pred
Mark 1 as visited
Recursive RDFS( 2 )
calls RDFS(8) Mark Pred[1]
RDFS(9)
RDFS(1)
visit RDFS(3)
Graphs, BFS, DFS 48
 Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 T 1

1 4 F -

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 T 8

Pred
Mark 3 as visited
Recursive RDFS( 2 )
calls RDFS(8) Mark Pred[3]
RDFS(9)
RDFS(1)
RDFS(3)
Graphs, BFS, DFS 49
visit RDFS(4)
 Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 T 1

1 4 T 3

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 T 8

Pred
RDFS( 2 ) Mark 4 as visited
RDFS(8)
Recursive
calls RDFS(9) Mark Pred[4]
RDFS(1)
RDFS(3)
RDFS(4)  STOP all of 4’s neighbors have been visited
return
Graphs, BFS, DFS back to call RDFS(3) 50
 Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 T 1

1 4 T 3

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 T 8
Back to 3
Pred
RDFS( 2 )
RDFS(8)
Recursive
calls RDFS(9)
RDFS(1)
RDFS(3)
visit 5 -> RDFS(5)
Graphs, BFS, DFS 51
 Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 T 1

1 4 T 3

5 T 3

3 7 6 F -
6 7 F -
4
5 8 T 2

9 T 8

Pred
RDFS( 2 )
RDFS(8) Mark 5 as visited
Recursive
calls RDFS(9)
RDFS(1) Mark Pred[5]
RDFS(3)
RDFS(5)
3 isGraphs,
alreadyBFS,visited,
DFS so visit 6 -> RDFS(6) 52
 Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 T 1

1 4 T 3

5 T 3

3 7 6 T 5
6 7 F -
4
5 8 T 2

9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9) Mark 6 as visited
calls RDFS(1) Mark Pred[6]
RDFS(3)
RDFS(5)
RDFS(6)
Graphs, BFS, DFS 53
visit 7 -> RDFS(7)
 Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 T 1

1 4 T 3

5 T 3

3 7 6 T 5
6 7 T 6
4
5 8 T 2

9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9) Mark 7 as visited
calls RDFS(1) Mark Pred[7]
RDFS(3)
RDFS(5)
RDFS(6)
Graphs, BFS, DFS 54
RDFS(7) -> Stop no more unvisited neighbors
 Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

6 7 T 6

4 8
5 T 2

9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9)
calls RDFS(1)
RDFS(3)
RDFS(5)
RDFS(6) -> Stop
Graphs, BFS, DFS 55
 Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

6 7 T 6

4 8
5 T 2

9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9)
calls RDFS(1)
RDFS(3)
RDFS(5) -> Stop

Graphs, BFS, DFS 56

 Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

6 7 T 6

4 8
5 T 2

9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9)
calls RDFS(1)
RDFS(3) -> Stop

Graphs, BFS, DFS 57

 Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

6 7 T 6

4 8
5 T 2

9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9)
calls RDFS(1) -> Stop

Graphs, BFS, DFS 58

 Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

6 7 T 6

4 8
5 T 2

9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9) -> Stop
calls

Graphs, BFS, DFS 59

 Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

6 7 T 6

4 8
5 T 2

9 T 8

Pred
RDFS( 2 )
RDFS(8) -> Stop
Recursive
calls

Graphs, BFS, DFS 60

Example Finished
Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

6 7 T 6

4 8
5 T 2

9 T 8

Pred
RDFS( 2 ) -> Stop

Recursive calls finished

Graphs, BFS, DFS 61

DFS Path Tracking
0 Adjacency List Visited Table (T/F)
8 0 T 8

1 T 9

source 2 9
2 T -

3 T 1
1
4 T 3

3 7 5 T 3

6 6 T 5
4
5 7 T 6

8 T 2

9 T 8

DFS find out path too Pred

Try some examples.

Path(0) ->
Path(6) ->
Path(7) ->
Graphs, BFS, DFS 62
 DFS Tree
Resulting DFS-tree.
Notice it is much “deeper”
than the BFS tree.

Captures the structure of the

recursive calls
- when we visit a neighbor w of v,
we add w as child of v
- whenever DFS returns from a
vertex v, we climb up in the tree
from v to its parent

Graphs, BFS, DFS 63

 Time Complexity of DFS
(Using adjacency list)
• We never visited a vertex more than once

• We had to examine all edges of the vertices

– We know Σvertex v degree(v) = 2m where m is the number of edges

• So, the running time of DFS is proportional to the number of

edges and number of vertices (same as BFS)
– O(n + m)

• You will also see this written as:

– O(|v|+|e|) |v| = number of vertices (n)
|e| = number of edges (m)

Graphs, BFS, DFS 64

Connected Components,
Directed Graphs,
Topological Sort

Graphs, BFS, DFS 65

 Graph Application: Connectivity

G= P
Q
N
L R
O
M D s
E
C How do we tell if two vertices
A are connected?
F A connected to F?
B
K A connected to L?
G

H
Graphs, BFS, DFS 66
 Connectivity
• A graph is connected if and only if there exists a path between
every pair of distinct vertices.

• A graph is connected if and only if there exists a simple path

between every pair of distinct vertices
– since every non-simple path contains a cycle, which can be bypassed

• How to check for connectivity?

– Run BFS or DFS (using an arbitrary vertex as the source)
– If all vertices have been visited, the graph is connected.
– Running time? O(n + m)

Graphs, BFS, DFS 67

 Trees
• Tree arises in many computer science
applications

• A graph G is a tree if and only if it is connected

and acyclic
(Acyclic means it does not contain any simple cycles)

• The following statements are equivalent

– G is a tree
– G is acyclic and has exactly n-1 edges
– G is connected and has exactly n-1 edges
Graphs, BFS, DFS 68
 Tree Example
6 3
8

0 7
2 9
1

5
4

• Is it a graph?
• Does it contain cycles? In other words, is it acyclic?
• How many vertices?
• How many edges?
Graphs, BFS, DFS 69
 Directed Graph
• A graph is directed if direction is assigned to
each edge.
• Directed edges are denoted as arcs.
– Arc is an ordered pair (u, v)

• Recall: for an undirected graph

– An edge is denoted {u,v}, which actually
corresponds to two arcs (u,v) and (v,u)

Graphs, BFS, DFS 70

 Representations
• The adjacency matrix and adjacency list can be used

Graphs, BFS, DFS 71

 Directed Graphs Usage
• Directed graphs are often used to represent order-dependent
tasks
– That is we cannot start a task before another task finishes

• We can model this task dependent constraint using arcs

• An arc (i,j) means task j cannot start until task i is finished

i j

Task j cannot start

until task i is finished

• Clearly, for the system not to hang, the graph must be acyclic
Graphs, BFS, DFS 72
 Topological Sort
• Topological sort is an algorithm for a directed acyclic graph
• Linearly order the vertices so that the linear order respects
the ordering relations implied by the arcs

6 3 For example:
8
0, 1, 2, 5, 9
0 7
1
2 9 0, 4, 5, 9
0, 6, 3, 7 ?
5
4

It may not be unique asGraphs,

they are
BFS, DFS many ‘equal’ elements!
73
 RDFS(v)
(one), Two, (three) v is visited

algorithms: W = {unvisited neighbors of v}

for each w in W
RDFS(w)

BFS (queue) DFS (stack)

s is visited s is visited
enqueue(Q,s) push(S,s)
while not-empty(Q) while not-empty(S)
v <- dequeue(Q) v <- pop(S)
W = {unvisited neighbors of v} W = {unvisited neighbors of v}
for each w in W for each w in W
w is visited w is visited
enqueue(Q,w) push(S,w)

Graphs, BFS, DFS 74

 Two applications
• For each non-visited vertex, run ‘connected
component’ (either BFS or DFS)
– For a connected component, list all vertices, find a
spanning tree (BFS tree or DFS tree)

Graphs, BFS, DFS 75