Run ❯
Get your
own
website
×
Change Orientation
Change Theme, Dark/Light
Go to Spaces
Python
C
Java
class Graph: def __init__(self, size): self.adj_matrix = [[0] * size for _ in range(size)] self.size = size self.vertex_data = [''] * size def add_edge(self, u, v, weight): if 0 <= u < self.size and 0 <= v < self.size: self.adj_matrix[u][v] = weight self.adj_matrix[v][u] = weight # For undirected graph def add_vertex_data(self, vertex, data): if 0 <= vertex < self.size: self.vertex_data[vertex] = data def prims_algorithm(self): in_mst = [False] * self.size key_values = [float('inf')] * self.size parents = [-1] * self.size key_values[0] = 0 # Starting vertex print("Edge \tWeight") for _ in range(self.size): u = min((v for v in range(self.size) if not in_mst[v]), key=lambda v: key_values[v]) in_mst[u] = True if parents[u] != -1: # Skip printing for the first vertex since it has no parent print(f"{self.vertex_data[parents[u]]}-{self.vertex_data[u]} \t{self.adj_matrix[u][parents[u]]}") for v in range(self.size): if 0 < self.adj_matrix[u][v] < key_values[v] and not in_mst[v]: key_values[v] = self.adj_matrix[u][v] parents[v] = u g = Graph(8) g.add_vertex_data(0, 'A') g.add_vertex_data(1, 'B') g.add_vertex_data(2, 'C') g.add_vertex_data(3, 'D') g.add_vertex_data(4, 'E') g.add_vertex_data(5, 'F') g.add_vertex_data(6, 'G') g.add_vertex_data(7, 'H') g.add_edge(0, 1, 4) # A - B g.add_edge(0, 3, 3) # A - D g.add_edge(1, 2, 3) # B - C g.add_edge(1, 3, 5) # B - D g.add_edge(1, 4, 6) # B - E g.add_edge(2, 4, 4) # C - E g.add_edge(2, 7, 2) # C - H g.add_edge(3, 4, 7) # D - E g.add_edge(3, 5, 4) # D - F g.add_edge(4, 5, 5) # E - F g.add_edge(4, 6, 3) # E - G g.add_edge(5, 6, 7) # F - G g.add_edge(6, 7, 5) # G - H print("Prim's Algorithm MST:") g.prims_algorithm() #Python
#include
#include
#include
#define SIZE 8 // Assuming a fixed size graph as per the given Python example // Graph structure in C typedef struct Graph { int adj_matrix[SIZE][SIZE]; char* vertex_data[SIZE]; int size; void (*add_edge)(struct Graph*, int, int, int); void (*add_vertex_data)(struct Graph*, int, char*); void (*prims_algorithm)(struct Graph*); } Graph; // Function to initialize the graph void init_graph(Graph* g, int size) { g->size = size; for (int i = 0; i < size; i++) { g->vertex_data[i] = ""; for (int j = 0; j < size; j++) { g->adj_matrix[i][j] = 0; } } } // Function to add an edge void add_edge(Graph* g, int u, int v, int weight) { if (u >= 0 && u < g->size && v >= 0 && v < g->size) { g->adj_matrix[u][v] = weight; g->adj_matrix[v][u] = weight; // For an undirected graph } } // Function to add vertex data void add_vertex_data(Graph* g, int vertex, char* data) { if (vertex >= 0 && vertex < g->size) { g->vertex_data[vertex] = data; } } // Function to print the MST using Prim's Algorithm void prims_algorithm(Graph* g) { bool in_mst[SIZE]; int key_values[SIZE]; int parents[SIZE]; // Initialize all key values as INFINITE and in_mst as false for (int i = 0; i < g->size; i++) { key_values[i] = INT_MAX; in_mst[i] = false; parents[i] = -1; } // Starting from the first vertex key_values[0] = 0; printf("Edge \tWeight\n"); for (int count = 0; count < g->size; count++) { // Find the minimum key vertex from the set of vertices not yet included in MST int min = INT_MAX, u = -1; for (int v = 0; v < g->size; v++) { if (!in_mst[v] && key_values[v] < min) { min = key_values[v]; u = v; } } in_mst[u] = true; // Print the edge as it's added to the MST, skip if u is the starting vertex if (parents[u] != -1) { printf("%s-%s \t%d\n", g->vertex_data[parents[u]], g->vertex_data[u], g->adj_matrix[u][parents[u]]); } // Update key value and parent index of the adjacent vertices of the picked vertex for (int v = 0; v < g->size; v++) { if (g->adj_matrix[u][v] && !in_mst[v] && g->adj_matrix[u][v] < key_values[v]) { key_values[v] = g->adj_matrix[u][v]; parents[v] = u; } } } } // Main function to demonstrate the Prim's Algorithm int main() { Graph g; init_graph(&g, SIZE); add_vertex_data(&g, 0, "A"); add_vertex_data(&g, 1, "B"); add_vertex_data(&g, 2, "C"); add_vertex_data(&g, 3, "D"); add_vertex_data(&g, 4, "E"); add_vertex_data(&g, 5, "F"); add_vertex_data(&g, 6, "G"); add_vertex_data(&g, 7, "H"); // Add edges add_edge(&g, 0, 1, 4); // A - B add_edge(&g, 0, 3, 3); // A - D add_edge(&g, 1, 2, 3); // B - C add_edge(&g, 1, 3, 5); // B - D add_edge(&g, 1, 4, 6); // B - E add_edge(&g, 2, 4, 4); // C - E add_edge(&g, 2, 7, 2); // C - H add_edge(&g, 3, 4, 7); // D - E add_edge(&g, 3, 5, 4); // D - F add_edge(&g, 4, 5, 5); // E - F add_edge(&g, 4, 6, 3); // E - G add_edge(&g, 5, 6, 7); // F - G add_edge(&g, 6, 7, 5); // G - H printf("Prim's Algorithm MST:\n"); prims_algorithm(&g); return 0; } //C
import java.util.Arrays; public class Main { private static class Graph { int size; int[][] adjMatrix; String[] vertexData; boolean[] inMST; int[] keyValues; int[] parents; public Graph(int size) { this.size = size; this.adjMatrix = new int[size][size]; this.vertexData = new String[size]; this.inMST = new boolean[size]; this.keyValues = new int[size]; this.parents = new int[size]; Arrays.fill(this.keyValues, Integer.MAX_VALUE); Arrays.fill(this.parents, -1); } public void addEdge(int u, int v, int weight) { adjMatrix[u][v] = weight; adjMatrix[v][u] = weight; } public void addVertexData(int vertex, String data) { vertexData[vertex] = data; } public void primsAlgorithm() { keyValues[0] = 0; System.out.println("Edge"+ " \t" + "Weight"); for (int count = 0; count < size; count++) { int u = -1; int min = Integer.MAX_VALUE; for (int v = 0; v < size; v++) { if (!inMST[v] && keyValues[v] < min) { min = keyValues[v]; u = v; } } inMST[u] = true; if (parents[u] != -1) { System.out.println(vertexData[parents[u]] + "-" + vertexData[u] + " \t" + adjMatrix[u][parents[u]]); } for (int v = 0; v < size; v++) { if (adjMatrix[u][v] != 0 && !inMST[v] && adjMatrix[u][v] < keyValues[v]) { parents[v] = u; keyValues[v] = adjMatrix[u][v]; } } } } } public static void main(String[] args) { Graph g = new Graph(8); g.addVertexData(0, "A"); g.addVertexData(1, "B"); g.addVertexData(2, "C"); g.addVertexData(3, "D"); g.addVertexData(4, "E"); g.addVertexData(5, "F"); g.addVertexData(6, "G"); g.addVertexData(7, "H"); g.addEdge(0, 1, 4); // A - B g.addEdge(0, 3, 3); // A - D g.addEdge(1, 2, 3); // B - C g.addEdge(1, 3, 5); // B - D g.addEdge(1, 4, 6); // B - E g.addEdge(2, 4, 4); // C - E g.addEdge(2, 7, 2); // C - H g.addEdge(3, 4, 7); // D - E g.addEdge(3, 5, 4); // D - F g.addEdge(4, 5, 5); // E - F g.addEdge(4, 6, 3); // E - G g.addEdge(5, 6, 7); // F - G g.addEdge(6, 7, 5); // G - H System.out.println("Prim's Algorithm MST:"); g.primsAlgorithm(); } } // Java
Python result:
C result:
Java result:
Prim's Algorithm MST:
Edge Weight
A-D 3
A-B 4
B-C 3
C-H 2
C-E 4
E-G 3
D-F 4
Prim's Algorithm MST:
Edge Weight
A-D 3
A-B 4
B-C 3
C-H 2
C-E 4
E-G 3
D-F 4
Prim's Algorithm MST:
Edge Weight
A-D 3
A-B 4
B-C 3
C-H 2
C-E 4
E-G 3
D-F 4