Lecture 14: Graph Traversals

CSE 373: Data Structures and Algorithms

CSE 373 22 SP – CHAMPION

1

Administrivia

​

P3 due August 3rd 11:59PM

• heaps
• 2 week assignment
• should take you 1 week to complete (START EARLY THOOO)

EC 2 Survey due Tomorrow at 11:59P

​

Final Exam Date

• take home
• Due Saturday 20th at Noon NOT Midnight
• No Late Exceptions
• like fr fr…..
• we start grading the second submissions close (literally, we start grading at noon)

Warm Up

• How would you transform the following scenario into a graph?

​

• You are creating a graph representing a brand-new social media network. Each profile has both the option to “friend” another user or to “follow” another user. When ”friend” is selected the other profile is asked for permission, and if given the two profiles will link to one another. If “follow” is selected then no permission is asked, but the recipient will not connect to the follower. Answer the following questions about the graph design:
• What are the vertices?
• What are the edges?
• Undirected or directed?
• Weighted or unweighted?

Profiles

​

Follows and friendships

​

Directed

​

Unweighted

https://tinyurl.com/Summer373L14

Introduction to Graphs

CSE 373 SP 18 - KASEY CHAMPION

4

Graph: Formal Definition

• A graph is defined by a pair of sets G = (V, E) where…

CSE 373 SP 18 - KASEY CHAMPION

5

V = { A, B, C, D, E, F, G, H }

E = { (A, B), (A, C), (A, D), (A, H),

(C, B), (B, D), (D, E), (D, F),

(F, G), (G, H)}

• V is a set of vertices
• A vertex or “node” is a data entity

• E is a set of edges
• An edge is a connection between two vertices

Graph Glossary

• Graph: a category of data structures consisting of a set of vertices and a set of edges (pairs of vertices)
• Labels: additional data on vertices, edges, or both
• Weighted: a graph where edges have numeric labels
• Directed: the order of edge pairs matters (edges are arrows) [otherwise undirected]
• Origin is first in pair, Destination is second in pair
• In-neighbors of vertex are vertices that point to it, out-neighbors are vertices it points to
• In-degree: number of edges pointing to vertex, out-degree: number of edges from vertex
• Cyclic: contains at least one cycle [otherwise acyclic]
• Simple graph: No self-loops or parallel edges
• Path: sequence of vertices reachable by edges
• Simple path: no repeated vertices
• Cycle: a path that starts and ends at the same vertex
• Self-loop: edge from vertex to itself
• Parallel edges: two edges between same vertices in directed graph, going opposite directions

( , )

a

b

c

V: Set of vertices

E: Set of edges

a

b

( , )

a

c

( , )

c

d

…

…

a

b

c

e

d

Adjacency Matrix - Runtime

CSE 373 SU 19 – ROBBIE WEBBER

In an adjacency matrix a[u][v] is 1 if there is an edge (u,v), and 0 otherwise.

Worst-case Time Complexity �(|V| = n, |E| = m):

Add Edge:

Remove Edge:

Check edge exists from (u,v):

Get outneighbors of u:

Get inneighbors of u:

​

Space Complexity:

𝚯(1)

𝚯(1)

𝚯(1)

𝚯(n)

𝚯(n)

𝚯(n * n)

Adjacency List

CSE 373 SP 20 - KASEY CHAMPION

8

Linked Lists

D

In an adjacency matrix a[u][v] is 1 if there is an edge (u,v), and 0 otherwise.

Worst-case Time Complexity �(|V| = n, |E| = m):

Add Edge:

Remove Edge:

Check edge exists from (u,v):

Get outneighbors of u:

Get inneighbors of u:

​

Space Complexity:

𝚯(1)

𝚯(deg(u) )

𝚯(deg (u) )

𝚯(deg(u) )

𝚯(n + m)

𝚯(n + m)

Adjacency List

CSE 373 SP 20 - KASEY CHAMPION

9

Hash Tables

In an adjacency matrix a[u][v] is 1 if there is an edge (u,v), and 0 otherwise.

Worst-case Time Complexity �(|V| = n, |E| = m):

Add Edge:

Remove Edge:

Check edge exists from (u,v):

Get outneighbors of u:

Get inneighbors of u:

​

Space Complexity:

𝚯(1)

