DFS, BFS & Shortest Paths
Exam Prep 10
CS 61B // Fall 2020
Announcements
Exam Prep 10
CS 61B // Fall 2020
Content Review
CS 61B // Fall 2020
Graphs
Graphs are structures that contain nodes and edges.
Graphs can be directed or undirected.
A
B
C
D
E
F
A
B
C
D
E
F
CS 61B // Fall 2020
Graph Representations
Adjacency lists list out all the nodes connected to each node in our graph:
A
B
C
D
E
F
A | B → C |
B | E |
C | F |
D | B |
E | |
F | D |
CS 61B // Fall 2020
Graph Representations
Adjacency matrices are true if there is a line going from node A to B and false otherwise.
A
B
C
D
E
F
| A | B | C | D | E | F |
A | 0 | 1 | 1 | 0 | 0 | 0 |
B | 0 | 0 | 0 | 0 | 1 | 0 |
C | 0 | 0 | 0 | 0 | 0 | 1 |
D | 0 | 1 | 0 | 0 | 0 | 0 |
E | 0 | 0 | 0 | 0 | 0 | 0 |
F | 0 | 0 | 0 | 1 | 0 | 0 |
CS 61B // Fall 2020
Graph Searches
Breadth First Search goes in order of how far each node is from the starting node. Programatically this is done using a queue.
Depth First Search goes all the way down one path before exploring others. Programatically this is done using a stack.
A
B
C
D
E
F
CS 61B // Fall 2020
Dijkstra’s Algorithm
Dijkstra’s algorithm is a method of finding the shortest path from one node to every other node in the graph. You use a priority queue that sorts points based off of their distance to the root node.
Steps:
A
B
C
D
E
F
7
1
2
1
1
2
CS 61B // Fall 2020
A*
A* is a method of finding the shortest path from one node to a specific other node in the graph. It operates very similarly to Dijkstra’s except for the fact that we use a (given) heuristic to which path is the best to our goal point.
Steps:
distance will be the sum of the distance up to that child node and
our guess of how far away the goal node is (our heuristic).
The only constraints on our heuristic is that it must be less than or equal to the true distance to the goal node.
A
B
C
D
E
F
7
1
2
1
1
2
(1)
(3)
(3)
(4)
(6)
CS 61B // Fall 2020
Worksheet
CS 61B // Fall 2020
1ABC DFS, BFS, Dijkstra’s, A*
A
B
E
F
G
C
D
H
3
1
7
4
2
4
1
4
5
1
2
CS 61B // Fall 2020
1D DFS, BFS, Dijkstra’s, A*
A
B
E
F
G
C
D
H
3
1
7
4
2
4
1
4
5
1
2
CS 61B // Fall 2020
1E DFS, BFS, Dijkstra’s, A*
A
B
E
F
G
C
D
H
3
1
7
4
2
4
1
4
5
1
2
(1)
(4)
(7)
(5)
(9)
(10)
(3)
CS 61B // Fall 2020
2 Graph Conceptuals
CS 61B // Fall 2020
3 Cycle Detection
CS 61B // Fall 2020