Всем привет,
Сегодня я буду говорить о структурах данных Graph. Графики используются практически во всех социальных сетях, когда мы моделируем пользователей, а также механизмы рекомендаций. Например, когда Youtube или Netflix рекомендуют вам фильмы, графики обычно остаются за кадром. Итак, что такое график? Граф - это просто набор узлов с ребрами между ними. Графики могут быть как направленными, так и неориентированными. Направленные кромки похожи на улицу с односторонним движением, неориентированные кромки похожи на улицу с двусторонним движением.
Графики - это отличные структуры данных , они используются повсеместно. Некоторые из реальных приложений - это Google Maps, Google Search, Facebook, Twitter и многие другие.
Типы графиков
Условия графика:
Вершина → Узел
Edge → Связь между узлами
Взвешенный график → Если на краях графика есть значения, значит, это взвешенный график.
Невзвешенный график → Если на краях графика нет значений, значит, это взвешенный график.
Ненаправленный граф → Граф с неориентированными краями (например, улица с двусторонним движением).
Вы можете думать об этом примере неориентированного графа как о друзьях по моделированию в Facebook. Когда ваш друг отправляет ваш запрос, если вы принимаете его, вы и ваш друг можете видеть материалы друг друга. Это двусторонние отношения.
Пример неориентированных графов, используемых при картировании
Это пример того, как Google дает вам маршруты,
Направленный граф → Граф только с направленными ребрами (например, улица с односторонним движением).
Вы можете думать об этом как о запросе подписки в Instagram над примером направленного графа. Однако, если вы принимаете запрос, они видят ваши материалы, вы также должны запросить их, если хотите увидеть их профиль.
Хранение графиков
Матрицы смежности
Матрица смежности - это квадратная (NxN) логическая матрица (где N - количество узлов). При этом мы храним информацию в строках и столбцах. Мы можем представить отношения между узлами с помощью матрицы.
Вверху справа матрица, представляющая отношения для левого графика. Если вы хотите увидеть взаимосвязь между узлом A и F, вы можете просто посмотреть на столбец F и строку A. Вы должны увидеть Y, что означает «Да». Это работает в обоих направлениях: сначала вы можете перейти к строке F, а затем к столбцу A, вы получите те же результаты.
Каждый раз, когда вы добавляете новый узел, вам придется добавлять совершенно новую строку и новый столбец.
Список смежности
Это наиболее распространенный способ представления графа. Мы можем использовать хеш-таблицу для хранения структуры данных пары ключ-значение.
Используя хеш-таблицу, мы видим, что A связан с (A, B и A, F). Мы можем сделать то же самое для узла B (B, A и B, C).
Реализация графа с использованием списка смежности
class Graph{
constructor(){
this.adjacencyList = {};
}
addVertex(vertex){
if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}
addEdge(vertex1,vertex2){
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
}
removeEdge(vertex1,vertex2){
this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
v => v !== vertex2
);
this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
v => v !== vertex1
);
}
removeVertex(vertex){
while(this.adjacencyList[vertex].length){
const adjacentVertex = this.adjacencyList[vertex].pop();
this.removeEdge(vertex, adjacentVertex);
}
delete this.adjacencyList[vertex]
}
}
Для сравнения, Список смежности занимает меньше места и является первым при итерации, однако он может быть медленнее при поиске определенных краев. Матрица смежности - это полная противоположность, она занимает больше места и медленнее при итерации по краям, однако быстрее при поиске определенных краев.
Вот и все. Надеюсь, этот блог был вам полезен. Если у вас возникнут какие-либо трудности или вам нужно больше объяснений, я буду более чем счастлив помочь вам. Пожалуйста, свяжитесь со мной в LinkedIn или мой адрес электронной почты [email protected]. Также ознакомьтесь с моим последним блогом Развертывание приложения React на Heroku.
Удачного кодирования :)
Ресурсы:
