Graph Representation

☝️This is a graph. How? A graph is a collection of nodes and edges in a way that nodes are connected by edges.

How does the computer understand what is a graph? and what are nodes and edges?

There are two commonly used techniques for representing graphs

• Adjacency Matrix
• Adjacency List

Adjacency Matrix

An Adjacency matrix is the square matrix (same number of rows and columns) of size N x N where N is the number of the nodes. each vertex of a matrix is either 0 or 1 depending on whether there is an edge between nodes.

If you look at the graph, node "A" has the edge with node "B" and vice versa. To represent this in the matrix we write 1 in the front row "A" and column "B" And if there is no edge between nodes we write 0.

class Graph {
    constructor(totalNodes) {
        this.nodes = totalNodes;
        this.adjMatrix = [];
    }
    initialize() {
        for (let row = 0; row < this.nodes; row++) {
            this.adjMatrix.push([]);
            for (let column = 0; column < this.nodes; column++) {
                this.adjMatrix[row][column] = 0
            }
        }
    }
    addEdge(source, destination) {
        this.adjMatrix[source][destination] = 1;
        this.adjMatrix[destination][source] = 1;
    }
    display() {
        console.log(this.adjMatrix);
    }
}

const totalNodes = 6
let graph = new Graph(totalNodes);
graph.initialize();
graph.display();

graph.addEdge(0, 1);
graph.addEdge(0, 3);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(2, 5);
graph.addEdge(3, 4);
graph.addEdge(3, 5);
graph.addEdge(4, 5);

console.log('\nAdjacency Matrix')
graph.display();

/*
OUTPUT:

[
  [ 0, 1, 0, 1, 1, 0 ],
  [ 1, 0, 1, 1, 0, 0 ],
  [ 0, 1, 0, 1, 0, 1 ],
  [ 1, 1, 1, 0, 1, 1 ],
  [ 1, 0, 0, 1, 0, 1 ],
  [ 0, 0, 1, 1, 1, 0 ]
]
*/

Adjacency List

An adjacency list is the list of adjacent nodes(nodes that shares an edge with another node). Node "B" & Node "D" shares and edge with Node "A". so the adjacency list of Node "A" is [B, D]

class Graph {
    constructor() {
        this.adjList = new Map();
    }
    initialize(nodes) {
        for(let node of nodes){
            this.addNode(node);
        }
    }
    addNode(node) {
        this.adjList.set(node, []);
    }
    addEdge(source, destination) {
        this.adjList.get(source).push(destination);
    }
    display() {
        for (let [key, value] of this.adjList) {
            console.log(`${key}: ${value}`);
        }
    }
}

let nodes = ["A", "B", "C", "D", "E", "F"];

let graph = new Graph();

graph.initialize(nodes);

graph.addEdge("A", "E");
graph.addEdge("A", "D");
graph.addEdge("A", "B");

graph.addEdge("B", "A");
graph.addEdge("B", "D");
graph.addEdge("B", "C");

graph.addEdge("C", "B");
graph.addEdge("C", "D");
graph.addEdge("C", "F");

graph.addEdge("D", "A");
graph.addEdge("D", "B");
graph.addEdge("D", "C");
graph.addEdge("D", "E");
graph.addEdge("D", "F");

graph.addEdge("E", "A");
graph.addEdge("E", "D");
graph.addEdge("E", "F");

graph.addEdge("F", "E");
graph.addEdge("F", "D");
graph.addEdge("F", "C");

graph.display();

/*
OUTPUT: 

A: E,D,B
B: A,D,C
C: B,D,F
D: A,B,C,E,F
E: A,D,F
F: E,D,C

*/