CSE 373 Au24 AX Section 9

MSTs and Project Sidewalk

​

Check-in

Any plans for break on Nov 28-29?

Announcements

• Lectures: Code Challenges on Friday! Learn more about interviewing + LeetCode :)
• Project: Shortest Paths Analysis due tomorrow night! Last project!
• Extra resubmissions out, due Nov 27th!

MicroTeach: MSTs

MSTs

• Tree: (when talking about graphs) An connected acyclic graph.�
• Spanning Tree: A set of edges connecting all nodes of the graph in a Tree.�
• Minimum Spanning Tree: The Spanning Tree of lowest possible total weight.�
• Multiple algorithms that are used to find MSTs!

��� �

​

​

1

A

B

C

D

3

4

2

5

1

A

B

C

D

3

4

2

5

1

A

B

C

D

3

4

2

5

MSTs vs. SPTs: A Key Difference

A shortest paths tree depends on the source vertex. There is no source vertex for a minimum spanning tree. The SPT for every other vertex is different from the MST!

Minimizes each node’s distance from source

Minimizes tree’s total edge weight

A

2

4

3

1

D

B

C

SPT from A

A

2

4

3

1

D

B

C

MST

MST Finding Algorithms

Prim’s

​

Start a tree from a single node.��Each iteration, connect a node in the tree to a node not in the tree with the cheapest edge possible. ��(Slowly builds up one, connected tree).

Kruskal’s

​

Repeatedly add the smallest edge that doesn’t cause a cycle in the tree you are building. ��(Can build a few disconnected trees before they all merge). => Disjoint Sets/Union Find ADT

[Thinks about nodes!]

[Thinks about edges!]

Prim’s Walkthrough

Try the problem on your worksheet now!

Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

10

0

6

8

Note: The red lines represent a “cut”!

Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

10

0

6

8

Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

10

0

6

8

Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

10

0

6

8

Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

10

0

6

8

Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

0

6

8

Prim’s

A

C

B

D

2

7

1

4

3

E

5

G

F

9

10

0

6

8

Resulting MST!

A

C

B

D

2

1

3

E

5

G

F

0

6

Kruskal’s Walkthrough

Try the problem on your worksheet now!

Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

for each edge(u,v) in sorted order:

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

4

Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

for each edge(u,v) in sorted order:

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

4

Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

for each edge(u,v) in sorted order:

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

4

Note: We join C and F, so it is reflected under both in the table! (union)

Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

for each edge(u,v) in sorted order:

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Note: choosing between D-G and A-E is arbitrary + up to you!

Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

for each edge(u,v) in sorted order:

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

for each edge(u,v) in sorted order:

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Note: choosing between B-D and E-C is arbitrary + up to you!

Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

for each edge(u,v) in sorted order:

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

for each edge(u,v) in sorted order:

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Note: There is a distinction between E-F and A-B! Cycles!

Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

for each edge(u,v) in sorted order:

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

By now, all vertices have been joined - the remaining larger weighted edges create cycles! (To optimize, stop at |V| - 1)

Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

for each edge(u,v) in sorted order:

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

for each edge(u,v) in sorted order:

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Kruskal’s

A

B

E

C

D

G

F

4

2

3

5

1

6

9

3

2

4

Kruskal’s pseudocode(Graph G):

Create disjoint sets for each vertex in G

Sort the edges by weight

for each edge(u,v) in sorted order:

If u is not in the same set as v:

Join set u and v)

Add edge(u,v) to mst

​

Resulting MST!

Case Study: Project Sidewalk

Inaccessible Paths

Consider the following scenario…

• The grand staircase vs. ramp
• Which one is shorter? Which one is more accessible?
• Let's check out more examples from Project Sidewalk!

​

​

Naive Approach

Naive Approach: Boolean Field for “inaccessible”

Additional input: A set of “inaccessible edges” decided by volunteers

​

​

​

​

As we construct the graph, explicitly check if an edge has been deemed as “inaccessible”

• If yes, move on to other edges
• Don’t allow it to be part of our graph setup for Dijkstra’s!
• If no, add it into the edge set

​

Shortest Paths Project: Naive Approach Implementation

Insert if-checks towards each edge here, where we add the edge information to build the graph

Naive Approach: Potential drawbacks to consider…

Draw out what this graph would look like without the inaccessible edges before we run Dijkstra’s from S, given the set of inaccessible edges below.

​

​

​

​

​

Are there any potential drawbacks to this algorithm to consider? How might this algorithm not work the way we expect it to?

​

Set of inaccessible edges:

S –> T

S –> Y

Naive Approach: Potential drawbacks to consider…

• What if we accidentally disconnect the graph?
• The criterion for shortest path could potentially eliminate all paths : (

​

• Example:

Set of inaccessible edges:

S –> T

S –> Y

A disconnected graph!

New Approach!

New Approach: Cost Refinements with accessibility score

Instead of completely relying on the “accessibility” condition of an edge, we are given an “accessibility score” between 0 to 1:

Refined cost of an edge = Original Cost / Accessibility Score

​

Accessibility Score Range

​

​

​

​

​

Accessibility Score = 0

The refined cost goes to infinity in this case, marking the edge as being “extremely inaccessible”.

Refined cost remains the same, indicating no extra cost arising from the accessible criterion when this edge is included

​

Accessibility Score = 1

New Approach: Cost Refinements

Instead of completely relying on the “accessibility” condition of an edge, we are given an “accessibility score” between 0 to 1:

Refined cost of an edge = Original Cost / Accessibility Score

​

Additional input data set: Edge set with associated accessibility score

​

​

New Approach: Example

This is what we’re seeing in the Shortest Paths Project!

For your analysis, consider alternatives! Would you maybe set an adjustable threshold, or use other diverse factors?

Diverse Factors; Diverse Weights

In the previous examples, we were only concerned about physical access as being a barrier to accessibility. What other factors or aspects of paths may be of interest to users? What are other possible barriers to accessibility?

​

Here’s one example, please come up with others:

• Safety of the path

Closing Announcements

• Thanks for coming to section! See you tomorrow in class! Stay safe and stay hydrated :)
• Remember analysis for Shortest Paths is due tomorrow night!

​

​

Please don't hesitate to reach out if you have any

questions or concerns about the course, or if there's

anything else we can help you with! We're here to support

you however we can!