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)