CSE 373 Section 6

Graphs

Grab a handout!

If time - leetcode

(keep computer handy)

Agenda

• Announcements
• Graph terminology / types / applications
• BFS / DFS
• Order of traversal
• Brief Dijkstra’s
• Algorithm Application Summary
• S-T connectivity problem

Announcements

• P3 - Heap
• Get it out of the way :)
• Due Wednesday, August 3, 23:59
• Ex4 - BFS, DFS, Dijkstra’s
• Due Friday, July 29, 23:59
• Ex5 - MST, Disjoint Sets
• Out Friday, July 29, 23:59
• Exercises:
• Occam’s Razor
• If an ADT already has methods that support all functionality, choose that ADT
• Pls pls pls read carefully!
• Y’all are doing great!

MicroTeach: Graph Intro

Graphs

Graph: A set of nodes (also called vertices) connected pairwise by edges.�

Graph Terminology

• Graph:
• Set of vertices, a.k.a. nodes.
• Set of edges: Pairs of vertices.
• Vertices with an edge between are adjacent.
• The degree of a vertex is the number of edges directly connected to it.
• A path is a sequence of vertices connected by edges.
• A cycle is a path whose first and last vertices are the same.
• A graph with a cycle is ‘cyclic’.
• A directed graph goes one way.
• A connection means there is a path between two vertices

Some Graph Types

a

b

d

c

a

b

d

c

e

a

b

d

c

a

b

d

c

Acyclic:

Cyclic:

Directed

Undirected

Graph Applications

• Physical Maps
• Airline maps
• Traffic
• Relationships
• Social media graphs
• Code bases
• Influence
• Biology
• Related topics
• Web Page Ranking
• Wikipedia
• Many more...

​

Graph Applications

• Physical Maps
• Airline maps
• Traffic
• Relationships
• Social media graphs
• Code bases
• Influence
• Biology
• Related topics
• Web Page Ranking
• Wikipedia
• Many more...

​

Everything is a graph → everything can be solved with a graph algorithm

Graph Representations

• Adjacency List
• List of all vertices
• Within each list, list of vertices that the original vertex connects TO (not from)
• Adjacency Matrix
• 2D array
• Vertices in rows and columns
• “0” if no edge, “1” if edge
• Symmetrical on diagonal if undirected
• Column / row whichever first

a

b

d

c

e

Questions?

MicroTeach: DFS/BFS

BFS Pseudocode (simplified)

Queue q

add Vertex start to q

mark start as discovered

while q is not empty {

Vertex from = q.remove()

for each edge {from,d} {

if d is not discovered {

add d to q

mark d as discovered

}

}

}

​

Why a queue?

BFS Pseudocode (simplified)

Queue q

add Vertex start to q

mark start as discovered

while q is not empty {

Vertex from = q.remove()

for each edge {from,d} {

if d is not discovered {

add d to q

mark d as discovered

}

}

}

​

Why a queue? FIFO; next in line is in the closest undiscovered layer to vertex

BFS Pseudocode

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

}

}

}

}

DFS Pseudocode (simplified)

Stack s

add Vertex start to s

while s is not empty {

Vertex from = s.remove()

if from is not discovered {

for each edge {from,d} {

add d to s

}

mark from as discovered

}

}

​

* Fixes the “bug” Sonia mentioned in Lecture 14! Can you spot the change? :)

Why a stack?

DFS Pseudocode (simplified)

Stack s

add Vertex start to s

while s is not empty {

Vertex from = s.remove()

if from is not discovered {

for each edge {from,d} {

add d to s

}

mark from as discovered

}

}

​

* Fixes the “bug” Sonia mentioned in Lecture 14! Can you spot the change? :)

Why a stack? LIFO: next in line is the deepest next vertex

DFS Pseudocode

dfs(Graph graph, Vertex start) {

// stores the remaining vertices to visit in the DFS

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

​

// 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);

​

while (!perimeter.isEmpty()) {

Vertex from = perimeter.remove();

if (!discovered.contains(from)) {

for (E edge : graph.outgoingEdgesFrom(from)) {

Vertex to = edge.to();

perimeter.add(to);

}

discovered.add(from);

}

}

}

* Fixes the “bug” Sonia mentioned in Lecture 14! Can you spot the change? :)

Problem 3:

Simulating BFS

7 min

Simulating BFS

Y

S

Z

T

X

Queue of Vertices to Explore:

Begin with the start vertex in the queue!

Simulating BFS

Y

S

Z

T

X

Queue of Vertices to Explore:

​

Remove S to explore!

Simulating BFS

Y

S

Z

T

X

Queue of Vertices to Explore:

​

Add neighbors of S in to queue to be explored

(order depends on the problem - sometimes arbitrary, sometimes numerical/alphabetical)

Simulating BFS

Y

S

Z

T

X

Queue of Vertices to Explore:

​

Remove T to explore!

Simulating BFS

Y

S

Z

T

X

Queue of Vertices to Explore:

​

Add neighbors of T in to queue to be explored

Simulating BFS

Y

S

Z

T

X

Queue of Vertices to Explore:

​

Remove Y to explore!

