CS计算机代考程序代写 data structure algorithm COMP2521

COMP2521
Data Structures & Algorithms

Week 5.3
Graph Traversal

 

1

In this lecture

Why?

Graphs aren’t very useful if all we’re doing is storing things
in them. We need to effectively search and traverse them
to gather information

What?

Traverse and searching a graph
Breadth-first-search
Depth-first-search

 

2

Why do we use graphs?

Allow us to ask these kinds of questions:

Can we remove an edge and keep the graph connected?
Is a vertex reachable starting from somewhere else?
What is the quickest way to get from one node to another?
Is there a tree that links all vertices?

3 . 1

Why do we use graphs?

There are 3 topics we will focus on relating to traversal. All rely on
very similar algorithms and processes, they’re just used to different

extents.

Traverse for Item Searching

Using an algorithm to move
between nodes to look for a value

Traverse for Path Finding
Using an algorithm to look for a
value, but keep track of how to

get there

Traverse Fully
Like path finding, except we’re
just exploring the entire graph,
not looking for specific value

3 . 2

Graph Traversal (/Search)

Graph Traversal is the systematic exploration of a graph via the
edges. The focus is often between exploring paths between a starting

vertex and a finish vertex.
 

Solutions can be iterative or recursive
Sometimes need to store the path we explore as we explore it,
and sometimes store a list of nodes we’ve visited

 

4 . 1

Graph Traversal
There are two primary methods we’ll be using to traverse a graph:

Depth-first search (go deep)
Iterative & recursive solutions

Breadth-first search (go wide)
Iterative solutions

4 . 2

Graph Traversal
Both approaches ignore some edges by remembering previously

visited vertices (this also prevents cycles)
 

4 . 3

Breadth First Search

Traversing with BFS is about start at a node, and expanding out
equally from there. You visit all the neighbours of the current vertex,

then you visit all the neighbours of those neighbours. Etc.
 

5 . 1

BFS – Example Path Find

5 . 2

BFS – Algorithm

A very tricky algorithm to describe recursively. Typically we do it
iteratively

findPathBFS(G,src,dest):
visited[] // store previously visited node
for all vertices v∈G:
visited[v]=-1
found = false
visited[src] = src
enqueue src into queue Q
while not found ∧ Q is not empty:
dequeue v from Q
if v = dest:
found = true
else:
for each (v,w) ∈ edges(G) with visited[w] = -1:
visited[w] = v
enqueue w into Q
end while
if found:
display path in dest..src order

1
2
3
4
5
6
7
8
9

10
11
12
13
14
15
16
17
18

5 . 3

BFS – Cost Analysis

For an adjacency list representation:
Each vertex visited at most once. Cost => O(V)

Visit all edges incident on visited vertices. Cost => O(E)
 

BFS: O(V + E) (adjacency list)
 

5 . 4

Depth First Search

Traversing with DFS is about going as deep as possible until you
reach a dead end, and then unwinding back through nodes until

there is another branch to take.

6 . 1

DFS – Algorithm

An iterative DFS is identical to an iterative BFS, except we use a stack
instead of a queue.

findPathDFS(G,src,dest):
visited[] // store previously visited node
for all vertices v ∈ G:
visited[v] = -1
found = false
visited[src] = src
push src into stack S
while not found ∧ Q is not empty:
pop stack from S
if v = dest:
found = true
else:
for each (v,w) ∈ edges(G) with visited[w] = -1:
visited[w] = v
push w into stack S
end while
if found:
display path in dest..src order

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

6 . 2

DFS – Recursive

Recursive solutions are a bit more elegant.
 

Full Traversal Path Checking
visited = {}

depthFirst(G,v):
visited = visited ∪ {v}
for all (v,w) ∈ edges(G):
if w ∉ visited:
depthFirst(G,w)

1
2
3
4
5
6
7

visited = {}

hasPath(G,src,dest):
return dfsPathCheck(G,src,dest)

dfsPathCheck(G,v,dest):
visited = visited ∪ {v}
for all (v,w) ∈ edges(G):
if w = dest: // found edge to dest
return true
else if w ∉ visited:
if dfsPathCheck(G,w,dest):
return true // found path via w to dest
return false // no path from v to dest

1
2
3
4
5
6
7
8
9

10
11
12
13
14

Path Finding
visited[] // store previously visited node

findPath(G,src,dest):
for all vertices v ∈ G:
visited[v] = -1
visited[src] = src // starting node of the path
if dfsPathCheck(G,src,dest):
// show path in dest..src order
v = dest
while v ≠ src:
print v”-”
v = visited[v]
print src

dfsPathCheck(G,v,dest):
for all (v,w) ∈ edges(G):
if visited[w] = -1:
visited[w] = v
if w = dest: // found edge from v to dest
return true
else if dfsPathCheck(G,w,dest):
return true // found path via w to dest
return false // no path from v to dest

1
2
3
4
5
6
7
8
9

10
11
12
13
14
15
16
17
18
19
20
21
22
23

6 . 3

DFS – Recursive Path Find

6 . 4

DFS – Cost Analysis

For an adjacency list representation:
Each vertex visited at most once. Cost => O(V)

Visit all edges incident on visited vertices. Cost => O(E)
 

BFS: O(V + E) (adjacency list)
 

6 . 5

DFS – Other

DFS does not guarantee optimal solution
 

Example below clearly does not find shortest path

6 . 6

Full Traversal

A full traversal of a tree is essentially using BFS or DFS to find a
spanning tree

 

7

Feedback

8