Представление графа в виде списка дуг

 

Иногда используются и другие представления графов, например, для случая очень разреженных графов, когда при большом количестве N вершин графа число дуг существенно меньше NXN, например, порядка N. Одним из таких представлений является представление в виде списка дуг, когда все дуги графа собраны в единый список, в каждом элементе которого записана информация об обоих концах дуги, а также, возможно, о нагрузке на дугу (рис.3).

 

Рис.3. Граф и его представление в виде списка дуг.

 

В листинге приведено представление графа в виде списка дуг. Такое представление будем называть A-графом от слова Arc— дуга. Список дуг представлен списком элементов, каждый из которых содержит два целых числа— номера концов дуги. В данной реализации список не представлен в виде отдельного описания класса. Вместо этого описание элемента такого списка— дуги— внесено прямо в описание класса для представления A-графа, а реализации операций над списком просто являются частью реализации операций над дугами графа.

Операция добавления дуги в этом представлении — это просто операция добавления одного элемента в конец списка, и реализуется она сравнительно эффективно. Напротив, при выполнении операции поиска дуги может потребоваться просмотреть весь список. Разумеется, настолько же неэффективной будет и операция удаления дуги.