Матриця суміжності

Матриця суміжності 

Розглянемо наступний граф:

При представленні графа матрицею суміжності інформація про граф зберігається в квадратній матриці (двомірному списку), де елемент a[i,j] дорівнює 1, якщо вершини i та j з’єднані ребром та дорівнює 0, якщо вершини i та j не з’єднані.

Для даного прикладу матриця суміжності матиме вигляд: 

	1	2	3	4	5
1	0	1	1	1	0
2	1	0	0	1	1
3	1	0	0	1	0
4	1	1	1	0	1
5	0	1	0	1	0

 

Якщо граф неорієнтований, то матриця суміжності завжди симетрична відносно головної діагоналі. 

 

Розглянемо орієнтований граф: 

Матриця суміжності матиме вигляд

	1	2	3	4	5
1	0	1	0	0	0
2	0	0	0	1	1
3	1	0	0	1	0
4	1	0	1	0	0
5	0	0	0	0	0

Для зваженого графа кожному ребру відповідає деяке число (наприклад,  довжина дороги або вартість проїзду) – вага ребра.

В цьому випадку замість одиниць в матриці суміжності зберігають ваги ребер, а при відсутності ребра зберігають спеціальне значення, наприклад, в багатьох задачах зручно при відсутності ребра зберігати дуже велике число – «нескінченість». 

 

Джерела:

http://foxford.ru/wiki/informatika/hranenie-grafa-matritsa-smezhnosti