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

Список ребер

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

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

Если задается ориентированный граф, то номера вершин понимаются как упорядоченная пара, а если граф неориентированный - как неупорядоченная.

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

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

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