Simulating BFS

Y

S

Z

T

X

(Nothing happens!)

Queue of Vertices to Explore:

​

Simulating BFS

Y

S

Z

T

X

Queue of Vertices to Explore:

​

Remove X to explore!

Simulating BFS

Y

S

Z

T

X

Queue of Vertices to Explore:

​

(Nothing happens!)

Simulating BFS

Y

S

Z

T

X

Queue of Vertices to Explore:

​

Pop Z to explore!

Simulating BFS

Y

S

Z

T

X

(Nothing happens!)

Queue of Vertices to Explore:

​

How do we interpret the final table?

Simulating BFS

To check if there exists a path from a given start node to given target…

​

​

​

​

​

​

To find the resulting shortest paths tree (SPT)…

​

​

​

​

​

​

​

• For each vertex, backtrace from its predecessors until you reach the source vertex
• This is the same as getting the shortest path from the source to each vertex
• By combining the shortest paths to each vertex in the graph, you will get the SPT for the graph

​

• Locate the target vertex in the table
• Backtrace through its predecessors
• If the start vertex is one of its predecessors, then there exists a path between them, otherwise there does not

Simulating BFS

Y

S

Z

T

X

Resulting SPT

Questions?

Problem 2:

Graph Traversal

Start at vertex “A”: only DFS

7 min

D

H

A

F

E

C

B

G

If we traverse this using breadth-first search, what are the two possible orderings of the nodes we visit?

​

What if we use depth-first search?

Questions?

Dijkstra’s

• Dye-k-stra’s
• Similar to BFS - add distance column because weighted graph
• Update as we go; recommend crossing the previous out
• Instead of not doing anything, check weights
• Distances are <= until “processed”
• Once processed, lock it in
• Guaranteed shortest path
• Think about why!
• More - hard coding,

why this works

next week!

Questions?

Summary of Applications so Far

• Prerequisite or dependency problems
• Use Topological sort (checks in-degrees and in-edges, ordering)
• Cannot be cyclic
• S-T connectivity problems
• BFS, DFS
• Boolean
• Shortest paths problem - unweighted
• BFS - break ties??
• Use maps to track backpointers
• SPT (S to every other vertex)
• Shortest paths problem - weighted
• Dijkstra’s - update distances
• Use maps to track backpointers
• SPT (S to every other vertex)

Leetcode Problem: Find if Path Exists

