Матрица смежности помогает в определении связности графа, отображая, есть ли ребро между вершинами. 2

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

Если граф несвязен, то он состоит из нескольких связных подграфов, между которыми нет рёбер, и матрица смежности позволяет выделить эти компоненты связности. 3

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