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 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
#include
#include
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
Python result:
C result:
Java result:
Union: A + B
[1, 1, 2, 3, 4, 5, 6]
Union: B + C
[1, 2, 2, 3, 4, 5, 6]
Union: C + D
[1, 2, 3, 3, 4, 5, 6]
Graph has cycle: True
Union: A + B
Union: B + C
Union: C + D
Graph has cycle: true
Union: A + B
[1, 1, 2, 3, 4, 5, 6]
Union: B + C
[1, 2, 2, 3, 4, 5, 6]
Union: C + D
[1, 2, 3, 3, 4, 5, 6]
Graph has cycle: true