𝚯(1)

𝚯(1)

𝚯(deg(u) )

𝚯(n)

𝚯(n + m)

Adapting for Undirected Graphs

destination

origin

Abstraction of the Hash Map! Buckets not shown.

A

C

B

Keys (origins)

Values (hashmaps w/ destinations as keys)

B

C

1

1

B

D

1

1

B

1

A

B

C

E

D

Adjacency Matrix

Store each edge as both directions

(makes the matrix symmetrical)

Adjacency List

Store each edge as both directions

(doubles the number of entries)

A

1

C

1

A

C

1

1

D

1

D

Tradeoffs

373: Assumed Graph Implementations

• For this class, unless otherwise stated, assume we’re using an adjacency list with hash maps.
• Also unless otherwise stated, assume all graph hash map operations are O(1). This is a pretty reasonable assumption, because for most problems we examine you know the set of vertices ahead of time and can prevent resizing.

(|V| = n, |E| = m)

Graph Traversals

CSE 373 SP 18 - KASEY CHAMPION

13

s-t Connectivity Problem

• Try to come up with an algorithm for connected(s, t)

• We can use recursion: if a neighbor of s is connected to t, that means s is also connected to t!

s-t Connectivity Problem: Proposed Solution

connected(Vertex s, Vertex t) {

if (s == t) {

return true;

} else {

for (Vertex n : s.neighbors) {

if (connected(n, t)) {

return true;

}

}

return false;

}

}

What’s wrong with this proposal?

