DEV Community

Kurapati Mahesh
Kurapati Mahesh

Posted on • Updated on

Is it DFS using adjacency Matrix?

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));
Enter fullscreen mode Exit fullscreen mode
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]
Enter fullscreen mode Exit fullscreen mode

Thanks! Happy Learning :)

Top comments (0)