Що таке структура даних графіка?
А Графік це нелінійна структура даних, що складається з вершин і ребер. Вершини іноді також називають вузлами, а ребра — лініями або дугами, які з’єднують будь-які два вузли в графі. Більш формально, граф складається з набору вершин ( IN ) і набір ребер ( І ). Графік позначено G(V, E) .
Зображення графа
Ось два найпоширеніші способи представлення графіка:
- Матриця суміжності
- Список суміжності
Матриця суміжності
Матриця суміжності — це спосіб представлення графа як матриці логічних значень (0 і 1).
Припустимо, що є п вершини в графі Отже, створіть 2D матрицю adjMat[n][n] має розмір n x n.
- Якщо є ребро від вер i до j , знак adjMat[i][j] як 1 .
- Якщо ребра від вершини немає i до j , знак adjMat[i][j] як 0 .
Представлення неорієнтованого графа в матриці суміжності:
На малюнку нижче показано неорієнтований граф. Спочатку ініціалізується вся Матриця 0 . Якщо є межа від джерела до місця призначення, ми вставляємо 1 в обох випадках ( adjMat[пункт призначення] і adjMat [ призначення]) тому що ми можемо піти будь-яким шляхом.
Неорієнтований граф до матриці суміжності
Представлення орієнтованого графа в матрицю суміжності:
На малюнку нижче показано спрямований граф. Спочатку ініціалізується вся Матриця 0 . Якщо є межа від джерела до місця призначення, ми вставляємо 1 для цього конкретного adjMat[пункт призначення] .
Орієнтований граф до матриці суміжності
Список суміжності
Масив списків використовується для зберігання ребер між двома вершинами. Розмір масиву дорівнює кількості вершини (тобто n) . Кожен індекс у цьому масиві представляє певну вершину в графі. Запис за індексом i масиву містить пов’язаний список, що містить вершини, які є суміжними з вершиною i .
Припустимо, що є п вершини в графі Отже, створіть масив списку розміру п як adjList[n].
- adjList[0] матиме всі вузли, які підключені (сусідні) до вершини 0 .
- adjList[1] матиме всі вузли, які підключені (сусідні) до вершини 1 і так далі.
Представлення неорієнтованого графа в списку суміжності:
Наведений нижче неорієнтований граф має 3 вершини. Отже, буде створено масив списку розміром 3, де кожен індекс представляє вершини. Тепер вершина 0 має двох сусідів (тобто 1 і 2). Отже, вставте вершини 1 і 2 в індекси 0 масиву. Аналогічно, для вершини 1 вона має двох сусідів (тобто 2 і 0). Отже, вставте вершини 2 і 0 в індекси 1 масиву. Аналогічно для вершини 2 вставте її сусідів у масив списку.
Неорієнтований граф до списку суміжності
Представлення спрямованого графа в список суміжності:
Орієнтований нижче граф має 3 вершини. Отже, буде створено масив списку розміром 3, де кожен індекс представляє вершини. Тепер вершина 0 не має сусідів. Для вершини 1 вона має двох сусідів (тобто 0 і 2). Отже, вставте вершини 0 і 2 в індекси 1 масиву. Аналогічно для вершини 2 вставте її сусідів у масив списку.
Спрямований граф до списку суміжності