Does 0 == 7? No; if(connected(1, 7) return true;

Does 1 == 7? No; if(connected(0, 7) return true;

Does 0 == 7?

connected(Vertex s, Vertex t) {

if (s == t) {

return true;

} else {

for (Vertex n : s.neighbors) {

if (connected(n, t)) {

return true;

}

}

return false;

}

}

s-t Connectivity Problem: Better Solution

• Solution: Mark each node as visited!

Set<Vertex> visited; // assume global

connected(Vertex s, Vertex t) {

if (s == t) {

return true;

} else {

visited.add(s);

for (Vertex n : s.neighbors) {

if (!visited.contains(n)) {

if (connected(n, t)) {

return true;

}

}

}

return false;

}

}

This general approach for crawling through a graph is going to be the basis for a LOT of algorithms!

Set<Vertex> visited; // assume global

connected(Vertex s, Vertex t) {

if (s == t) {

return true;

} else {

visited.add(s);

for (Vertex n : s.neighbors) {

if (!visited.contains(n)) {

if (connected(n, t)) {

return true;

}

}

}

return false;

}

}

Recursive Depth-First Search (DFS)

• What order does this algorithm use to visit nodes?
• Assume order of s.neighbors is arbitrary!

• It will explore one option “all the way down” before coming back to try other options
• Many possible orderings: {0, 1, 2, 5, 6, 9, 7, 8, 4, 3} or �{0, 1, 4, 3, 2, 5, 8, 6, 7, 9} both possible

VISITED

9

• We call this approach a depth-first search (DFS)

• We could also apply this code to a tree (recall: a type of graph) to do a depth-first search on it

Set<Vertex> visited; // assume global

connected(Vertex s, Vertex t) {

if (s == t) {

return true;

} else {

visited.add(s);

for (Vertex n : s.neighbors) {

if (!visited.contains(n)) {

if (connected(n, t)) {

return true;

}

}

}

return false;

}

}

• CSE 143 Review traversing a binary tree depth-first has 3 options:
• Pre-order: visit node before its children
• In-order: visit node between its children
• Post-order: visit node after its children

​

VISITED

Aside Tree Traversals

The difference between these orderings is when we “process” the root – all are DFS!

Breadth-First Search (BFS)

• Suppose we want to visit closer nodes first, instead of following one choice all the way to the end
• Just like level-order traversal of a tree, now generalized to any graph

1

2

3

4

5

6

7

8

s

VISITED

9

We call this approach a breadth-first search (BFS)

for (Vertex n : s.neighbors) {

0

1

2

3

4

This is our goal, but how do we translate into code?

• Key observation: recursive calls interrupted s.neighbors loop to immediately process children
• For BFS, instead we want to complete that loop before processing children
• Recursion isn’t the answer! Need a data structure to ”queue up” children…

• Explore “layer by layer”

BFS Implementation

bfs(Graph graph, Vertex start) {

Our extra data structure! Will keep track of “outer edge” of nodes still to explore

Let’s make this a bit more realistic and add a Graph

Kick off the algorithm by adding start to perimeter

start

Grab one element at a time from the perimeter

Look at all that element’s children

Add new ones to perimeter!

Queue<Vertex> perimeter = new Queue<>();

Set<Vertex> visited = new Set<>();

​

perimeter.add(start);

visited.add(start);

​

while (!perimeter.isEmpty()) {

Vertex from = perimeter.remove();

for (Edge edge : graph.edgesFrom(from)) {

Vertex to = edge.to();

​

if (!visited.contains(to)) {

perimeter.add(to);

visited.add(to);

}

}

}

}

BFS Implementation: In Action

PERIMETER

bfs(Graph graph, Vertex start) {

Queue<Vertex> perimeter = new Queue<>();

Set<Vertex> visited = new Set<>();

​

perimeter.add(start);

visited.add(start);

​

while (!perimeter.isEmpty()) {

Vertex from = perimeter.remove();

for (Edge edge : graph.edgesFrom(from)) {

Vertex to = edge.to();

if (!visited.contains(to)) {

perimeter.add(to);

visited.add(to);

}

}

}

}

1

2

3

4

5

6

7

8

start

VISITED

9

1

2

4

5

3

6

8

9

7

BFS Intuition: Why Does it Work?

0

1

2

3

4

PERIMETER

bfs(Graph graph, Vertex start) {

Queue<Vertex> perimeter = new Queue<>();

Set<Vertex> visited = new Set<>();

​

perimeter.add(start);

visited.add(start);

​

while (!perimeter.isEmpty()) {

Vertex from = perimeter.remove();

for (Edge edge : graph.edgesFrom(from)) {

Vertex to = edge.to();

if (!visited.contains(to)) {

perimeter.add(to);

visited.add(to);

}

}

}

}

1

2

3

4

5

6

7

8

start

VISITED

9

1

2

4

5

3

6

8

9

7

• Properties of a queue exactly what gives us this incredibly cool behavior
• As long as we explore an entire layer before moving on (and we will, with a queue) the next layer will be fully built up and waiting for us by the time we finish!
• Keep going until perimeter is empty

BFS’s Evil Twin: DFS!

bfs(Graph graph, Vertex start) {

Queue<Vertex> perimeter = new Queue<>();

Set<Vertex> visited = new Set<>();

​

perimeter.add(start);

visited.add(start);

​

while (!perimeter.isEmpty()) {

Vertex from = perimeter.remove();

for (Edge edge : graph.edgesFrom(from)) {

Vertex to = edge.to();

if (!visited.contains(to)) {

perimeter.add(to);

visited.add(to);

}

}

}

}

In DFS we can’t immediately add a node as “visited”. We need to make sure we are only marking the node when it is popped.

Change Queue for order to process neighbors to a Stack

Recap: Graph Traversals

• We’ve seen two approaches for ordering a graph traversal
• BFS and DFS are just techniques for iterating! (think: for loop over an array)
• Need to add code that actually processes something to solve a problem
• A lot of interview problems on graphs can be solved with modifications on top of BFS or DFS! Very worth being comfortable with the pseudocode ☺

BFS

(Iterative)

​

• Explore layer-by-layer: examine every node at a certain distance from start, then examine nodes that are one level farther
• Uses a queue!

​

DFS

(Iterative)

​

• Follow a “choice” all the way to the end, then come back to revisit other choices
• Uses a stack!

​

​

DFS

(Recursive)

Let’s Practice Now!

Using BFS for the s-t Connectivity Problem

• BFS is a great building block – all we have to do is check each node to see if we’ve reached t!
• Note: we’re not using any specific properties of BFS here, we just needed a traversal. DFS would also work.

stCon(Graph graph, Vertex start, Vertex t) {

Queue<Vertex> perimeter = new Queue<>();

Set<Vertex> visited = new Set<>();

​

perimeter.add(start);

visited.add(start);

​

while (!perimeter.isEmpty()) {

Vertex from = perimeter.remove();

if (from == t) { return true; }

for (Edge edge : graph.edgesFrom(from)) {

Vertex to = edge.to();

if (!visited.contains(to)) {

perimeter.add(to);

visited.add(to);

}

}

}

return false;

}

Topological Sort

Topological Sort

• A topological sort of a directed graph G is�an ordering of the nodes, where for every edge in the graph, the origin appears before the destination in the ordering

​

• Intuition: a “dependency graph”
• An edge (u, v) means u must happen before v
• A topological sort of a dependency graph gives an ordering that respects dependencies�
• Applications:
• Graduating
• Compiling multiple Java files
• Multi-job Workflows

Topological Sort:

With original edges for reference:

Input:

Problem 1: Ordering Dependencies

• Today’s (first) problem: Given a bunch of courses with prerequisites, find an order to take the courses in.

CSE 373 SP 18 - KASEY CHAMPION

29

Math 126

CSE 142

CSE 143

CSE 373

CSE 374

CSE 417

Ordering a DAG

• Does this graph have a topological ordering? If so find one.

CSE 373 19 WI - KASEY CHAMPION

30

A

B

C

E

D

If a vertex doesn’t have any edges going into it, we can add it to the ordering.

More generally, if the only incoming edges are from vertices already in the ordering, it’s safe to add.

0

1

2

1

1

A

C

B

D

E

0

1

0

0

0

Problem 1: Ordering Dependencies

• Given a directed graph G, where we have an edge from u to v if u must happen before v.
• We can only do things one at a time, can we find an order that respects dependencies?

CSE 373 19 SP - KASEY CHAMPION

31

​

Given: a directed graph G

Find: an ordering of the vertices so all edges go from left to right (all the dependency arrows are satisfied and the vertices can be processed left to right with no problems) .

Topological Sort (aka Topological Ordering)

Topological Ordering

• A course prerequisite chart and a possible topological ordering.

​

CSE 373 19 SP - KASEY CHAMPION

32

Math 126

CSE 142

CSE 143

CSE 373

CSE 374

CSE 417

Math 126

CSE 142

CSE 143

CSE 373

CSE 374

CSE 417

Can We Always Topo Sort a Graph?

• Can you topologically sort this graph?�����
• What’s the difference between this graph and our first graph?����
• A graph has a topological ordering if it is a DAG
• But a DAG can have multiple orderings

🤔 Where do I start?

Where do I end? 🤔

No 😭

Topological Sort Pseudocode

CSE 373 SP 22 - KASEY CHAMPION

toposort(Graph graph) {

Queue<Vertex> perimeter = new Queue<>();

Set<Vertex> visited = new Set<>();

Map<Vertex, Integer> indegree = countInDegree(graph);

for (Vertex v : indegree.keySet()) {

if(indegree.get(v) == 0) {

perimeter.add(v);

visited.add(v);

}

}

while (!perimeter.isEmpty()) {

Vertex from = perimeter.remove();

for (Edge edge : graph.edgesFrom(from)) {

Vertex to = edge.to();

if (!visited.contains(to)) {

int inDeg = indegree.get(to);

inDeg--;

if (inDeg == 0) {

perimeter.add(to);

visited.add(to);

}

indegree.put(to, inDeg);

}...

​

Start with BFS code (Queue to visit neighbors, List to mark visited)

Count the in-degree of each vertex

queue up the 0 in-degree nodes to visit

Loop over Queue

for each neighbor of a visited node reduce their in-degree count

for nodes that hit 0, add them to Queue

Toposort is order nodes are “visited” (could create separate List to track order, could print out as you add to Set)

Shortest Path

CSE 373 SP 22 - KASEY CHAMPION

35

The Shortest Path Problem

• This is a little harder, but still totally doable! We just need a way to keep track of how far each node is from the start.
• Sounds like a job for?

Using BFS for the Shortest Path Problem

• This is a little harder, but still totally doable! We just need a way to keep track of how far each node is from the start.
• Sounds like a job for?
• BFS!

...

Map<Vertex, Edge> edgeTo = ...

Map<Vertex, Double> distTo = ...

​

edgeTo.put(start, null);

distTo.put(start, 0.0);

​

while (!perimeter.isEmpty()) {

Vertex from = perimeter.remove();

for (Edge edge : graph.edgesFrom(from)) {

Vertex to = edge.to();

if (!visited.contains(to)) {

edgeTo.put(to, edge);

distTo.put(to, distTo.get(from) + 1);

perimeter.add(to);

visited.add(to);

}

}

}

return edgeTo;

}

Remember how we got to this point, and what layer this vertex is part of

The start required no edge to arrive at, and is on level 0

BFS for Shortest Paths: Example

• The edgeTo map stores backpointers: each vertex remembers what vertex was used to arrive at it!
• Note: this code stores visited, edgeTo, and distTo as external maps (only drawn on graph for convenience). Another implementation option: store them as fields of the nodes themselves

A

B

E

C

D

start

VISITED

PERIMETER

...

Map<Vertex, Edge> edgeTo = ...

Map<Vertex, Double> distTo = ...

​

edgeTo.put(start, null);

distTo.put(start, 0.0);

​

while (!perimeter.isEmpty()) {

Vertex from = perimeter.remove();

for (Edge edge : graph.edgesFrom(from)) {

Vertex to = edge.to();

if (!visited.contains(to)) {

edgeTo.put(to, edge);

distTo.put(to, distTo.get(from) + 1);

perimeter.add(to);

visited.add(to);

}

}

}

return edgeTo;

}

EDGETO

DISTTO

0

1

1

2

2

A

B

C

D

E

What about the Target Vertex?

• This modification on BFS didn’t mention the target vertex at all!
• Instead, it calculated the shortest path and distance from start to every other vertex
• This is called the shortest path tree
• A general concept: in this implementation, made up of distances and backpointers
• Shortest path tree has all the answers!
• Length of shortest path from A to D?
• Lookup in distTo map: 2
• What’s the shortest path from A to D?
• Build up backwards from edgeTo map: start at D, follow backpointer to B, follow backpointer to A – our shortest path is A 🡪 B 🡪 D

​

• All our shortest path algorithms will have this property
• If you only care about t, you can sometimes stop early!

​

A

B

E

C

D

start

EDGETO

DISTTO

0

1

1

2

2

Shortest Path Tree:

Recap: Graph Problems

• Just like everything is Graphs, every problem is a Graph Problem
• BFS and DFS are very useful tools to solve these! We’ll see plenty more.

EASY

MEDIUM

BFS or DFS + check if we’ve hit t

BFS + generate shortest path tree as we go

What about the Shortest Path Problem on a weighted graph?

Next Stop Weighted Shortest Paths

HARDER (FOR NOW)

• Suppose we want to find shortest path from A to C, using weight of each edge as “distance”
• Is BFS going to give us the right result here?

Dijkstra’s Algorithm

• Named after its inventor, Edsger Dijkstra (1930-2002)
• Truly one of the “founders” of computer science
• 1972 Turing Award
• This algorithm is just one of his many contributions!
• Example quote: “Computer science is no more about computers than astronomy is about telescopes”

​

• The idea: reminiscent of BFS, but adapted to handle weights
• Grow the set of nodes whose shortest distance has been computed
• Nodes not in the set will have a “best distance so far”

​

​

Dijkstra’s Algorithm: Idea

• Initialization:
• Start vertex has distance 0; all other vertices have distance ∞

​

• At each step:
• Pick closest unknown vertex v
• Add it to the “cloud” of known vertices
• Update “best-so-far” distances for vertices with edges from v

​

0

4

2

1

4??

12??

∞

∞

KNOWN

UNKNOWN

PERIMETER

start

dijkstraShortestPath(G graph, V start)

�

Dijkstra’s Pseudocode (High-Level)

Similar to “visited” in BFS, “known” is nodes that are finalized (we know their path)

Dijkstra’s algorithm is all about updating “best-so-far” in distTo if we find shorter path! Init all paths to infinite.

Order matters: always visit closest first!

Consider all vertices reachable from me: would getting there through me be a shorter path than they currently know about?

• Suppose we already visited B, distTo[D] = 7
• Now considering edge (C, D):
• oldDist = 7
• newDist = 3 + 1
• That’s better! Update distTo[D], edgeTo[D]

Set known; Map edgeTo, distTo;

initialize distTo with all nodes mapped to ∞, except start to 0

​

while (there are unknown vertices):

let u be the closest unknown vertex

known.add(u);

​

for each edge (u,v) from u with weight w:

oldDist = distTo.get(v) // previous best path to v

newDist = distTo.get(u) + w // what if we went through u?

if (newDist < oldDist):

distTo.put(v, newDist)

edgeTo.put(v, u)

Dijkstra’s Algorithm: Key Properties

• Once a vertex is marked known, its shortest path is known
• Can reconstruct path by following back-pointers (in edgeTo map)

dijkstraShortestPath(G graph, V start)

Set known; Map edgeTo, distTo;

initialize distTo with all nodes mapped to ∞, except start to 0

​

while (there are unknown vertices):

let u be the closest unknown vertex

known.add(u)

for each edge (u,v) to unknown v with weight w:

oldDist = distTo.get(v) // previous best path to v

newDist = distTo.get(u) + w // what if we went through u?

if (newDist < oldDist):

distTo.put(v, newDist)

edgeTo.put(v, u)�

• While a vertex is not known, another shorter path might be found
• We call this update relaxing the distance because it only ever shortens the current best path�

• Going through closest vertices first lets us confidently say no shorter path will be found once known
• Because not possible to find a shorter path that uses a farther vertex we’ll consider later

Dijkstra’s Algorithm: Example #1

46

Order Added to Known Set:

​

start

Dijkstra’s Algorithm: Example #1

47

Order Added to Known Set:

A

start

Dijkstra’s Algorithm: Example #1

48

Order Added to Known Set:

A, C

start

Dijkstra’s Algorithm: Example #1

49

Order Added to Known Set:

A, C, B

start

Dijkstra’s Algorithm: Example #1

50

Order Added to Known Set:

A, C, B, D

start

Dijkstra’s Algorithm: Example #1

51

Order Added to Known Set:

A, C, B, D, F

start

Dijkstra’s Algorithm: Example #1

52

Order Added to Known Set:

A, C, B, D, F, H

start

Dijkstra’s Algorithm: Example #1

53

Order Added to Known Set:

A, C, B, D, F, H, G

start

Dijkstra’s Algorithm: Example #1

54

Order Added to Known Set:

A, C, B, D, F, H, G, E

start

Dijkstra’s Algorithm: Interpreting the Results

Now that we’re done, how do we get the path from A to E?

• Follow edgeTo backpointers!
• distTo and edgeTo make up the shortest path tree

​

55

Order Added to Known Set:

A, C, B, D, F, H, G, E

start

Review: Key Features

• Once a vertex is marked known, its shortest path is known
• Can reconstruct path by following backpointers
• While a vertex is not known, another shorter path might be found!

​

• The “Order Added to Known Set” is unimportant
• A detail about how the algorithm works (client doesn’t care)
• Not used by the algorithm (implementation doesn’t care)
• It is sorted by path-distance; ties are resolved “somehow”

​

• If we only need path to a specific vertex, can stop early once that vertex is known
• Because its shortest path cannot change!
• Return a partial shortest path tree

Appendix

Graph problems

• There are lots of interesting questions we can ask about a graph:
• ▪ What is the shortest route from S to T?

▪ What is the longest without cycles?

• ▪ Are there cycles?
• ▪ Is there a tour (cycle) you can take that only uses each node (station) exactly once?
• ▪ Is there a tour (cycle) that uses each edge exactly once?

​

​

HANNAH TANG 20WI

​

Graph problems

• Some well known graph problems and their common names:
• ▪ s-t Path. Is there a path between vertices s and t?
• ▪ Connectivity. Is the graph connected?
• ▪ Biconnectivity. Is there a vertex whose removal disconnects the graph?
• ▪ Shortest s-t Path. What is the shortest path between vertices s and t?
• ▪ Cycle Detection. Does the graph contain any cycles?
• ▪ Euler Tour. Is there a cycle that uses every edge exactly once?
• ▪ Hamilton Tour. Is there a cycle that uses every vertex exactly once?
• ▪ Planarity. Can you draw the graph on paper with no crossing edges?
• ▪ Isomorphism. Are two graphs the same graph (in disguise)?
• Graph problems are among the most mathematically rich areas of CS theory!

HANNAH TANG 20WI

​

s-t path Problem

• s-t path problem
• Given source vertex s and a target vertex t, does there exist a path between s and t?

​

• Why does this problem matter? Some possible context:
• real life maps and trip planning – can we get from one location (vertex) to another location (vertex) given the current available roads (edges)
• family trees and checking ancestry – are two people (vertices) related by some common ancestor (edges for direct parent/child relationships)
• game states (Artificial Intelligence) can you win the game from the current vertex (think: current board position)? Are there moves (edges) you can take to get to the vertex that represents an already won game?

​

​

60

s-t path Problem

• s-t path problem
• Given source vertex s and a target vertex t, does there exist a path between s and t?

​

​

61

• What’s the answer for this graph on the left, and how did we get that answer as humans?
• We can see there’s edges that are visually in between s and t, and we can try out an example path and make sure that by traversing that path you can get from s to t.
• We know that doesn’t scale that well though, so now let’s try to define a more algorithmic (comprehensive) way to find these paths. The main idea is: starting from the specified s, try traversing through every single possible path possible that’s not redundant to see if it could lead to t.

traversals are really important to solving this problem / problems in general, so slight detour to talk about them, we’ll come back to this though

Graph traversals: DFS

• Depth First Search - a traversal on graphs (or on trees since those are also graphs) where you traverse “deep nodes” before all the shallow ones
• High-level DFS: you go as far as you can down one path till you hit a dead end (no neighbors are still undiscovered or you have no neighbors). Once you hit a dead end, you backtrack / undo until you find some options/edges that you haven’t actually tried yet.

Kind of like wandering a maze – if you get stuck at a dead end (since you physically have to go and try it out to know it’s a dead end), trace your steps backwards towards your last decision and when you get back there, choose a different option than you did before.

one valid DFS traversal: 10, 5, 3, 2, 4, 8, 7,6, 9, 15, 12, 14, 18

Graph traversals: BFS

• Breadth First Search - a traversal on graphs (or on trees since those are also graphs) where you traverse level by level. So in this one we’ll get to all the shallow nodes before any “deep nodes”.
• Intuitive ways to think about BFS:
• - opposite way of traversing compared to DFS
• - a sound wave spreading from a starting point, going outwards in all directions possible.
• - mold on a piece of food spreading outwards so that it eventually covers the whole surface

​

one valid BFS traversal: 10, 5, 15, 3, 8, 12, 18, 2, 4, 7, 9, 14, 6

Graph traversals: BFS and DFS on more graphs

• Take 2 minutes and try to come up with two possible traversal orderings starting with the 0 node:
• a BFS ordering (ordering within each layer doesn’t matter / any ordering is valid)
• a DFS ordering (ordering which path you choose next at any point doesn’t matter / any is valid as long as you haven’t explored it before)
• @ordering choices will be more stable when we have code in front of us, but not the focus / point of the traversals so don’t worry about it

In DFS, you go as far as you can down one path till you hit a dead end (no neighbors are still undiscovered or you have no neighbors). Once you hit a dead end, you backtrack / undo until you find some options/edges that you haven’t actually tried yet.

​

In BFS, you traverse level by level

Graph traversals: BFS and DFS on more graphs

• Take a minute and try to come up with two possible traversal orderings starting with the 0 node:
• a BFS ordering (ordering within each layer doesn’t really matter / any ordering is valid)
• 0, [1, 2, 3, 4, 5, 6, 7], [8, 9, 10, 12, 13, 14, 15, 16, 17], [11, 18], [19]
• a DFS ordering (ordering which path you choose next at any point doesn’t matter / any is valid as long as you haven’t explored it before)
• 0, 2, 9, 3, 10, 11, 19, 4, 12, 18, �5, 13, 14, 6, 15, 7, 16, 1,17, 8

​

In DFS, you go as far as you can down one path till you hit a dead end (no neighbors are still undiscovered or you have no neighbors). Once you hit a dead end, you backtrack / undo until you find some options/edges that you haven’t actually tried yet.

​

In BFS, you traverse level by level

Graph traversals: BFS and DFS on more graphs

https://visualgo.net/en/dfsbfs

​

• click on draw graph to create your own graphs and run BFS/DFS on them!
• check out visualgo.net for more really cool interactive visualizations
• or do your own googling – there are a lot of cool visualizations out there ☺!

BFS pseudocode (some details not Java specific)

• bfs(Graph graph, Vertex start) {
• // stores the remaining vertices to visit in the BFS
• Queue<Vertex> perimeter = new Queue<>();
• // stores the set of discovered vertices so we don't revisit them multiple times
• Set<Vertex> discovered = new Set<>();
• // kicking off our starting point by adding it to the perimeter
• perimeter.add(start);
• discovered.add(start);

​

• while (!perimeter.isEmpty()) {
• Vertex from = perimeter.remove();
• for (E edge : graph.outgoingEdgesFrom(from)) {
• Vertex to = edge.to();
• if (!discovered.contains(to)) {
• perimeter.add(to);
• discovered.add(to)
• }
• }
• }

BFS pseudocode (some details not Java specific)

• //. . . this is the main loop/code for BFS
• while (!perimeter.isEmpty()) {
• Vertex from = perimeter.remove();
• for (E edge : graph.outgoingEdgesFrom(from)) {
• Vertex to = edge.to();
• if (!discovered.contains(to)) {
• perimeter.add(to);
• discovered.add(to)
• }
• }
• }

Perimeter queue:

Discovered set:

Expected levels starting the BFS from 0:

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

DFS pseudocode (some details not Java specific)

• dfs(Graph graph, Vertex start) {
• // stores the remaining vertices to visit in the DFS
• Stack<Vertex> perimeter = new Stack<>(); //the only change you need to make to do DFS!
• // stores the set of discovered vertices so we don't revisit them multiple times
• Set<Vertex> discovered = new Set<>();
• // kicking off our starting point by adding it to the perimeter
• perimeter.add(start);
• discovered.add(start);

​

• while (!perimeter.isEmpty()) {
• Vertex from = perimeter.remove();
• for (E edge : graph.outgoingEdgesFrom(from)) {
• Vertex to = edge.to();
• if (!discovered.contains(to)) {
• perimeter.add(to);
• discovered.add(to)
• }
• }
• }

Modifying BFS and DFS

BFS and DFS are like the for loops over arrays for graphs. They’re super fundamental to so many ideas, but when they’re by themselves they don’t do anything. Consider the following code:

for (int i = 0; i < n; i++) {

int x = arr[i];

}

​

​

​

We actually need to do something with the data for it to be useful!

A lot of times to solve basic graph problems (which show up in technical interviews at this level), and often the answer is that you just need to describe / implement BFS/DFS with a small modification for your specific problem.

Now back to the s-t path problem…

​

• while (!perimeter.isEmpty()) {
• Vertex from = perimeter.remove();
• for (E edge : graph.outgoingEdgesFrom(from)) {
• Vertex to = edge.to();
• if (!discovered.contains(to)) {
• perimeter.add(to, newDist);
• discovered.add(to)
• }
• }
• }

Modifying BFS for the s-t path problem

• //. . . this is the main loop/code for BFS
• while (!perimeter.isEmpty()) {
• Vertex from = perimeter.remove();
• for (E edge : graph.outgoingEdgesFrom(from)) {
• Vertex to = edge.to();
• if (!discovered.contains(to)) {
• perimeter.add(to);
• discovered.add(to)
• }
• }
• }

• // with modifications to return true if
• // there is a path where s can reach t
• while (!perimeter.isEmpty()) {
• Vertex from = perimeter.remove();
• if (from == t) {
• return true;
• }
• for (E edge : graph.outgoingEdgesFrom(from)) {
• Vertex to = edge.to();
• if (!discovered.contains(to)) {
• perimeter.add(to);
• discovered.add(to)
• }
• }
• }
• return false;

• Small note: for this s-t problem, we didn’t really need the power of BFS in particular, just some way of looping through the graph starting at a particular point and seeing everything it was connected to. So we could have just as easily used DFS.

​

• There are plenty of unique applications of both, however, and we’ll cover some of them in this course – for a more comprehensive list, feel free to google or check out resources like:
• - https://www.geeksforgeeks.org/applications-of-breadth-first-traversal/
• - https://www.geeksforgeeks.org/applications-of-depth-first-search/

Questions / clarifications on anything?

we covered:

• s-t path problem
• BFS/DFS visually + high-level
• BFS/DFS pseudocode
• modifying BFS/DFS to solve s-t path problem