DEV Community

Igor Dubinin
Igor Dubinin

Posted on • Edited on

Graph data structure JS

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.

For example there are few cities M, R, T, K, B, O, S and routes between these M-R, M-T, M-K, M-B, M-S, M-O, R-T, T-K, T-O, K-B, B-S, B-O.

There are two ways to represent graph:

Adjacency matrix

M R T K B O S
M 0 1 1 1 1 1 1
R 1 0 1 0 0 0 0
T 1 1 0 1 0 1 1
K 1 0 1 0 1 0 0
B 1 0 0 1 0 1 1
O 1 0 1 0 1 0 0
S 1 0 0 0 1 0 0

List of vertex

{
    M: [ R, T, K, B, S, O ],
    R: [ M, T ],
    T: [ M, R, K, O ],
    K: [ M, T, B ],
    B: [ M, K, S, O ],
    O: [ M, B ],
    S: [ M, B ]
}
Enter fullscreen mode Exit fullscreen mode

Classes for vertex and graph

class Vertex {
    /**
     * new vertex
     * @param {String} p.id - id of vertex
     */
    constructor(p) {
        this.id = p.id;
        this.connectedTo = new Set();
        this.visited = false;
        this.parent = undefined;
    }
    /**
     * add adjacency to another vertex
     * @param {String} p.id - id of vertex
     */
    addAdjacency(p) {
        if (this.connectedTo.has(p.id)) {
            return;
        }
        this.connectedTo.add(p.id);
    }
}

class Graph {
    /**
     * new graph
     */
    constructor(p) {
        this.verticesById = new Map();
    }

    /**
     * add new vertex to graph
     * @param {String} p.id - id of new vertex
     */
    addVertex(p) {
        const vertex = new Vertex({ id: p.id });
        this.verticesById.set(p.id, vertex)
        return vertex;
    }

    /**
     * add edge between two vertices
     * @param {String} p.from - id from vertex from
     * @param {String} p.to - id from vertex to
     */
    addEdge(p) {
        if (p.from === p.to) {
            return;
        }
        this.verticesById.get(p.from).addAdjacency({ id: p.to });
        this.verticesById.get(p.to).addAdjacency({ id: p.from });
    }

    /**
     * Search of vertex
     * @param {Object} p.strategy - strategy for searching
     * @param {String} p.from - id from
     * @param {String} p.to - id to
     */
    search({ strategy, from, to }) {
        this.verticesById.forEach(v => {
            v.visited = false;
            v.parent = undefined;
        });
        this.strategy = new strategy({ graph: this });
        return this.strategy.search({ from, to });
    }

    /**
     * Show path from vertex
     * @param {String} p.from - id from
     */
    traverse(p) {
        const vertex = this.verticesById.get(p.from);
        console.log(vertex);
        if (! vertex.parent) {
            console.log(this.strategy.constructor.name);
            return;
        }
        this.traverse({ from: vertex.parent });
    }
}
Enter fullscreen mode Exit fullscreen mode

There are few simple algorithm for searching in graph data structures.

class Strategy {
    /**
     * new strategy for searching of vertex
     * @param {Object} p.graph - graph for search
     */
    constructor(p) {
        this.graph = p.graph;
    }
    /**
     * search algorithm
     * @param {String} p.from - id from
     * @param {String} p.to - id to
     */
    search(from, to) {
        return;
    }
}
Enter fullscreen mode Exit fullscreen mode

Breadth-first search (BFS) - it starts searching from children of vertex, after check all of them, begin to search into all children of first child, after into children of second child and so on. Algorithm of bfs with a queue for sequential traverse of children vertices.

class BreadthFirstSearchStrategy extends Strategy {
    /**
     * @param {String} p.from - id vertex from
     * @param {String} p.to - id vertex to
     */
    search(p) {
        let result;
        const q = [ this.graph.verticesById.get(p.from) ];

        while (q.length) {
            const vertex = q.shift();

            vertex.visited = true;
            if (vertex.id === p.to) {
                result = vertex;
                break;
            }

            vertex.connectedTo.forEach((v, k) => {
                const child = this.graph.verticesById.get(k);
                if (child.visited || child.parent) {
                    return;
                }

                child.parent = vertex.id;
                q.push(child);
            });
        }

        return result;
    }
}
Enter fullscreen mode Exit fullscreen mode

Depth-first search (DFS) this algorithm begin searching from children of vertex, but after check of first children, apply search to children of this vertex and move into deep of graph.

Possible to implement dfs with stack.

class DepthFirstSearchStrategy extends Strategy {
    /**
     * @param {String} p.from - id vertex from
     * @param {String} p.to - id vertex to
     */
    search(p) {
        let result;
        const s = [ this.graph.verticesById.get(p.from) ];

        while (s.length) {
            const vertex = s.pop();

            vertex.visited = true;
            if (vertex.id === p.to) {
                result = vertex;
                break;
            }

            vertex.connectedTo.forEach((v, k) => {
                const child = this.graph.verticesById.get(k);
                if (child.visited || child.parent) {
                    return;
                }

                child.parent = vertex.id;
                s.push(child);
            });
        }

        return result;
    }
}
Enter fullscreen mode Exit fullscreen mode

And possible to implement dfs with recursion.

class DepthFirstSearchRecursionStrategy extends Strategy {
    constructor(p) {
        super(p);
        this.result;
        this.to;
    }
    /**
     * @param {String} p.from - id vertex from
     * @param {String} p.to - id vertex to
     */
    search(p) {
        this.to = p.to;
        const vertex = this.graph.verticesById.get(p.from);
        this.searchRecursion({ vertex });
        return this.result;
    }

    /**
     * @param p.vertex - vertex
     */
    searchRecursion(p) {
        if (this.result) {
            return;
        }

        p.vertex.visited = true;
        if (p.vertex.id === this.to) {
            this.result = p.vertex;
            return;
        }

        p.vertex.connectedTo.forEach(id => {
            const vertex = this.graph.verticesById.get(id);
            if (vertex.visited || vertex.parent) {
                return;
            }
            vertex.parent = p.vertex.id;
            this.searchRecursion({ vertex });
        });
    }
}
Enter fullscreen mode Exit fullscreen mode

Search of path between cities.

// Creation of graph
const graph = new Graph();

// Insertion of values
[ 'M', 'R', 'T', 'K', 'B', 'O', 'S' ].forEach(v => graph.addVertex({ id: v }));
[
    {from: "M", to: "R"},
    {from: "M", to: "T"},
    {from: "M", to: "K"},
    {from: "M", to: "B"},
    {from: "M", to: "S"},
    {from: "R", to: "T"},
    {from: "T", to: "K"},
    {from: "T", to: "O"},
    {from: "K", to: "B"},
    {from: "B", to: "S"},
    {from: "B", to: "O"},
].forEach(v => graph.addEdge(v));

// Applying several way of search
const searchBreadth = graph.search({ strategy: BreadthFirstSearchStrategy, from: 'R', to: 'S' });
graph.traverse({ from: searchBreadth.id });

const searchDepth = graph.search({ strategy: DepthFirstSearchStrategy, from: 'R', to: 'S' });
graph.traverse({ from: searchDepth.id });

const searchDepthRecursion = graph.search({ strategy: DepthFirstSearchRecursionStrategy, from: 'R', to: 'S' });
graph.traverse({ from: searchDepthRecursion.id });
Enter fullscreen mode Exit fullscreen mode

Top comments (0)