Что такое граф?

Что такое граф?

Граф — это математическая абстракция, которая состоит из множества вершин (узлов) и множества ребер, соединяющих пары вершин. Эта структура данных идеально подходит для моделирования отношений между объектами, таких как друзья в социальной сети, маршруты на карте или зависимости в проекте.

Основные понятия

• Вершина (Node/Vertex) — базовый элемент графа, представляющий объект.
• Ребро (Edge) — связь между двумя вершинами.
• Ориентированный граф — ребра имеют направление (например, подписка в Twitter).
• Неориентированный граф — ребра не имеют направления (например, дружба в Facebook).
• Взвешенный граф — каждому ребру присвоен вес (например, расстояние между городами).

Пример реализации на JavaScript

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); // для неориентированного графа
  }
}

const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addEdge('A', 'B');
console.log(graph.adjacencyList); // { A: ['B'], B: ['A'] }

Где применяется

Графы используются в алгоритмах поиска кратчайшего пути (Dijkstra, A*), в социальных сетях для рекомендаций друзей, в системах управления зависимостями (npm, Maven), а также в маршрутизации сетевых пакетов.

Вывод: Графы — это универсальный инструмент для моделирования связей. Их стоит применять везде, где важны отношения между сущностями, особенно в задачах поиска путей, анализа сетей и оптимизации маршрутов.