Find cost of tree with prims algorithm in data structures
Prim's algorithm is a well-known algorithm for finding the minimum spanning tree (MST) of a weighted undirected graph. The algorithm works by starting with a single vertex and gradually adding vertices to the tree that minimize the total weight of the edges in the tree.
Prim's algorithm is a greedy algorithm that finds a minimum spanning tree in a weighted undirected graph. The algorithm starts with a single vertex and incrementally adds vertices to the tree, choosing the edge with the smallest weight that connects a vertex in the tree to a vertex outside the tree.
To find the cost of the minimum spanning tree using Prim's algorithm, we need to keep track of the total weight of the edges in the tree as we build it. Here's the pseudocode for Prim's algorithm with cost calculation:
function prim (graph):
// initialize empty set and priority queue
tree = { }
pq = priority_queue ( )
// add first vertex to tree and its edges to priority queue
start_vertex = graph. vertices [ 0]
add_edges_to_pq (start_vertex, pq)
while pq is not empty:
// get edge with smallest weight
curr_edge = pq. pop ( )
// check if edge connects to new vertex
if curr_edge. vertex1 not in tree:
new_vertex = curr_edge. vertex1
else:
new_vertex = curr_edge. vertex2
// add new vertex and edge to tree, and add new edges to priority queue
tree. add (new_vertex)
tree. add (curr_edge)
add_edges_to_pq (new_vertex, pq)
// calculate total cost of the tree
total_cost = 0
for edge in tree:
total_cost += edge. weight
return total_cost
function add_edges_to_pq (vertex, pq):
// add edges from vertex to priority queue
for edge in vertex. edges:
if edge. other_vertex (vertex) not in tree:
pq. push (edge)
In this pseudocode, graph represents the weighted undirected graph, and each vertex in the graph has a set of edges that connect it to other vertices. The priority_queue is a data structure that stores edges in increasing order of weight.
The prim function starts by initializing an empty set tree and a priority queue pq. It then adds the first vertex in the graph to tree and its edges to pq. The algorithm then enters a loop that continues until pq is empty.
In each iteration of the loop, the algorithm removes the edge with the smallest weight from pq. It then checks if the edge connects to a vertex that is not already in tree. If it does, the algorithm adds the new vertex and the edge to tree, and adds the new vertex's edges to pq. If the edge connects to a vertex that is already in tree, the algorithm discards the edge and moves on to the next one in pq.
Once the algorithm has built the minimum spanning tree, it calculates the total cost of the tree by summing the weights of its edges. The total cost is returned as the output of the function.
Note that the cost of the tree can also be calculated by summing the weights of the edges in tree as they are added, without the need for a separate loop at the end. However, the pseudocode above separates the cost calculation from the main loop for clarity.
Here is an implementation of Prim's algorithm in Python:
import heapq
def prim (graph):
# Initialize the tree and the set of visited vertices
tree = [ ]
visited = set ( )
# Choose a starting vertex (we' ll choose the first vertex)
start_vertex = next (iter (graph))
# Add the starting vertex to the visited set
visited. add (start_vertex)
# Get the edges that connect the starting vertex to other vertices
edges = [ ( weight, start_vertex, neighbor) for neighbor, weight in graph [ start_vertex ]. items ( ) ]
# Heapify the edges so we can efficiently get the minimum edge
heapq. heapify (edges)
# While there are still edges to process
while edges:
# Get the minimum edge
weight, vertex1, vertex2 = heapq. heappop (edges)
# If we've already visited this vertex, continue
if vertex2 in visited:
continue
# Add the edge to the tree
tree. Append ( ( vertex1, vertex2, weight))
# Mark the second vertex as visited
visited. add (vertex2)
# Get the edges that connect the second vertex to other vertices
for neighbor, weight in graph [ vertex2]. items ( ):
if neighbor not in visited:
heapq. heappush (edges, (weight, vertex2, neighbor))
# Return the minimum spanning tree
return treeIn this implementation, graph is a dictionary that represents the graph, where each key is a vertex and the value is another dictionary that maps neighbours to edge weights.
To calculate the cost of the tree, you can simply sum up the weights of all the edges in the tree:
tree = prim(graph)
cost = sum(weight for _, _, weight in tree)
The variable cost will contain the cost of the minimum spanning tree.
Prim's algorithm starts with a single vertex and gradually builds up the MST by adding edges that connect to the vertices already in the tree. At each step, the algorithm selects the edge with the minimum weight that connects a vertex in the tree to a vertex that is not yet in the tree.
The algorithm maintains a set of visited vertices, which starts with just the starting vertex. It also maintains a heap of edges that connect visited vertices to unvisited vertices, sorted by their weights.
The algorithm repeatedly extracts the minimum-weight edge from the heap and adds it to the tree, as long as it connects a visited vertex to an unvisited vertex. When a new vertex is added to the tree, its edges to unvisited vertices are added to the heap.
The algorithm continues until all vertices are visited, at which point the tree is the MST.
To calculate the cost of the MST, we simply sum up the weights of all the edges in the tree, as mentioned earlier. This gives us the total weight of the minimum spanning tree, which is the smallest possible sum of weights that can connect all the vertices in the graph.
import java. util. *;
class Edge implements Comparable < Edge > {
int vertex1;
int vertex2;
int weight;
public Edge (int vertex1, int vertex2, int weight) {
this. vertex1 = vertex1;
this. vertex2 = vertex2;
this. weight = weight;
}
public int compareTo (Edge other) {
return this. weight - other. weight;
}
}
public class Prim {
public static int prim (ArrayList < ArrayList < Edge > > graph) {
int n = graph. size ( );
boolean [ ] visited = new boolean [ n];
PriorityQueue < Edge > pq = new PriorityQueue < > ( );
// add first vertex to tree and its edges to priority queue
visited [ 0] = true;
addEdgesToPQ (graph. get ( 0), visited, pq);
int totalCost = 0;
while (! pq. isEmpty ( )) {
// get edge with smallest weight
Edge currEdge = pq. poll ( );
// check if edge connects to new vertex
int newVertex;
if ( ! visited [ currEdge. vertex1] ) {
newVertex = currEdge. vertex1;
} else {
newVertex = currEdge. vertex2;
}
// add new vertex and edge to tree, and add new edges to priority queue
Visited [ newVertex] = true;
totalCost += currEdge. weight;
addEdgesToPQ (graph. get (newVertex), visited, pq);
}
return totalCost;
}
public static void addEdgesToPQ (ArrayList < Edge > edges, boolean [ ] visited, PriorityQueue < Edge > pq) {
for (Edge edge : edges) {
if (! visited [edge. vertex1] | | ! visited [ edge. vertex2]) {
pq. add (edge);
}
}
}
public static void main (String [ ] args) {
// example graph
ArrayList < ArrayList < Edge > > graph = new ArrayList < > ( );
graph. add (new ArrayList < > (Arrays. asList (new Edge (1, 2, 1), new Edge (1, 3, 4) ) ) );
graph. add (new ArrayList < > (Arrays. asList (new Edge (0, 2, 2), new Edge (2, 3, 5) ) ) );
graph. add (new ArrayList < > (Arrays. asList (new Edge (0, 1, 2), new Edge (1, 3, 3), new Edge (2, 3, 1) ) ) );
graph. add (new ArrayList < > (Arrays. asList (new Edge (0, 1, 4), new Edge (1, 2, 3), new Edge (2, 3, 1) ) ) );
int cost = prim (graph);
System. out. println ( " Cost of minimum spanning tree: " + cost);
}
}