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 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 bfs(self, start_vertex_data): queue = [self.vertex_data.index(start_vertex_data)] visited = [False] * self.size visited[queue[0]] = True while queue: current_vertex = queue.pop(0) print(self.vertex_data[current_vertex], end=' ') for i in range(self.size): if self.adj_matrix[current_vertex][i] == 1 and not visited[i]: queue.append(i) visited[i] = True 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(0, 3) # A - D g.add_edge(0, 4) # A - E g.add_edge(4, 2) # E - C g.add_edge(2, 5) # C - F g.add_edge(2, 1) # C - B g.add_edge(2, 6) # C - G g.add_edge(1, 5) # B - F g.print_graph() print("\nBreadth First Search starting from vertex D:") g.bfs('D') #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; g->adjMatrix[v][u] = 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]); } } void bfs(Graph *g, char startVertexData) { bool visited[SIZE] = {false}; int queue[SIZE], queueStart = 0, queueEnd = 0; int startVertex = -1; for (int i = 0; i < SIZE; i++) { if (g->vertexData[i] == startVertexData) { startVertex = i; break; } } if (startVertex != -1) { queue[queueEnd++] = startVertex; visited[startVertex] = true; while (queueStart < queueEnd) { int currentVertex = queue[queueStart++]; printf("%c ", g->vertexData[currentVertex]); for (int i = 0; i < SIZE; i++) { if (g->adjMatrix[currentVertex][i] == 1 && !visited[i]) { queue[queueEnd++] = i; visited[i] = true; } } } } } 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, 0, 3); // A - D addEdge(&g, 0, 4); // A - E addEdge(&g, 4, 2); // E - C addEdge(&g, 2, 5); // C - F addEdge(&g, 2, 1); // C - B addEdge(&g, 2, 6); // C - G addEdge(&g, 1, 5); // B - F printGraph(&g); printf("\nBreadth First Search starting from vertex D:\n"); bfs(&g, 'D'); return 0; } //C
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; adjMatrix[v][u] = 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[] row : adjMatrix) { for (int cell : row) { System.out.print(cell + " "); } System.out.println(); } System.out.println("\nVertex Data:"); for (int i = 0; i < size; i++) { System.out.println("Vertex " + i + ": " + vertexData[i]); } } public void bfs(char startVertexData) { boolean[] visited = new boolean[size]; int[] queue = new int[size]; int queueStart = 0; int queueEnd = 0; int startVertex = new String(vertexData).indexOf(startVertexData); queue[queueEnd++] = startVertex; visited[startVertex] = true; while (queueStart < queueEnd) { int currentVertex = queue[queueStart++]; System.out.print(vertexData[currentVertex] + " "); for (int i = 0; i < size; i++) { if (adjMatrix[currentVertex][i] == 1 && !visited[i]) { queue[queueEnd++] = i; visited[i] = true; } } } } } 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(3, 0); // D - A g.addEdge(0, 2); // A - C g.addEdge(0, 3); // A - D g.addEdge(0, 4); // A - E g.addEdge(4, 2); // E - C g.addEdge(2, 5); // C - F g.addEdge(2, 1); // C - B g.addEdge(2, 6); // C - G g.addEdge(1, 5); // B - F g.printGraph(); System.out.println("\nBreadth First Search starting from vertex D:"); g.bfs('D'); } } //Java
Python result:
C result:
Java result:
Adjacency Matrix:
0 0 1 1 1 0 0
0 0 1 0 0 1 0
1 1 0 0 1 1 1
1 0 0 0 0 0 0
1 0 1 0 0 0 0
0 1 1 0 0 0 0
0 0 1 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
Breadth First Search starting from vertex D:
D A C E B F G
Adjacency Matrix:
0 0 1 1 1 0 0
0 0 1 0 0 1 0
1 1 0 0 1 1 1
1 0 0 0 0 0 0
1 0 1 0 0 0 0
0 1 1 0 0 0 0
0 0 1 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
Breadth First Search starting from vertex D:
D A C E B F G
Adjacency Matrix:
0 0 1 1 1 0 0
0 0 1 0 0 1 0
1 1 0 0 1 1 1
1 0 0 0 0 0 0
1 0 1 0 0 0 0
0 1 1 0 0 0 0
0 0 1 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
Breadth First Search starting from vertex D:
D A C E B F G