Программирование на языке Pascal

       

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


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

<номер_начальной_вершины>: <номера_смежных_вершин>

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

В качестве примера приведем списки смежности, задающие все те же три графа, изображенные на рис. 11.5, рис. 11.6 и рис. 11.7 (см. рис. 11.10).

Таблица 11.10. Примеры списков смежности

a: b c b: c d f c: d f d: f1: 2 4 3: 1 2 5 4: 3b: a 1 c 2 d 10 c: a 10 d 3



Содержание раздела