Чем отличается реализация списка смежности от матрицы смежности?

Основное отличие реализации списка смежности от матрицы смежности заключается в способе представления графа. prog-cpp.ru habr.com

Матрица смежности — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1. prog-cpp.ru Число строк матрицы смежности равно числу столбцов и соответствует количеству вершин графа. prog-cpp.ru 0 соответствует отсутствию ребра, 1 — наличию ребра. prog-cpp.ru Матрица удобна для представления плотных графов, в которых число рёбер близко к максимально возможному числу рёбер (у полного графа). habr.com

Список смежности — это список (массив), в котором указаны вершины графа, и каждый из них имеет ссылку на смежные с ним вершины. habr.com Такой список можно представить в виде таблицы, столбцов в которой — 2, а строк — не больше, чем вершин в графе. prog-cpp.ru В каждой строке в первом столбце указана вершина выхода, а во втором столбце — список вершин, в которые входят рёбра из текущей вершины. prog-cpp.ru Список смежности подходит для разреженных графов, в которых число рёбер намного меньше максимально возможного числа рёбер (у полного графа). habr.com

Таким образом, матрица смежности лучше для плотных графов, а список смежности — для разреженных. prog-cpp.ru habr.com