|
Матриця суміжності Розглянемо наступний граф:
При представленні графа матрицею суміжності інформація про граф зберігається в квадратній матриці (двомірному списку), де елемент a[i,j] дорівнює 1, якщо вершини i та j з’єднані ребром та дорівнює 0, якщо вершини i та j не з’єднані. Для даного прикладу матриця суміжності матиме вигляд:
Якщо граф неорієнтований, то матриця суміжності завжди симетрична відносно головної діагоналі.
Розглянемо орієнтований граф:
 Матриця суміжності матиме вигляд
Для зваженого графа кожному ребру відповідає деяке число (наприклад, довжина дороги або вартість проїзду) – вага ребра. В цьому випадку замість одиниць в матриці суміжності зберігають ваги ребер, а при відсутності ребра зберігають спеціальне значення, наприклад, в багатьох задачах зручно при відсутності ребра зберігати дуже велике число – «нескінченість».
Джерела:disted.edu.vn.ua
|
