Матрица смежности — одна из основных структур данных, которые используются для представления графов в компьютерных программах. 35

С помощью матрицы смежности хранят рёбра графа. 1 Для этого используют двумерную матрицу, каждый элемент которой равен 1, если две вершины являются смежными, и 0 — в противном случае. 1 В случае неориентированного графа матрица симметрична относительно главной диагонали, а сумма каждой строчки и каждого столбца равна степени вершины. 1

Некоторые особенности использования матрицы смежности:

• Предпочтительно применять для неразреженных графов с большим числом рёбер. 35 Если граф разрежён, то большая часть памяти будет тратиться на хранение нулей. 3
• В алгоритмах, работающих со взвешенными графами, элементы матрицы смежности вместо чисел 0 и 1, указывающих на присутствие или отсутствие ребра, часто содержат веса самих рёбер. 35
• В некоторых приложениях с каждым ребром связывают различную информацию. 2 В таких случаях матрицу смежности можно обобщить, позволив ей хранить любую информацию, а не только булевские значения. 2