Lab 19: Minimum Spanning Trees | CS 61BL Summer 2024
Each assignment will have an FAQ linked at the top. You can also access it by adding “/faq” to the end of the URL. The FAQ for Lab 19 is located here. As usual, pull the files from the skeleton and make a new IntelliJ project. Consider an undirected graph 𝐺 = ( 𝑉 , 𝐸 ) comprising of a set of vertices, 𝑉 , and a set of edges, 𝐸 . Let’s define some terms first: A tree is a connected graph that has no cycles. If it has 𝑁 vertices, then it must have exactly 𝑁 − 1 edges in order to satisfy these properties. A spanning tree, informally, can be thought of as a tree that spans all the vertices in a graph. Formally, a spanning tree 𝑇 = ( 𝑉 , 𝐹 ) of 𝐺 is a tree that contains all of the vertices 𝑉 of the graph 𝐺 , and a subset of its edges: 𝐹 ⊆ 𝐸 , where | 𝐹 | = | 𝑉 | − 1 . Here’s an example of two different spanning trees on the same graph. Notice how each spanning tree contains all of the vertices 𝑉 in the graph, exactly | 𝑉 | − 1 edges, and is connected.
Each assignment will have an FAQ linked at the top. You can also access it by adding “/faq” to the end of the URL. The FAQ for Lab 19 is located here. As usual, pull the files from the skeleton and make a new IntelliJ project. Consider an undirected graph 𝐺 = ( 𝑉 , 𝐸 ) comprising of a set of vertices, 𝑉 , and a set of edges, 𝐸 . Let’s define some terms first: A tree is a connected graph that has no cycles. If it has 𝑁 vertices, then it must have exactly 𝑁 − 1 edges in order to satisfy these properties. A spanning tree, informally, can be thought of as a tree that spans all the v
Explore this link on the map →