Матрица инциденций

Данное представление пригодно для описания мультиграфов – кратных ребер, обычных графов с петлями (но не орграфов!), взвешенных графов.

Сложность задания – O(mn). Практически этот способ малопригоден – матрица инциденций содержит в каждом столбце лишь два ненулевых элемента.

Списки смежности.

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

Орграф можно задавать как списком потомков Г⁺, так и списком предшественников (родителей) Г^–.

Сложность – O(n+m).