class Graph {
constructor()
{
this.vertices = [];
this.adjacencyList = {};
}
addVertex(vertex) {
this.vertices.push(vertex);
this.adjacencyList[vertex] = [];
}
addEdge(vertex1, vertex2) {
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
}
dfs(startVertex) {
const
visited = {};
for (let i =
0; i < this.vertices.length; i++) {
visited[this.vertices[i]] = false;
}
this._dfsHelper(startVertex, visited);
}
_dfsHelper(vertex, visited) {
visited[vertex] = true;
console.log(vertex);
const
neighbors = this.adjacencyList[vertex];
for (let i =
0; i < neighbors.length; i++) {
const
neighbor = neighbors[i];
if
(!visited[neighbor]) {
this._dfsHelper(neighbor, visited);
}
}
}
bfs(startVertex) {
const
visited = {};
const queue = [];
for (let i =
0; i < this.vertices.length; i++) {
visited[this.vertices[i]] = false;
}
visited[startVertex] = true;
queue.push(startVertex);
while
(queue.length > 0) {
const
vertex = queue.shift();
console.log(vertex);
const
neighbors = this.adjacencyList[vertex];
for (let i
= 0; i < neighbors.length; i++) {
const
neighbor = neighbors[i];
if
(!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
}
}
}
}
// Example usage:
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'D');
console.log('Depth First Search:');
graph.dfs('A');
console.log('Breadth First Search:');
graph.bfs('A');
Output:-
Depth First Search:
A
B
D
C
Breadth First Search:
A
B
C
D
0 Comments