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
        self.parent = [i for i in range(size)]  # Union-Find array

def add_edge(self, u, v):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = 1
            self.adj_matrix[v][u] = 1

def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

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

def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        print('Union:',self.vertex_data[x],'+',self.vertex_data[y])
        self.parent[x_root] = y_root
        print(self.parent,'\n')

def is_cyclic(self):
        for i in range(self.size):
            for j in range(i + 1, self.size):
                if self.adj_matrix[i][j]:
                    x = self.find(i)
                    y = self.find(j)
                    if x == y:
                        return True
                    self.union(x, y)
        return False

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

print("Graph has cycle:", g.is_cyclic())

#Python

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

typedef struct {
    int **adj_matrix;
    char *vertex_data;
    int *parent;
    int size;
} Graph;

Graph* create_graph(int size) {
    Graph *g = malloc(sizeof(Graph));
    g->size = size;

g->adj_matrix = malloc(size * sizeof(int *));
    for (int i = 0; i < size; i++) {
        g->adj_matrix[i] = calloc(size, sizeof(int));
    }

g->vertex_data = malloc(size * sizeof(char));
    for (int i = 0; i < size; i++) {
        g->vertex_data[i] = '\0';
    }

g->parent = malloc(size * sizeof(int));
    for (int i = 0; i < size; i++) {
        g->parent[i] = i;
    }

return g;
}

void add_edge(Graph *g, int u, int v) {
    if (u >= 0 && u < g->size && v >= 0 && v < g->size) {
        g->adj_matrix[u][v] = 1;
        g->adj_matrix[v][u] = 1;
    }
}

void add_vertex_data(Graph *g, int vertex, char data) {
    if (vertex >= 0 && vertex < g->size) {
        g->vertex_data[vertex] = data;
    }
}

int find(Graph *g, int i) {
    if (g->parent[i] == i) {
        return i;
    }
    return find(g, g->parent[i]);
}

void union_vertices(Graph *g, int x, int y) {
    int xRoot = find(g, x);
    int yRoot = find(g, y);
    printf("Union: %c + %c\n", g->vertex_data[x], g->vertex_data[y]);
    g->parent[xRoot] = yRoot;
}

bool is_cyclic(Graph *g) {
    for (int i = 0; i < g->size; i++) {
        for (int j = i + 1; j < g->size; j++) {
            if (g->adj_matrix[i][j]) {
                int x = find(g, i);
                int y = find(g, j);
                if (x == y) {
                    return true;
                }
                union_vertices(g, x, y);
            }
        }
    }
    return false;
}

void free_graph(Graph *g) {
    for (int i = 0; i < g->size; i++) {
        free(g->adj_matrix[i]);
    }
    free(g->adj_matrix);
    free(g->vertex_data);
    free(g->parent);
    free(g);
}

int main() {
    Graph *g = create_graph(7);

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_edge(g, 1, 0); // B - A
    add_edge(g, 0, 3);  // A - D
    add_edge(g, 0, 2);  // A - C
    add_edge(g, 2, 3);  // C - D
    add_edge(g, 3, 4);  // D - E
    add_edge(g, 3, 5);  // D - F
    add_edge(g, 3, 6);  // D - G
    add_edge(g, 4, 5);  // E - F

printf("Graph has cycle: %s\n", is_cyclic(g) ? "true" : "false");

free_graph(g);
    return 0;
}

//C

public class Main {

public static void main(String[] args) {
        Graph g = new Graph(7);

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.addEdge(1, 0); // B - A
        g.addEdge(0, 3); // A - D
        g.addEdge(0, 2); // A - C
        g.addEdge(2, 3); // C - D
        g.addEdge(3, 4); // D - E
        g.addEdge(3, 5); // D - F
        g.addEdge(3, 6); // D - G
        g.addEdge(4, 5); // E - F

System.out.println("Graph has cycle: " + g.isCyclic());
    }

public static class Graph {
        private int[][] adjMatrix;
        private char[] vertexData;
        private int[] parent;
        private int size;
    
        public Graph(int size) {
            this.size = size;
            this.adjMatrix = new int[size][size];
            this.vertexData = new char[size];
            this.parent = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }
    
        public void addEdge(int u, int v) {
            if (u >= 0 && u < size && v >= 0 && v < size) {
                adjMatrix[u][v] = 1;
                adjMatrix[v][u] = 1;
            }
        }
    
        public void addVertexData(int vertex, char data) {
            if (vertex >= 0 && vertex < size) {
                vertexData[vertex] = data;
            }
        }
    
        private int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return find(parent[i]);
        }
    
        private void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            System.out.println("Union: " + vertexData[x] + " + " + vertexData[y]);
            parent[xRoot] = yRoot;
            System.out.println(java.util.Arrays.toString(parent) + "\n");
        }
    
        public boolean isCyclic() {
            for (int i = 0; i < size; i++) {
                for (int j = i + 1; j < size; j++) {
                    if (adjMatrix[i][j] == 1) {
                        int x = find(i);
                        int y = find(j);
                        if (x == y) {
                            return true;
                        }
                        union(x, y);
                    }
                }
            }
            return false;
        }
    }
}

//Java