Представление графов в ЭВМ

Наиболее распространены следующие 4 метода представления графов в ЭВМ:

- Матрица смежности,

- Матрица инцидентности,

- Списки смежности вершин,

- Списки смежности дуг.

Вы уже имеете представление о представлении графа матрицами смежности и инцидентности (Тема 11, пункт 1). Поясним суть списков смежности вершин.

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

Представление графа с помощью массива структур представляется в виде записей: .

Тема 12. Компоненты связности и объединение графов. Оценка числа ребер через число вершин и число компонентов связности. Вершинная и реберная связность. Мосты и блоки.