W3Schools 線上編輯器 - W3Schools 教學

Python

Java

class Graph:
    def __init__(self, size):
        self.size = size
        self.edges = []  # For storing edges as (u, v, weight)
        self.vertex_data = [''] * size  # Store vertex names

def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.edges.append((u, v, weight))  # Add edge with weight
            
    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

def kruskals_algorithm(self):
        result = []  # MST
        i = 0  # edge counter

self.edges = sorted(self.edges, key=lambda item: item[2])

parent, rank = [], []

for node in range(self.size):
            parent.append(node)
            rank.append(0)

while i < len(self.edges):
            u, v, weight = self.edges[i]
            i += 1
            
            x = self.find(parent, u)
            y = self.find(parent, v)
            if x != y:
                result.append((u, v, weight))
                self.union(parent, rank, x, y)

print("Edge \tWeight")
        for u, v, weight in result:
            print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")

g = Graph(7)
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_edge(0, 1, 4)  #A-B,  4
g.add_edge(0, 6, 10) #A-G, 10
g.add_edge(0, 2, 9)  #A-C,  9
g.add_edge(1, 2, 8)  #B-C,  8
g.add_edge(2, 3, 5)  #C-D,  5
g.add_edge(2, 4, 2)  #C-E,  2
g.add_edge(2, 6, 7)  #C-G,  7
g.add_edge(3, 4, 3)  #D-E,  3
g.add_edge(3, 5, 7)  #D-F,  7
g.add_edge(4, 6, 6)  #E-G,  6
g.add_edge(5, 6, 11) #F-G, 11

print("Kruskal's Algorithm MST:")
g.kruskals_algorithm()

#Python

#include <stdio.h>
#include <stdlib.h>

// Structure to represent an edge
typedef struct {
    int u, v, weight;
} Edge;

// Structure to represent a graph
typedef struct {
    int size;
    Edge* edges;
    char** vertex_data;
    int edgeCount;
} Graph;

// Function prototypes
void initGraph(Graph* g, int size);
void addEdge(Graph* g, int u, int v, int weight);
void addVertexData(Graph* g, int vertex, const char* data);
int find(int parent[], int i);
void unionSet(int parent[], int rank[], int x, int y);
void kruskalsAlgorithm(Graph* g);
int compareEdges(const void* a, const void* b);

void initGraph(Graph* g, int size) {
    g->size = size;
    g->edges = (Edge*)malloc(size * size * sizeof(Edge)); // Assuming maximum possible edges
    g->vertex_data = (char**)malloc(size * sizeof(char*));
    g->edgeCount = 0;
}

void addEdge(Graph* g, int u, int v, int weight) {
    g->edges[g->edgeCount].u = u;
    g->edges[g->edgeCount].v = v;
    g->edges[g->edgeCount].weight = weight;
    g->edgeCount++;
}

void addVertexData(Graph* g, int vertex, const char* data) {
    g->vertex_data[vertex] = (char*)malloc(2 * sizeof(char)); // Assuming single character names
    sprintf(g->vertex_data[vertex], "%s", data);
}

int find(int parent[], int i) {
    if (parent[i] == i)
        return i;
    return find(parent, parent[i]);
}

void unionSet(int parent[], int rank[], int x, int y) {
    int xRoot = find(parent, x);
    int yRoot = find(parent, y);

if (rank[xRoot] < rank[yRoot])
        parent[xRoot] = yRoot;
    else if (rank[xRoot] > rank[yRoot])
        parent[yRoot] = xRoot;
    else {
        parent[yRoot] = xRoot;
        rank[xRoot]++;
    }
}

int compareEdges(const void* a, const void* b) {
    Edge* edgeA = (Edge*)a;
    Edge* edgeB = (Edge*)b;
    return edgeA->weight - edgeB->weight;
}

void kruskalsAlgorithm(Graph* g) {
    Edge result[g->size]; // This will store the resultant MST
    int e = 0; // An index variable, used for result[]
    int i = 0; // An index variable, used for sorted edges

qsort(g->edges, g->edgeCount, sizeof(g->edges[0]), compareEdges);

int parent[g->size];
    int rank[g->size];

for (int node = 0; node < g->size; ++node) {
        parent[node] = node;
        rank[node] = 0;
    }

while (i < g->edgeCount) {
        Edge next_edge = g->edges[i++];
        int x = find(parent, next_edge.u);
        int y = find(parent, next_edge.v);

if (x != y) {
            result[e++] = next_edge;
            unionSet(parent, rank, x, y);
        }
    }

printf("Edge \tWeight\n");
    for (i = 0; i < e; ++i) {
        printf("%s-%s \t%d\n", g->vertex_data[result[i].u], g->vertex_data[result[i].v], result[i].weight);
    }
}

