Списки смежности
Этот способ задания графов подразумевает, что для каждой вершины будет указан список всех смежных с нею вершин (для орграфа - список вершин, являющихся концами исходящих дуг). Конкретный формат входного файла, содержащего списки смежности, необходимо обговорить отдельно. Например, в нашем случае начальная вершина отделена от списка смежности двоеточием:
<номер_начальной_вершины>: <номера_смежных_вершин>
Наиболее естественно применять этот способ для задания орграфов, однако и для остальных вариантов он тоже подходит.
В качестве примера приведем списки смежности, задающие все те же три графа, изображенные на рис. 11.5, рис. 11.6 и рис. 11.7 (см. рис. 11.10).
| a: b c b: c d f c: d f d: f | 1: 2 4 3: 1 2 5 4: 3 | b: a 1 c 2 d 10 c: a 10 d 3 |
