і i-го рядка з j-м стовпцем матриці записується:
· 1 у випадку, якщо зв'язок «виходить» з вершини,
· - 1, якщо зв'язок «входить» в вершину,
· 0 у всіх інших випадках (тобто якщо зв'язок є петлею або зв'язок не инцидентна вершині).
Даний спосіб є найбільш ємним і незручним для зберігання, але полегшує знаходження циклів в графі.
2.5 Списки суміжних вершин через списки
Більш ефективним способом подання розріджених графів є пов'язані списки, в яких зберігаються інцідентние сусіди кожної вершини. Для роботи зі списками суміжних вершин потрібні покажчики, що вже ускладнює вирішення завдання. Крім того, не у всіх мовах програмування є такий інструмент як покажчики, що може давати додаткові складнощі при реалізації цієї способу зберігання графа.
При роботі зі списками суміжності стає складніше відповісти на питання про приналежність даного ребра (i, j) графу, оскільки для цього необхідно переглядати відповідний список, щоб знайти відповідне ребро. Проте, нерідко зовсім нескладно побудувати алгоритми роботи з графами, не вдаватися до таких запитах. Зокрема, можливий прохід по всіх ребрах графа за один захід, використовуючи обхід завширшки або у глибину, і оновлення ребра в момент його відвідин.
2.6 Списки суміжних вершин через матриці
Списки суміжності також можна реалізувати через матриці, уникаючи, таким чином, роботи з покажчиками. Ми можемо уявити список масивом (або, що еквівалентно, рядком в матриці), ввівши лічильник k числа елементів і поміщаючи їх в перші k елементів масиву. Тепер ми можемо послідовно обійти елементи від першого до останнього, просто збільшуючи лічильник циклу, а не подорожуючи за вказівниками.
На перший погляд, здається, що ця структура даних об'єднала в собі найгірші риси матриць суміжності (великий розмір) і списків суміжності (необхідність пошуку ребер). Тим не менше, існують і плюси. По-перше, цю структуру даних найпростіше запрограмувати, особливо, якщо мова йде про статичних графах, незмінних після побудови. По-друге, проблему з розміром можна вирішити, якщо виділяти рядки кожної вершини динамічно і робити їх відповідного розміру.
2.7 Таблиця ребер
Ще більш простий структурою даних буде масив або зв'язаний список ребер. Працюючи з нею, складніше відповідати на такі питання, як: «Які вершини є сусідніми для x?» - Але вона чудово підходить для певних простих процедур, таких, як алгоритм Крускала остовного дерева мінімальної ваги.
2.8 Модифікована структура даних
Дана структура будується на основі типу даних, який використовується в таких класичних алгоритмах роботи з графами як:
· пошук в ширину;
· пошук в глибину;
· алгоритм Прима;
· алгоритм Дейкстри;
· алгоритм Форда-Фалкерсона;
· алгоритм Беллмана-Форда;
Розглянемо структуру даних і пов'язаних з ними методів, які будуть використовуватися для внутрішнього представлення транспортної мережі. (Мал. 1.2)
Клас Transport Network являє собою верхній рівень транспортної мережі і зберігає в собі наступний набір полів:
· aGraph - зберігає в собі масив графів, що входять в транспортну мережу;
· aVertex - зберігає в собі масив вершин, що входять в транспортну мережу;
· aEdge - зберігає в собі масив ребер, що входять в транспортну мережу;
Малюнок 1.2 - Діаграма зв'язків класів представляють транспортну мережу
Малюнок 1.3 Клас транспортної мережі
· Width - ширина транспортної мережі в пікселях, тобто ширина зображення необхідна для того, що б транспортна мережа могла на ньому поміститися;
· Height - висота транспортної мережі в пікселях, тобто висота зображення необхідна для того, що б транспортна мережа могла на ньому поміститися;
· pb - посилання на об'єкт PictureBox на якому здійснюється отрисовка транспортної мережі;
· dc - посилання на об'єкт Graphics допомогою якого здійснюється отрисовка транспортної мережі;
· textFontNormal - шрифт для отрисовки нормального тексту;
· textFontBold - шрифт для отрисовки напівжирного тексту, за допомогою якого виділяються об'єкти, що є активними в даний момент;
· dSize - розмір квадратика, ...