// Main function to demonstrate the Kruskal's Algorithm
int main() {
    Graph g;
    initGraph(&g, 7); // Initialize graph with 7 vertices

// Add vertex names
    addVertexData(&g, 0, "A");
    addVertexData(&g, 1, "B");
    addVertexData(&g, 2, "C");
    addVertexData(&g, 3, "D");
    addVertexData(&g, 4, "E");
    addVertexData(&g, 5, "F");
    addVertexData(&g, 6, "G");

// Add edges
    addEdge(&g, 0, 1, 4);  // A-B, weight  4
    addEdge(&g, 0, 6, 10); // A-G, weight 10
    addEdge(&g, 0, 2, 9);  // A-C, weight  9
    addEdge(&g, 1, 2, 8);  // B-C, weight  8
    addEdge(&g, 2, 3, 5);  // C-D, weight  5
    addEdge(&g, 2, 4, 2);  // C-E, weight  2
    addEdge(&g, 2, 6, 7);  // C-G, weight  7
    addEdge(&g, 3, 4, 3);  // D-E, weight  3
    addEdge(&g, 3, 5, 7);  // D-F, weight  7
    addEdge(&g, 4, 6, 6);  // E-G, weight  6
    addEdge(&g, 5, 6, 11); // F-G, weight 11

printf("Kruskal's Algorithm MST:\n");
    kruskalsAlgorithm(&g);

return 0;
}

//C

import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static class Edge implements Comparable<Edge> {
        int src, dest, weight;

public int compareTo(Edge compareEdge) {
            return this.weight - compareEdge.weight;
        }
    }

static class Subset {
        int parent, rank;
    }

static class Graph {
        int V; // Number of vertices
        ArrayList<Edge> edges; // Collection of all edges
        String[] vertexNames; // Store vertex names for printout

Graph(int v) {
            V = v;
            edges = new ArrayList<>();
            vertexNames = new String[V];
        }

void addEdge(int src, int dest, int weight) {
            Edge newEdge = new Edge();
            newEdge.src = src;
            newEdge.dest = dest;
            newEdge.weight = weight;
            edges.add(newEdge);
        }

void addVertexName(int vertex, String name) {
            vertexNames[vertex] = name;
        }

// Make find method similar to Python's, using path compression
        int find(Subset subsets[], int i) {
            if (subsets[i].parent != i)
                subsets[i].parent = find(subsets, subsets[i].parent);
            return subsets[i].parent;
        }

// Simplify union method to match Python's logic more closely
        void union(Subset subsets[], int x, int y) {
            int xRoot = find(subsets, x);
            int yRoot = find(subsets, y);

// Attach smaller rank tree under root of high rank tree
            if (subsets[xRoot].rank < subsets[yRoot].rank)
                subsets[xRoot].parent = yRoot;
            else if (subsets[xRoot].rank > subsets[yRoot].rank)
                subsets[yRoot].parent = xRoot;
            else {
                subsets[yRoot].parent = xRoot;
                subsets[xRoot].rank++;
            }
        }

void KruskalMST() {
            ArrayList<Edge> result = new ArrayList<>(); // This will store the resultant MST
            Collections.sort(edges); // Sort all the edges in non-decreasing order of their weight

Subset subsets[] = new Subset[V];
            for (int v = 0; v < V; ++v) {
                subsets[v] = new Subset();
                subsets[v].parent = v;
                subsets[v].rank = 0;
            }

int i = 0; // Index used to pick next edge

while (i < edges.size()) {
                Edge next_edge = edges.get(i++);

int x = find(subsets, next_edge.src);
                int y = find(subsets, next_edge.dest);

if (x != y) {
                    result.add(next_edge);
                    union(subsets, x, y);
                }
            }

System.out.println("Edge \tWeight");
            for (Edge e : result)
                System.out.println(vertexNames[e.src] + "-" + vertexNames[e.dest] + "\t" + e.weight);
        }
    }

// Driver Code
    public static void main(String[] args) {
        int V = 7; // Number of vertices in graph
        Graph graph = new Graph(V);

// add edges
        graph.addEdge(0, 1, 4);  // A-B, weight  4
        graph.addEdge(0, 6, 10); // A-G, weight 10
        graph.addEdge(0, 2, 9);  // A-C, weight  9
        graph.addEdge(1, 2, 8);  // B-C, weight  8
        graph.addEdge(2, 3, 5);  // C-D, weight  5
        graph.addEdge(2, 4, 2);  // C-E, weight  2
        graph.addEdge(2, 6, 7);  // C-G, weight  7
        graph.addEdge(3, 4, 3);  // D-E, weight  3
        graph.addEdge(3, 5, 7);  // D-F, weight  7
        graph.addEdge(4, 6, 6);  // E-G, weight  6
        graph.addEdge(5, 6, 11); // F-G, weight 11

// adding names
        graph.addVertexName(0, "A");
        graph.addVertexName(1, "B");
        graph.addVertexName(2, "C");
        graph.addVertexName(3, "D");
        graph.addVertexName(4, "E");
        graph.addVertexName(5, "F");
        graph.addVertexName(6, "G");

System.out.println("Kruskal's Algorithm MST:");
        graph.KruskalMST();
    }
}

// Java