- Граф — это набор вершин (узлов) и связей между ними (рёбер).
- Виды графов:
- ориентированный — граф, в котором можно перемещаться по рёбрам в обоих направлениях;
- неориентированный — граф, граф, по некоторым рёбрам которого можно перемещаться только в одном направлении.
- Взвешенный граф — граф, в котором каждому ребру приписана числовая характеристика (вес).
- Матрица смежности невзвешенного графа — это таблица n × n (число вершин графа), заполненная единицами и нулями:
- 1 — существует ребро из вершины i в вершину j;
- 0 — не существует ребра из вершины i в вершину j.
- Во взвешенном графе ячейки таблицы заполняются весами рёбер.