(https://leetcode.com/problems/find-if-path-exists-in-graph/)

Leetcode!

​

Before coding the solution…

​

1. Read the problem in its entirety
2. Ensure you understand any edge cases
3. Think about the different possible solutions
1. You will most likely start thinking about the brute force solution first, and that’s okay!
2. Consider runtime (and memory) complexity
1. Most likely in terms of Big-O
4. Write pseudocode
5. Code out solution
6. Test Solution
7. Optimize -> repeat steps (3-8)

Explorations

• What kind of problem is this???
• ​
• Thus, how can we solve it???
• ​
• How do we know to stop???
• ​

Explorations

• What kind of problem is this???
• S-T connectivity!
• Thus, how can we solve it???
• BFS or DFS, both methods are possible!
• How do we know to stop???
• Traverse using edges
• Stop when we find T

Explorations

• What kind of problem is this???
• S-T connectivity!
• Thus, how can we solve it???
• BFS or DFS, both methods are possible!
• How do we know to stop???
• Traverse using edges
• Stop when we find T
• Let’s try it with BFS
• Avoids recursive algorithm - less runtime

Solution

• BFS; follow the pseudocode and stop when we find the goal!

public boolean validPath(int n, int[][] edges, int source, int destination) {

// source = starting vertex

// destination = terminating vertex

Queue<Integer> perimeter = new LinkedList<>();

Set<Integer> visited = new TreeSet<>();

perimeter.add(source);

visited.add(source);

while (!perimeter.isEmpty()) {

int from = perimeter.remove();

// "base case" of no recursion

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

// check what edges exist around vertex

List<Integer> connectedTo = findEdges(edges, from);

for (int vertex : connectedTo) {

if (!visited.contains(vertex)) {

perimeter.add(vertex);

visited.add(vertex);

}

}

}

return false;

}

// manually implement finding the outgoing edges

private List<Integer> findEdges(int[][] edges, int from) {

List<Integer> ret = new ArrayList<Integer>();

for (int[] edge : edges) {

if (edge[0] == from) {

ret.add(edge[1]);

}

if (edge[1] == from) {

ret.add(edge[0]);

}

}

return ret;

}

​

​

MicroTeach: Dijkstra’s

Dijkstra’s Algorithm: single-pair-shortest-path

• Pathfinding on a weighted graph!�
• Main idea: find shortest path/shortest distance from start node in graph to every other node.�
• Uses a Priority Queue, where priorities of nodes are their distance from the start node�
• We pull the closest node off the queue each iteration, and update the distances for its adjacent nodes. Then repeat.

​

Dijkstra’s Pseudocode

Dijkstra(Graph G, Vertex source)

initialize distances to ∞

mark all vertices unprocessed

mark source as distance 0

while(there are unprocessed vertices){

let u be the closest unprocessed vertex

for each(edge (u,v) leaving u){

if(u.dist+weight(u,v) < v.dist){

v.dist = u.dist+weight(u,v)

v.predecessor = u

}

}

mark u as processed

}

Q: How to get the shortest path?

A: After running Dijkstra, start from the target node and follow the backpointers!�

GetPath(Graph G, Vertex source, Vertex target)

// We never reached the target :(

if (target.dist == INFINITY)

return null

path = []

curNode = target

path.add_back(target)

​

while(curNode != source)

curNode = curNode.predecessor

path.add_back(curNode)�

// If we want the path to go from source -> goal.

return path.reversed()

​

Problem 4A: Dijkstra

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

(Nothing happens!)

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

(Nothing happens!)

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Resulting SPT

Why It Works - Understanding Dijkstra Invariants

Invariants

predecessor[v]: best known predecessor of v.

distTo[v]: best known distance of s to v.

PQ maintains vertices based on distTo.

​

Important properties

Always visits vertices in order of total distance from source.

​

Problem 6: DJ Kistra

Problem 6

​

Problem 6A

​

(a) Describe a graph you could construct to help you solve the problem. At the very least you’ll want to mention what the vertices and edges are, and whether the edges are weighted or unweighted and directed or undirected.

Problem 6A

​

Q: How do we get from Shake It Off to Wildest Dreams while obeying the rule:

​

Two consecutive songs’ tempos must differ by no more than 10 beats per minute (BPM)

Shake It Off

Wildest Dreams

Problem 6A

​

Shake It Off

Let vertices be songs!

Love

Song

22

Lover

Wildest Dreams

But how do we know if two songs’ tempos differ by more than 10 BPM?

Problem 6A

​

Shake It Off

150 BPM

Include BPM in vertices!

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Storing multiple pieces of information in Vertex or Edge Objects is often useful.

Problem 6A

​

Shake It Off

150 BPM

Q: What are our edges?

​

We know we want to slow down the tempo and create a path between Shake It Off and Wildest Dreams.

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Problem 6A

​

Shake It Off

150 BPM

Let edges represent valid song transitions!

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

Problem 6A

​

Shake It Off

150 BPM

Let edges represent valid song transitions!

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

valid?

Problem 6A

​

Shake It Off

150 BPM

Let edges represent valid song transitions!

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Directed or Undirected?

​

Directed: We don’t want to play a song we already played since it has a faster tempo and is farther away from Wildest Dreams.

Problem 6A

​

💯

👀

Can we accomplish the task with the graph model we’ve built? Let’s check.

There’s more information we haven’t used. Does the length of the songs help us?

We don’t have a way to prioritize between different possible song transitions!

Problem 6A

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Q: Once we have edges, how do we know which path between Shake It Off and Wildest Dreams will take the least amount of time?

​

Looks like we need to encode more information in our graph.

Problem 6A

​

Shake It Off

150 BPM

Let edge weights be the length of the next song!

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Let’s think ahead: why does this help us decide which path will take the shortest amount of time?

​

We’ll use this information later when we run an algorithm on our graph to find the list of songs that take the least time.

237 sec.

Problem 6A

​

Shake It Off

150 BPM

Let edge weights be the length of the next song!

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Which algorithm can make use of edge weights to give us a shortest path?

237 sec.

Dijkstra’s!

Problem 6A

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Now our graph model has everything it needs to find the shortest path between Shake It Off and Wildest Dreams!

237 sec.

Vertices: song and BPM

​

Edges: valid song transitions

​

Weights: next song length

Problem 6B

​

(b) Describe an algorithm to construct your graph from the previous part. You may assume your songs are stored in whatever data structure makes this part easiest. Assume you have access to a method makeEdge(v1, v2, w) which creates an edge from v1 to v2 of weight w.

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

valid?

Let’s continue making edges and see if we can turn the process into an algorithm.

237 sec.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

valid?

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

​

237 sec.

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

valid?

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

valid?

valid?

valid?

valid?

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

Are these valid?

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

187 sec.

Are these valid?

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

187 sec.

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

187 sec.

222 sec.

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

187 sec.

222 sec.

Are these valid?

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

187 sec.

222 sec.

Problem 6B

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Ta-da! This is our graph :)

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

187 sec.

222 sec.

Problem 6B

​

Problem 6C

​

(c) Describe an algorithm you could run on the graph you just constructed to find the list of songs you can play to get to “Wildest Dreams” the fastest without disappointing the crowd.

Problem 6D

​

(d) What is the running time of your plan to find the list of songs? You should include the time it would take to construct your graph and to find the list of songs. Give a simplified big-O running time in terms of whatever variables you need.

Problem 6D

​

How long did it take to construct our graph?

​

​

We then run Dijkstra’s starting from Shake It Off. What’s the runtime of Dijkstra’s?

O(S²)

O(E*log(S) + S*log(S))

O(S² + E*log(S) + S*log(S))

What’s the total runtime to find the list of songs the DJ should play?

Is this simplified?

S² dominates S*log(S) so we can ignore the smaller term!

Total runtime: O(S² + E*log(S))