Власне ми вже розглянув один із прикладів такої структури як графи - дерево. Дерево це ненаправленої незважений граф.
Графів насправді абсолютно божевільна кількість. Але для простоти ми поки будемо розділяти граф на такі два типи:
- неорієнтовані граф
- Орієнтований граф (спрямований граф).
Неорієнтовані граф. це підмножина пар (V, E), де V - це підмножина вершин, а Е - підмножина ребер графа які з'єднують ці вершини. Щоб відкинути всякі складні опису та терміни, найлегше уявити граф як дві точки A і B, з'єднані ребром. У неорієнтованому графі по ребру з точки A можна потрапити в точку B, і з точки B в точку А.
В орієнтованому графі все те ж саме, крім того, що ребра тут вже називаються дуги, і вони чітко з'єднують одну точку з іншого. Наприклад точку A з точкою B, що означає що з точки A в точку B потрапити по дузі можна, а ось з точки B в точку A - тут вже шиш. Звичайно ж з точки B в точку A теж може бути дуга :)
У графах все далеко не закінчується двома точками, графи зараз це сотні мільйонів вершин, а то і мільярдів або того більше, з величезною кількістю ребер або дуг (так, є змішані графи, де деякі вершини один з одним з'єднані дугами, а деякі ребрами) між вершинами.
Зважений граф - це граф кожному ребру якого проставлено певне число яке називається вагою ребра.
Власне, граф може бути представлений як лист смежностей так і як матриця суміжності.
Матриця суміжності - це матриця nxn де n це кількість вершин графа, а осередок [i, j] означає або є з'єднання між вершинами i, j. З матрицею суміжності досить просто сказати або є з'єднання між вершинами i, j навіть якщо між ними дуже багато інших вершин. Мінусом матриці суміжності є те кількість пам'яті яке потрібно для зберігання інформації про граф. Наприклад 10 вершин дає нам матрицю - 10 на 10, що дорівнює 100 осередків матриці. Якщо ж у нас буде хоча б тисяча вершин - то кількість осередків виростає до 1 мільйона :)
Припустимо ось такий граф:
Буде виглядати ось таким ось чином:
Альтернативою уявлення графа є список смежностей. Власне це уявлення є списком де з одного боку - вершина, а з іншого боку список вершин з якими є зв'язок.
Така структура є більш оптимальною з точки зору використаної пам'яті, але менш ефективна з точки зору виконання операцій.
Для подальших постів буде використано уявлення графа як списку смежностей. По-перше пам'ять, по-друге мені легше представляти графи в такій структурі.
Створюється граф під час передачі йому кількості вершин. Під час створення графа, ми створюємо масив в якому для кожної вершини будемо зберігати з'єднання з іншими вершинами.
Додавання вершини. Так як граф ненаправленої якщо вершина A з'єднана з вершиною B, значить і навпаки.
Подання спрямованого графа точно таке ж, з однією зміною:
Як бачимо, різниця тільки в одному методі addEdge - тут ми додаємо лише 1 з'єднання вершин.
Як завжди: вихідні прикладів ви можете знайти тут.
coding maleev's blog
