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 Graph Search.
Lecture
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 Graph Search.
This lecture covers the concept of minimum spanning trees, focusing on Prim's algorithm to find the tree with the smallest total edge weight in a complete graph. The instructor explains the process of selecting edges and vertices to build the tree while ensuring no cycles are formed. Additionally, the Traveling Salesman Problem is introduced, discussing the challenge of finding the shortest closed path visiting all vertices exactly once. Various algorithms and complexities are explored to address this optimization problem.