**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Lecture# Prim's and Kruskal's Algorithms

Description

This lecture covers Prim's algorithm, starting with any vertex and greedily growing a tree by adding minimum weight crossing edges. The cut property is explained, showing why the algorithm works. The lecture also delves into Kruskal's algorithm, which starts with an empty forest and adds the cheapest edge that does not create a cycle at each step. Implementation challenges and analysis of both algorithms are discussed, emphasizing the importance of maintaining acyclicity and finding minimum crossing edges. The lecture concludes with a summary highlighting the use of Min-priority queue for Prim's algorithm and Union-Find for Kruskal's algorithm.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

In course

Instructors (2)

Related concepts (33)

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

Greedy algorithm

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time. For example, a greedy strategy for the travelling salesman problem (which is of high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city.

Borůvka's algorithm

Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph, or a minimum spanning forest in the case of a graph that is not connected. It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia. The algorithm was rediscovered by Choquet in 1938; again by Florek, Łukasiewicz, Perkal, Steinhaus, and Zubrzycki in 1951; and again by Georges Sollin in 1965. This algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature.

Prim's algorithm

In computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

Kruskal's algorithm

Kruskal's algorithm (also known as Kruskal's method) finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. (A minimum spanning tree of a connected graph is a subset of the edges that forms a tree that includes every vertex, where the sum of the weights of all the edges in the tree is minimized. For a disconnected graph, a minimum spanning forest is composed of a minimum spanning tree for each connected component.

Euclidean minimum spanning tree

A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

Related lectures (32)

Prim's and Kruskal's AlgorithmsCS-250: Algorithms I

Explores Prim's and Kruskal's algorithms for finding minimum spanning trees in a graph, covering their correctness, implementation, and analysis.

Minimum Spanning TreesCS-250: Algorithms I

Covers the implementation and analysis of disjoint sets data structure and introduces the concept of minimum spanning trees.

Union-Find and Prim's AlgorithmCS-250: Algorithms I

Introduces Union-Find data structure and Prim's algorithm for minimum spanning trees in graphs, exploring cuts and historical origins.

Minimum Spanning Trees: Prims AlgorithmCS-250: Algorithms I

Covers minimum spanning trees, disjoint-set data structures, union methods, and Prim's algorithm for finding minimum spanning trees.

Union-Find and Minimum Spanning TreesCS-250: Algorithms I

Covers the Union-Find data structure and Minimum Spanning Trees.