1 of 15

DFS, BFS & Shortest Paths

Exam Prep 10

CS 61B // Fall 2020

2 of 15

Announcements

Exam Prep 10

  • Midterm 2 is on Wednesday 7pm
  • HW3 due tonight
  • No Lab this week

CS 61B // Fall 2020

3 of 15

Content Review

CS 61B // Fall 2020

4 of 15

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

5 of 15

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

6 of 15

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

7 of 15

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

8 of 15

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:

  1. Pop node from the top of the queue - this is the current node.
  2. Add/update distances of all of the children of the current node.
  3. Re-sort the priority queue.
  4. Finalize the distance to the current node from the root.
  5. Repeat.

A

B

C

D

E

F

7

1

2

1

1

2

CS 61B // Fall 2020

9 of 15

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:

  • Pop node from the top of the queue - this is the current node.
  • Add/update distances of all of the children of the current node. This

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).

  • Re-sort the priority queue.
  • Check if we’ve hit the goal node (if so we stop).
  • Repeat.

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

10 of 15

Worksheet

CS 61B // Fall 2020

11 of 15

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

12 of 15

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

13 of 15

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

14 of 15

2 Graph Conceptuals

CS 61B // Fall 2020

15 of 15

3 Cycle Detection

CS 61B // Fall 2020