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): if 0 <= u < self.size and 0 <= v < self.size: self.adj_matrix[u][v] = 1 #self.adj_matrix[v][u] = 1 <- used for undirected Graphs def add_vertex_data(self, vertex, data): if 0 <= vertex < self.size: self.vertex_data[vertex] = data def print_graph(self): print("Adjacency Matrix:") for row in self.adj_matrix: print(' '.join(map(str, row))) print("\nVertex Data:") for vertex, data in enumerate(self.vertex_data): print(f"Vertex {vertex}: {data}") def dfs_util(self, v, visited, recStack): visited[v] = True recStack[v] = True print("Current vertex:",self.vertex_data[v]) for i in range(self.size): if self.adj_matrix[v][i] == 1: if not visited[i]: if self.dfs_util(i, visited, recStack): return True elif recStack[i]: return True recStack[v] = False return False def is_cyclic(self): visited = [False] * self.size recStack = [False] * self.size for i in range(self.size): if not visited[i]: print() #new line if self.dfs_util(i, visited, recStack): return True 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(3, 0) # D -> A g.add_edge(0, 2) # A -> C g.add_edge(2, 1) # C -> B g.add_edge(2, 4) # C -> E g.add_edge(1, 5) # B -> F g.add_edge(4, 0) # E -> A g.add_edge(2, 6) # C -> G g.print_graph() print("\nGraph has cycle:", g.is_cyclic()) #Python
#include
#include
#define SIZE 7 typedef struct { int adjMatrix[SIZE][SIZE]; char vertexData[SIZE]; } Graph; void initGraph(Graph *g) { for (int i = 0; i < SIZE; i++) { for (int j = 0; j < SIZE; j++) { g->adjMatrix[i][j] = 0; } g->vertexData[i] = '\0'; } } void addEdge(Graph *g, int u, int v) { if (u >= 0 && u < SIZE && v >= 0 && v < SIZE) { g->adjMatrix[u][v] = 1; } } void addVertexData(Graph *g, int vertex, char data) { if (vertex >= 0 && vertex < SIZE) { g->vertexData[vertex] = data; } } void printGraph(Graph *g) { printf("Adjacency Matrix:\n"); for (int i = 0; i < SIZE; i++) { for (int j = 0; j < SIZE; j++) { printf("%d ", g->adjMatrix[i][j]); } printf("\n"); } printf("\nVertex Data:\n"); for (int i = 0; i < SIZE; i++) { printf("Vertex %d: %c\n", i, g->vertexData[i]); } } bool dfsUtil(Graph *g, int v, bool visited[], bool recStack[]) { visited[v] = true; recStack[v] = true; printf("Current vertex: %c\n", g->vertexData[v]); for (int i = 0; i < SIZE; i++) { if (g->adjMatrix[v][i] == 1) { if (!visited[i]) { if (dfsUtil(g, i, visited, recStack)) { return true; } } else if (recStack[i]) { return true; } } } recStack[v] = false; return false; } bool isCyclic(Graph *g) { bool visited[SIZE] = {false}; bool recStack[SIZE] = {false}; for (int i = 0; i < SIZE; i++) { if (!visited[i]) { printf("\n"); if (dfsUtil(g, i, visited, recStack)) { return true; } } } return false; } int main() { Graph g; initGraph(&g); 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'); addEdge(&g, 3, 0); // D -> A addEdge(&g, 0, 2); // A -> C addEdge(&g, 2, 1); // C -> B addEdge(&g, 2, 4); // C -> E addEdge(&g, 1, 5); // B -> F addEdge(&g, 4, 0); // E -> A addEdge(&g, 2, 6); // C -> G printGraph(&g); printf("\nGraph has cycle: %s\n", isCyclic(&g) ? "Yes" : "No"); return 0; } //C
public class Main { static class Graph { private int[][] adjMatrix; private char[] vertexData; private int size; public Graph(int size) { this.size = size; this.adjMatrix = new int[size][size]; this.vertexData = new char[size]; } public void addEdge(int u, int v) { if (u >= 0 && u < size && v >= 0 && v < size) { adjMatrix[u][v] = 1; } } public void addVertexData(int vertex, char data) { if (vertex >= 0 && vertex < size) { vertexData[vertex] = data; } } public void printGraph() { System.out.println("Adjacency Matrix:"); for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { System.out.print(adjMatrix[i][j] + " "); } System.out.println(); } System.out.println("\nVertex Data:"); for (int i = 0; i < size; i++) { System.out.println("Vertex " + i + ": " + vertexData[i]); } } private boolean dfsUtil(int v, boolean[] visited, boolean[] recStack) { visited[v] = true; recStack[v] = true; System.out.println("Current vertex: " + vertexData[v]); for (int i = 0; i < size; i++) { if (adjMatrix[v][i] == 1) { if (!visited[i]) { if (dfsUtil(i, visited, recStack)) { return true; } } else if (recStack[i]) { return true; } } } recStack[v] = false; return false; } public boolean isCyclic() { boolean[] visited = new boolean[size]; boolean[] recStack = new boolean[size]; for (int i = 0; i < size; i++) { if (!visited[i]) { System.out.println(); //new line if (dfsUtil(i, visited, recStack)) { return true; } } } return false; } } 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(3, 0); // D -> A g.addEdge(0, 2); // A -> C g.addEdge(2, 1); // C -> B g.addEdge(2, 4); // C -> E g.addEdge(1, 5); // B -> F g.addEdge(4, 0); // E -> A g.addEdge(2, 6); // C -> G g.printGraph(); System.out.println("\nGraph has cycle: " + g.isCyclic()); } } //Java
Python result:
C result:
Java result:
Adjacency Matrix:
0 0 1 0 0 0 0
0 0 0 0 0 1 0
0 1 0 0 1 0 1
1 0 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
Vertex Data:
Vertex 0: A
Vertex 1: B
Vertex 2: C
Vertex 3: D
Vertex 4: E
Vertex 5: F
Vertex 6: G
Current vertex: A
Current vertex: C
Current vertex: B
Current vertex: F
Current vertex: E
Graph has cycle: True
Adjacency Matrix:
0 0 1 0 0 0 0
0 0 0 0 0 1 0
0 1 0 0 1 0 1
1 0 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
Vertex Data:
Vertex 0: A
Vertex 1: B
Vertex 2: C
Vertex 3: D
Vertex 4: E
Vertex 5: F
Vertex 6: G
Current vertex: A
Current vertex: C
Current vertex: B
Current vertex: F
Current vertex: E
Graph has cycle: Yes
Adjacency Matrix:
0 0 1 0 0 0 0
0 0 0 0 0 1 0
0 1 0 0 1 0 1
1 0 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
Vertex Data:
Vertex 0: A
Vertex 1: B
Vertex 2: C
Vertex 3: D
Vertex 4: E
Vertex 5: F
Vertex 6: G
Current vertex: A
Current vertex: C
Current vertex: B
Current vertex: F
Current vertex: E
Graph has cycle: true