W3Schools 線上編輯器 - W3Schools 教學

Python

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 <stdio.h>
#include <limits.h>
#include <stdbool.h>

#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