ехнологію" використання тієї чи іншої бібліотеки у прикладних програмах. p> Нижче перераховані структури зберігання графів будуть розглянуті більш докладно, але перед цим необхідно зробити наступне зауваження. У теорії графів вершини і ребра графів, як правило, позбавлені індивідуальності: при такому підході граф можна задати, наприклад, булевою матрицею суміжності, де логічна одиниця на перетині i-го рядка і j-го стовпця означає існування ребра (або дуги) між i-ої та j-ої вершинами графа. У той же час, у всіх розглянутих бібліотеках вершини і ребра графа вважаються унікальними об'єктами (тут термін "об'єкт" вживається в контексті об'єктно-орієнтованого програмування), які розрізняються, принаймні, тим, що кожен з них займає окрему ділянку в оперативній пам'яті ЕОМ. Об'єкт-вершина може містити або не містити які-небудь дані; об'єкт-ребро містить, як мінімум, покажчики на інцідентние йому вершини. Якщо підходити з технологічної точки зору, то наявність унікальних об'єктів-вершин і об'єктів-ребер підвищує зручність реалізації та ефективність багатьох алгоритмів (Хоча і неекономічно в сенсі витрат оперативної пам'яті). Існує і більш фундаментальна причина: при вирішенні прикладних завдань вершини графа, а іноді і його ребра, відповідають реальним об'єктам предметної області. Таким чином, структури зберігання графів в об'єктно-орієнтованої бібліотеці для роботи з графами забезпечують зберігання не тільки "математичного" графа, але й об'єктів, що становлять вершини і ребра цього графа. Ще одне зауваження необхідно зробити щодо використання списків і/або масивів: ці структури даних будуть вважатися взаємозамінними, поки виклад не торкнеться конкретних бібліотек. p> Списки вершин і ребер
Граф представляється у вигляді двох списків, один з яких містить покажчики на його вершини, другий - на ребра (як завжди, кожне ребро зберігає в собі покажчики на інцідентние йому вершини). Дана структура зберігання забезпечує ефективне додавання в граф вершин і ребер, а також ітерацію по вершинах і ребрах. У той же час, це подання незручно, коли необхідно визначити ребра, інцідентние заданої вершині графа. p> Списки суміжності
Граф представляється списком входять до нього вершин. У свою чергу, кожна вершина містить список інцідентних їй ребер (або списки вхідних і вихідних дуг у разі орграфов). Дане подання забезпечує ефективне додавання в граф вершин і ребер, ітерацію по вершинах графа і доступ до ребер, інцідентним заданої вершині, але не підтримує ітерацію по ребрах графа. p> Матриці суміжності
Граф задається квадратною матрицею розмірності NxN, де N - кількість вершин у графі; на перетині i-го стовпця і j-го рядка матриці знаходиться або покажчик на ребро, що з'єднує вершини i і j, якщо ці вершини інцидентні, або nil, якщо вони не інцидентні. Вершини можуть або зберігатися в окремому списку, або тільки в складі інцідентних їм ребер (у разі зв'язкових графів). Це пода...
