Список ребер

При задании графа списком ребер каждое его ребро представляется парой инцидентных ему вершин. Это представление реализуется 2-мя массивами: .

Каждый элемент первого списка есть номер (метка) начальной вершины, соответствующий элемент второго списка – номер (метка) конечной вершины. При этом порядок (начало, конец) существенен только для орграфов. Нумерация вершин произвольна и фиксирована, порядок перечисления ребер произвольный. Этот способ задания – самый универсальный – можно задавать псевдо- и мультиграфы, смешанные и взвешенные графы. Для весов ребер необходимо задать еще один список.

Сложность задания графа списком ребер – O(2 m).