Списки смежности
Список ребер
Этот способ задания графов наиболее удобен для внешнего представления входных данных. Пусть каждая строка входного файла содержит информацию об одном ребре (дуге):
<номер_начальной_вершины> <номер_конечной_вершины> [<вес_ребра>]В качестве примера приведем списки ребер (дуг), задающие те же три графа с рис. 11.5, рис. 11.6 и рис. 11.7 (см. рис. 11.9).
Таблица 11.9. Примеры списков ребер (дуг) | ||
a b a c b cb dc dc ff db f | 1 21 43 13 23 54 3 | a b 1a c 10b c 2b d 10c d 3 |
Если задается ориентированный граф, то номера вершин понимаются как упорядоченная пара, а если граф неориентированный - как неупорядоченная.
Этот способ задания графов подразумевает, что для каждой вершины будет указан список всех смежных с нею вершин (для орграфа - список вершин, являющихся концами исходящих дуг). Конкретный формат входного файла, содержащего списки смежности, необходимо обговорить отдельно. Например, в нашем случае начальная вершина отделена от списка смежности двоеточием:
<номер_начальной_вершины>: <номера_смежных_вершин>Наиболее естественно применять этот способ для задания орграфов, однако и для остальных вариантов он тоже подходит.
В качестве примера приведем списки смежности, задающие все те же три графа, изображенные на рис. 11.5, рис. 11.6 и рис. 11.7 (см. рис. 11.10).
Таблица 11.10. Примеры списков смежности | ||
a: b cb: c d fc: d fd: f | 1: 2 4 3: 1 2 54: 3 | b: a 1 c 2 d 10c: a 10 d 3 |