Graph in Javascript
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. More formally a Graph can be defined as, A Graph consisting of a finite set of vertices(or nodes) and a set of edges that connect a pair of nodes.
In the graph data structure, a graph representation is a technique to store graphs in the memory of the computer. There are many ways to represent a graph:
The following two are the most commonly used representations of a graph.
- Adjacency Matrix: An adjacency matrix represents a graph as a matrix of boolean values (0s and 1s). In a computer, a finite graph can be represented as a square matrix, where the boolean value indicates if two vertices are connected directly.
- Adjacency List: An adjacency list represents a graph as an array of linked lists where an index of the array represents a vertex and each element in its linked list represents the other vertices that are connected with the edges, or say its neighbor.
Graph Operations:
- Add/Remove Vertex: Add or remove a vertex in a graph.
- Add/Remove Edge: Add or remove an edge between two vertices.
- Check if the graph contains a given value.
- Find the path from one vertex to another vertex.
Below is the implementation of Graph in javascript:
// create a graph class
class Graph {
// defining vertex array and
// adjacent list
constructor(noOfVertices)
{
this.noOfVertices = noOfVertices;
this.AdjList = new Map();
}
// functions to be implemented
// add vertex to the graph
addVertex(v)
{
// initialize the adjacent list with a
// null array
this.AdjList.set(v, []);
}
// add edge to the graph
addEdge(v, w)
{
// get the list for vertex v and put the
// vertex w denoting edge between v and w
this.AdjList.get(v).push(w);
// Since graph is undirected,
// add an edge from w to v also
this.AdjList.get(w).push(v);
}
// Prints the vertex and adjacency list
printGraph()
{
// get all the vertices
var get_keys = this.AdjList.keys();
// iterate over the vertices
for (var i of get_keys)
{
// get the corresponding adjacency list
// for the vertex
var get_values = this.AdjList.get(i);
var conc = "";
// iterate over the adjacency list
// concatenate the values into a string
for (var j of get_values)
conc += j + " ";
// print the vertex and its adjacency list
console.log(i + " -> " + conc);
}
}
}
// Using the above implemented graph class
var g = new Graph(6);
var vertices = [ 'A', 'B', 'C', 'D', 'E', 'F' ];
// adding vertices
for (var i = 0; i < vertices.length; i++) {
g.addVertex(vertices[i]);
}
// adding edges
g.addEdge('A', 'B');
g.addEdge('A', 'D');
g.addEdge('A', 'E');
g.addEdge('B', 'C');
g.addEdge('D', 'E');
g.addEdge('E', 'F');
g.addEdge('E', 'C');
g.addEdge('C', 'F');
// prints all vertex and
// its adjacency list
// A -> B D E
// B -> A C
// C -> B E F
// D -> A E
// E -> A D F C
// F -> E C
g.printGraph();
Output
A -> B D E B -> A C C -> B E F D -> A E E -> A D F C F -> E C
Learn Data Structures with Javascript | DSA using JavaScript Tutorial
JavaScript (JS) is the most popular lightweight, interpreted compiled programming language, and might be your first preference for Client-side as well as Server-side developments. But have you thought about using Javascript for DSA? Learning Data Structures and Algorithms can be difficult when combined with Javascript. For this reason, we have brought to you this detailed DSA tutorial on how to get started with Data Structures with Javascript from scratch.
Table of Content
- What is Data Structure?
- How to start learning Data Structures with Javascript?
- Learn about Complexities
- Learn Data Structures with JavaScript
- Array in javascript
- String in javascript
- Linked List in Javascript
- Stack in Javascript
- Queue in Javascript
- Tree in Javascript
- Priority Queue in Javascript
- Map in Javascript
- Set in Javascript
- Graph in Javascript
Contact Us