Матрица смежности для ориентированного графа — это квадратная матрица порядка n, где n является числом вершин графа. Строки и столбцы матрицы определяют вершины графа.
Введение
Понятие графа является одним из фундаментальных в информатике и математике. Под графом понимается комбинированный набор рёбер и вершин. В качестве примера графа можно привести аналогию с системой дорог. Есть определённое количество городов, между некоторыми городами построены дороги. Дороги есть односторонние, а есть и двухсторонние. Эту дорожную сеть можно назвать дорожным графом. Вершинами графа являются города, а рёбрами графа выступают дороги. Графически граф может иметь вид, представленный на рисунке 1.
Рисунок 1. Граф. Автор24 — интернет-биржа студенческих работ
Данный граф имеет шесть вершин, каждая из которых пронумерована, и семь двухсторонних рёбер. Рёбра принято обозначать номерами пары соединяемых вершин, то есть: 1-2, 1-5, 2-3, 2-5, 3-4, 4-5, 4-6.
Ориентированные и неориентированные графы
Если продолжить дорожную аналогию в среде графов, то односторонние (то есть однонаправленные) «дороги» принято называть ориентированными рёбрами графа, а двухсторонние имеют название неориентированных рёбер. Если у графа все рёбра неориентированные, то он называется неориентированным графом, а если все рёбра ориентированные, то и граф будет ориентированным. На рисунке два приведён пример неориентированного графа, а на рисунке три — ориентированного.
Рисунок 2. Неориентированный граф. Автор24 — интернет-биржа студенческих работ
Рисунок 3. Ориентированный граф. Автор24 — интернет-биржа студенческих работ
Как видно из рисунков, неориентированный граф возможно обойти в обоих направлениях, а ориентированный граф возможно целиком пройти только по часовой стрелке.
Под путём в графе понимается последовательные вершины, соединённые со следующей вершиной, ребром. Как правило, под «путём» понимается простой путь, проходящий через все разные вершины. Если путь попадает на какую-нибудь вершину больше одного раза, то он считается сложным путём. Циклом называется путь, у которого первая вершина на пути совпадает с последней.
Матрица смежности, ее достоинства и недостатки
В программировании есть два главных метода описания графов. Матрица смежности является одним из них. Применяется она достаточно редко, но очень проста в реализации. Граф, который имеет N вершин, может быть задан с помощью матрицы N∗N (двумерный массив) и в ней есть функция g[i][j], которая может иметь значение true или false, что означает есть ребро из вершины i в вершину j, или нет.
Матрица смежности имеет такую особенность: сложно проверить есть ли ребро между двумя вершинами.
К недостаткам матрицы смежности следует отнести:
- Требует N в квадрате ячеек памяти, что может вызвать проблемы при большом объёме графа.
- Достаточно сложно выполнить перебор всех смежных с текущей вершин.
Список смежности
Вторым методом описания графа является список смежности, который применяется намного чаще. Основной постулат этого метода состоит в сохранении для каждой вершины увеличенного массива (вектора), который содержит все соседние вершины.
Основными преимуществами такого метода являются:
- Оптимальное использование памяти.
- Возможность выполнять с большой скоростью перебор соседних вершин.
- Позволяет оперативно проверять присутствие ребра и выполнять его удаление при необходимости.
К недостаткам списка смежности можно отнести:
- Если выполняется работа с насыщенными графами (число рёбер приближается к N в квадрате), возможна нехватка скорости и это один из поводов применить матрицу смежности.
- Если ведётся работа со взвешенным графом необходимо сохранять вектор, что ведёт к усложнению кода.
