DEV Community

Kurapati Mahesh
Kurapati Mahesh

Posted on • Edited on

3 2

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 :)

Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay