Posts in 2021
-
Kruskal Algorithm
Tuesday, December 14, 2021 in 12-14 Kruskal
Make a minimal spanning tree by adding the smallest weight edge that connects two previously unconnected vertices. Count two vertices as connected if there is any path between them (not just a single edge). Code Outline We will produce a new Graph …
-
12-06 MST Wrapup
Tuesday, December 07, 2021 in Daily
Key question: how do you know your code produces a minimal spanning tree? Try some of these test cases. total weight Write a new method in the weighted graph class to return the total weight of all of the edges given. def total_weight(self, edges: …
-
12-02 MST Testing
Friday, December 03, 2021 in Daily
Minimal Spanning Tree: Basic Version We discussed in class a method for creating a minimal spanning tree from a weighted graph. If you need to look it up, it is known as Prim’s Algorithm. from typing import List, Dict, Tuple, Set def …
-
12-01 Weighted
Wednesday, December 01, 2021 in Daily
WeightedGraph Class Make a WeightedGraph subclass of your Graph class. (Just copy and edit if you’re not interested in subclassing.) self.weights[(a,b)] == wt means the edge from a to b has weight wt. The weights dictionary should be symmetric …
-
11-16 Tree Diam
Tuesday, November 16, 2021 in Daily
What is the definition of a tree? (That is, what conditions on a graph cause it to be considered a tree?) The diameter of a graph is the maximum distance between any two vertices. For a general graph, a quadratic algorithm is needed. When a graph is …
-
10-27 Slow Cut
Wednesday, October 27, 2021 in Daily
A cut vertex or “articulation vertex” is a vertex whose removal disconnects the graph. There is an efficient way of finding cut vertices, but as a warm up we will just focus on a simple algorithm. Remember: you should develop test cases …
-
10-20 Two Coloring
Wednesday, October 20, 2021 in Daily
A graph can be “colored” with N colors if you can paint every vertex with one of the N colors and have no edge between vertices of the same color. We will use integers to represent colors, like 0=red, 1=green, etc. (The actual colors do …
-
10-19 Connected
Tuesday, October 19, 2021 in Daily
Write a function to find the number of connected components in a graph. def connected_components(g: Graph) -> int: return -1 # skeleton Follow the design process to make it go more smoothly. Testing your code You should make some simple examples …
-
Design Process
Friday, October 15, 2021 in Daily
Show you understand the problem. Write using a fast feedback process. Demonstrate your code works. Understand the problem Examples that you have worked out show that you understand the problem. Pick two examples and show: What information is input …
-
10-15 Diameter
Wednesday, October 13, 2021 in Daily
Recall the setup from the previous project: Generate a random graph (“maze”) with 2000 vertices. Add 100 random edges to your graph. Diameter The diameter of a graph is the maximum shortest distance between any two vertices. Draw two …