math for data science
today is 17 december i am revising for end term exams of iitm bs data science.
11 and 12 problem solving with speed and accuracy developing skill
Minimum Cost Spanning Tress: Prim's Algorithm
Prim's algorithm is another efficient greedy algorithm for finding a minimum spanning tree (MST) in a weighted undirected graph. It works by starting with an arbitrary vertex and iteratively adding the cheapest edge that connects the growing tree to an unvisited vertex, until all vertices are included. Here's how it works: Start with an empty MST and choose any vertex as the starting point. Identify all edges connected to the starting vertex. Add the cheapest edge that doesn't create a cycle to the MST. Consider the vertex at the other end of the added edge. Add all edges connected to this new vertex to the set of candidate edges. Repeat steps 2 and 3, always adding the cheapest edge that doesn't create a cycle to the MST and expanding the tree to include new vertices, until all vertices are included. Here are some key points about Prim's algorithm: It is a greedy algorithm, meaning it makes the locally optimal choice at each step (adding the cheapest edge) in the
Comments
Post a Comment