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 ]
}
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 });
}
}
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;
}
}
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;
}
}
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;
}
}
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 });
});
}
}
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 });
Top comments (0)