I am little new to Graphs part in data structures. I am trying to implement DFS using adjacency matrix. I have looked for many references in Google but I don't find a better one rather I got the approaches to implement them. Hence, using them I started implementing DFS.
I am posting the code here. I have written using javascript.
Correct me if I am wrong in any way or suggest me the best way or provide me the best reference to learn.
class Graph {
constructor(size) {
this.matrix = [];
this.visited = {};
this.result = [];
const initLength = size;
while (size > 0) {
const arr = [];
arr.length = initLength;
arr.fill(0);
this.matrix.push(arr);
size--;
}
}
addEdge(source, destination) {
this.matrix[source][destination] = 1;
this.matrix[destination][source] = 1;
}
dfs(start) {
this.visited[start] = true;
this.result.push(start);
for (let i = 0; i < this.matrix[start].length; i++) {
if (this.matrix[start][i] == 1 && (!this.visited[i])) {
this.dfs(i);
}
}
return this.result;
}
}
const r = new Graph(5);
r.addEdge(0, 1);
r.addEdge(1, 2);
r.addEdge(2, 3);
r.addEdge(0, 3);
r.addEdge(0, 2);
r.addEdge(0, 4);
console.log(JSON.stringify(r.matrix));
console.log(r.dfs(0));
Output:
[[0,1,1,1,1],[1,0,1,0],[1,1,0,1],[1,0,1,0],[1,0,0,0]]
[0, 1, 2, 3, 4]
Thanks! Happy Learning :)
Top comments (0)