Углубленный взгляд на матрицы смежности логики и скрытого кода.
👋 Добро пожаловать!
Привет! Графы - это чрезвычайно мощные структуры данных. Они используются для представления «сети» связанных элементов.
В этой статье вы узнаете логику, лежащую в основе матриц смежности, и то, как вы можете создавать их в Python для представления графиков. Начнем! 😀 🔮
1️⃣ Встречайте матрицы смежности
Это, вероятно, очень похоже на то, что вы представляете, когда я упоминаю слово «график», верно?
Это правда, эта диаграмма представляет собой график, но не кажется ли вам, что она слишком абстрактна, чтобы реализовать ее в вашем коде и в реальных сценариях?
1️⃣ Что, если бы в вашем графике были тысячи узлов и соединений?
2️⃣ Как бы вы представили эти связи в своем коде?
Не волнуйтесь! На помощь приходят матрицы смежности! 💥
Они дают нам возможность представить наш график в соответствии с очень эффективной и структурированной процедурой. Создавая матрицу (таблицу со строками и столбцами), вы можете очень легко представлять узлы и ребра.
Давайте посмотрим, как вы можете шаг за шагом создать матрицу смежности! 👍
🔨 Давайте создадим матрицу смежности
Мы создадим таблицу смежности для представления этого графа:
1️⃣ Нарисуйте таблицу для представления узлов
Как вы можете видеть на диаграмме ниже, строки и столбцы используются для представления узлов на графике. На графике есть узлы A, B, C и D, поэтому мы включаем их все в столбцы и ряды. (Да, повторил! 😊)
Продолжайте читать, чтобы узнать, почему мы это делаем! 😉
2️⃣ Начните заполнять пробелы
Теперь пора начать представлять связи (ребра) между узлами. Вот тогда график оживает! 🔆
Вы можете начать заполнять поля по строкам или по столбцам. В зависимости от того, что вы выберете, вам нужно будет анализировать график по-разному. Давайте посмотрим, как вы можете начать анализировать его по строкам:
Узел A - Строка:
Если вы начинаете с первой строки (Узел A), вам необходимо проверить, имеет ли этот Узел ребро, направленное к каждому из узлов в графе (включая самих себя, которые называются «петлями»).
Когда вы анализируете по строкам, вы должны спросить себя:
✅ Есть ли ребро от узла A к самому себе?
✅ Есть ли ребро от узла A к узлу B?
✅ Есть ли ребро от узла A к узлу C?
…. и так далее. Вы можете увидеть узор. 👍
⚠️ Если ответ на этот вопрос для пары узлов «да», тогда вы должны написать 1 в ячейке, которая соответствует пересечению между этой парой узлов.
Давайте посмотрим на это в действии! 😅
На диаграмме ниже вы можете видеть, что соединения от узла A идут к узлу B, узлу C и узлу D, поэтому вы добавляете 1 в ячейки, где A и B пересекаются, где A и C пересекаются и где A и D. пересекаются. Затем вы заполняете остальную часть строки нулями, поскольку от узла A к нему нет ребер.
Узел B - строка:
Из этого узла не выходят ребра, поэтому вы заполняете всю строку нулями.
Узел C - строка:
Этот узел имеет только одно ребро, выходящее к узлу D, поэтому вы добавляете 1 в соответствующую ячейку и завершаете строку нулями.
Узел D - строка:
Как и узел B, узел D не имеет ребер, ведущих к другим узлам, поэтому вся строка будет заполнена нулями.
🏅 Вуаля! - Наша Матрица готова! Теперь столбцы 👍
Хорошая работа! Теперь давайте посмотрим, как можно заполнить эту матрицу столбец за столбцом. Вы увидите, как мы получим точно такую же матрицу.
Для заполнения таблицы по столбцам необходимо спросить:
✅ Какие грани подходят к узлу A?
✅ Какие грани подходят к узлу B?
✅ Какие грани подходят к узлу C?
…. и так далее. Вы можете увидеть узор. 👍
Узел A - столбец:
Поскольку никакие края не подходят к узлу A, вы заполняете столбец нулями.
Узел B - столбец:
Единственное ребро, идущее к узлу B, идет от узла A, поэтому вы указываете 1 в этой ячейке и заполняете остальную часть столбца нулями.
Узел C - столбец:
Единственное ребро, идущее к узлу C, идет от узла A, поэтому вы добавляете 1 в эту ячейку и заполняете остальную часть столбца нулями.
Узел D - столбец:
К узлу D идут два ребра от узлов A и C, поэтому вы добавляете 1 в соответствующие ячейки и заполняете остальную часть столбца нулями.
🏆 Наконец-то! - Наша Матрица готова! ❤️
Как видите, две полученные матрицы равны, поэтому оба метода эквивалентны. 🎉
💡 Примечание. Помните, что неориентированные графы имеют двустороннюю связь между соединенной парой узлов, поэтому это также должно быть представлено в таблице. Когда есть граница между узлом A и узлом B, должна быть граница между узлом B и узлом A.
🏋 Матрицы смежности и взвешенные графы
Для взвешенных графиков, где каждое ребро имеет связанный с ним вес (значение), вы просто заменяете единицы на вес ребра, а нули на Null, потому что 0 может быть допустимым весом.
🚦 Примеры использования
- Матрицы смежности следует использовать для плотных графов (графов с большим количеством ребер).
- В противном случае если у графа очень мало ребер, вы будете тратить память, потому что матрица будет хранить много нулей из-за отсутствия соединений. В этом случае рекомендуется использовать списки смежности (следите за статьями по этой теме! 😄)
💻 В Кодекс!
Момент, которого вы так ждали, наконец-то настал! Узнав, что такое матрица смежности и какова ее логика, давайте погрузимся в код!
Вот пример невзвешенного ориентированного графа, представленного матрицей смежности 👇
Давайте посмотрим, как этот код работает за кулисами: 🔍
1️⃣ Настройте матрицу
2D-список, полностью заполненный нулями, создается при создании экземпляра графика благодаря этому коду:
def __init__(self, numNodes):
self.adjacencyMatrix = []
for i in range(numNodes):
self.adjacencyMatrix.append([0 for i in range(numNodes)])
self.numNodes = numNodes
Ваша исходная матрица будет выглядеть так (сравните ее с диаграммой ниже):
self.adjacencyMatrix = [[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]
2️⃣ Добавить края
Затем вы начинаете добавлять края. Например:
graph1 = Graph(4) # Create an instance of the graph with 4 nodes
graph1.addEdge(0, 1); # The 0th element is A. The 1st element is BЭто приведет к выполнению показанного ниже метода, который присваивает значение 1 соответствующей ячейке:
def addEdge(self, start, end):
self.adjacencyMatrix[start][end] = 1
В этой строке self.adjacencyMatrix[start][end] = 1:
- [start] выбирает строку.
- [конец] выбирает столбец.
- Наконец, этой позиции присваивается значение 1.
self.adjacencyMatrix = [[0, 1, 0, 0], # 0th row, 1st column.
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]
На этом этапе наш график будет выглядеть, как на диаграмме ниже, потому что мы добавили только первое ребро.
Мы повторяем этот процесс, пока не добавим все ребра и наш график не будет выглядеть так:
3️⃣ Удалить края
Вы также можете удалить ребра из своего графика. Предположим, что после настройки матрицы вы хотите удалить границу между узлами C и D (как показано ниже).
Этот метод проверяет, есть ли граница между узлами, и, если есть, удалит ее, установив значение 0.
def removeEdge(self, start, end):
if self.adjacencyMatrix[start][end] == 0:
print("There is no edge between these nodes")
else:
self.adjacencyMatrix[start][end] = 0
4️⃣ Проверьте, подключены ли два узла
Вы также можете проверить, существует ли ребро, найдя элемент в матрице и проверив, равен ли он 0 или 1. Если значение ребра больше 0, ребро существует, и метод возвращает True. В противном случае между этими узлами нет края, и метод возвращает False.
def containsEdge(self, start, end):
if self.adjacencyMatrix[start][end] > 0:
return True
else:
return False
Предположим, вы хотите проверить, есть ли граница между узлами B и D.
Вы должны вызвать print(graph1.containsEdge(3, 1)), но, поскольку значение равно 0, между этими узлами нет грани, и возвращается False.
👋 Спасибо!
Очень надеюсь, что вам понравилась моя статья. ❤️
Искренне ценю ваши аплодисменты и комментарии.
Следуйте за мной на Medium | Twitter, чтобы найти больше подобных статей. 😃
Если вам понравилась эта статья, я предлагаю прочитать мою статью о Связанных списках:
📣 Следите за обновлениями, когда мы увидим будущую статью о Смежных списках, которые оптимальны для разреженных графов (графов с небольшим количеством ребер).
