Graph Representation

Graph Representation

GraphRepresentationSingleGraph.png ☝️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

GraphRepresentationAdjacencyMatrix.png

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.

GraphRepresentationAdjacencyMatrixHowToWrite.png

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

Group 12adjacency_matrix.png

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

*/

Did you find this article valuable?

Support saud chougle by becoming a sponsor. Any amount is appreciated!