График-это нелинейная структура данных, состоящая из узлов и краев. Узлы иногда также называются вершинами, а края – это линии или дуги, которые соединяют любые два узла на графике.
Например, есть несколько городов M, R, T, K, B, O, S и маршрутов между этими M-R, M-T, M-K, M-B, M-S, M-O, R-T, T-K, T-O, K-B, B-S, B-O.
Есть два способа представления графика:
Матрица смежности
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | M |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | R |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | T |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | K |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 | B |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | O |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | S |
Список вершины
{
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 ]
}
Классы для вершины и графика
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 });
}
}
Существует мало простого алгоритма для поиска в структурах графиков.
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;
}
}
Поиск по ширине (BFS) – он начинает искать детей вершины, после того, как проверить их всех, начинают искать всех детей первого ребенка, после детей второго ребенка и так далее. Алгоритм BFS с очередью для последовательного траверса детей.
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;
}
}
Поиск по глубине (DFS) Этот алгоритм начинает поиск детей вершины, но после проверки первых детей примените поиск детей этой вершины и перейти в глубину графика.
Возможно реализовать DFS со стеком.
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;
}
}
И возможно реализовать DFS с рекурсией.
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 });
});
}
}
Поиск пути между городами.
// 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 });
Оригинал: “https://dev.to/igorok/graph-data-structure-180g”