Лучшее вложение, которое вы можете сделать в собственное обучение, - это вернуться к тому, что вы (думаете) вы уже знаете, и это особенно верно в мире информатики. Все в вычислениях - это уровень абстракции, построенный на еще большем количестве слоев абстракции; если бы все отрасли в мире были луковичными, вычисления наверняка были бы одними из немногих с бесчисленным количеством уровней.

Все эти абстракции также делают программное обеспечение таким сложным (а иногда и таким устрашающим). Никто из нас не знает всего, что нужно знать о том, как работает программное или аппаратное обеспечение, на котором работает наш мир. И правда в том, что никто из нас никогда не узнает все, что нужно знать. Но ничего страшного! Мы изучаем то, что нам нужно узнать в данный момент, и изучаем новые вещи, которые нам интересно исследовать. Обычно это означает больше узнать о вещах, с которыми мы уже хоть немного знакомы.

Именно поэтому я люблю возвращаться к темам, которые, как мне кажется, я уже знаю, и копать немного глубже - вы почти всегда найдете что-то новое. Ранее в этой серии мы углубились в основы теории графов; но о графиках нужно знать еще очень много! Мы знаем, что они лежат в основе таких фундаментальных вещей, как социальные сети или даже история наших браузеров, но как они на самом деле работают и как мы их реализуем? Нас мягко познакомили с теорией, лежащей в основе графов, но как мы можем применить эту теорию на практике и понять графы на глубоком уровне, чтобы мы могли действительно использовать их для решения реальных проблем?

Чтобы сделать все это, нам нужно вернуться к основам. Нам нужно понять, как представлять графики и превратить теоретическое в нечто более конкретное.

Упорядоченная пара под любым другим именем

Так как мы уже знакомы с теорией, лежащей в основе графов, мы не будем слишком углубляться в их историю или их применение. Краткая версия истории состоит в том, что графики происходят из математики и представляют собой не что иное, как способ формального представления сети, которая представляет собой совокупность взаимосвязанных объектов.

Чтобы решить задачу представления структуры графа, которая так часто встречается в информатике и в Интернете, мы должны убедиться, что нам удобны части графа, а также его определение. граф - это структура данных с двумя отдельными частями: конечным набором вершин, которые также называются узлами, и конечным набором ребер, которые являются ссылками / ссылками / указатели с одной вершины на другую.

Граф определяется этими двумя отдельными частями, вершинами и ребрами. Некоторые графы имеют много ребер по сравнению с узлами и определяются как плотные графы, тогда как граф с меньшим отношением ребер к узлам называется разреженный график. Точно так же, если ребра графа имеют направленный поток, граф определяется как направленный, а граф с ребрами, у которых нет направленный поток ненаправленный.

Характеристики графа сильно зависят от того, как выглядят его вершины и ребра.

Возможность идентифицировать эти характеристики очень важна, поскольку это напрямую влияет на то, как мы представляем график. Но подождите - как делаем мы представляем граф! Это то, что мы намеревались сделать, но на самом деле мы еще не дошли до этой части, не так ли? Поскольку у нас уже есть некоторые знания о графах, мы можем опираться на это! (Видите, что я имел в виду, когда возвращался к темам, которые, как мы думаем, уже знаем?)

Напомним, что в математике графы представлены как G = (V, E), где V - множество вершин, и E - набор ребер. Когда мы узнали о теории графов, мы увидели, что есть два способа представления этого набора ребер - в виде неупорядоченных или упорядоченных пар - в зависимости от того, являются ли ребра ориентированными или неориентированными.

Давайте быстро освежим, что это означает на практике.

В этом примере мы увидим, что ребра неориентированного графа, представленные E, не имеют никакого порядка, поскольку можно перемещаться из одной вершины в другую. Однако в наборе ребер E для ориентированного графа существует направленный поток, который важен для структуры графа, и поэтому набор ребер представлен в виде упорядоченных пар.

Такое представление ребер графа - самый простой из возможных способов представления графа - и мы уже вроде как знали об этом! Но как эти простые упорядоченные пары на самом деле выглядят в коде и в памяти? Что ж, это то, о чем мы пока не знаем (хотя, возможно, и догадываемся!). Ответ, вероятно, так же прост, как и следовало ожидать: самый быстрый способ превратить эту группу упорядоченных пар - использовать список или массив, в зависимости от того, какой язык мы используем.

Этот список (или массив) называется списком ребер и представляет собой представление всех ребер (| E |) в графе.

В показанном здесь примере у нас есть небольшой граф всего с тремя узлами: 1, 2 и 3. Каждому ребру присваивается индекс, и он представляет собой ссылку от одного узла к другому. Мы заметим, что нет никакого определенного порядка ребер, как они появляются в списке ребер, но каждое ребро должно быть представлено.

Для этого конкретного графа список ребер будет выглядеть так:

[ 
  [1, 2],
  [2, 3],
  [3, 1]
]

Поскольку список краев на самом деле является просто массивом, единственный способ найти что-то в этом массиве - это выполнить итерацию по нему. Например, если мы хотим узнать, соединена ли вершина 1 с вершиной 2, нам нужно будет пройти по этому массиву и найти наличие пары [1, 2] или [2, 1]. Теперь это нормально для нашего графа, у которого всего три вершины и три ребра; итерация по этому массиву на самом деле не имеет большого значения. Но на самом деле большинство графиков будут намного больше, чем этот!

Представьте, что вам нужно перебрать массивный массив, чтобы увидеть, существует ли одно конкретное ребро в массиве; так как список ребер не обязательно должен следовать какому-либо определенному порядку, ребро может быть в самом конце списка! Или его вообще не могло быть, и нам все равно пришлось бы перебирать все, чтобы проверить это. Мало того, что выполнение этой работы потребует линейного, O (E) времени, где E представляет все края в графе - список ребер также требует O (E) места, и все же довольно ограничивает то, что мы можем с ним делать, несмотря на то, что нам нужно это пространство.

Давайте вспомним, с чего мы начали: это простейшее представление графа. Иногда самой простой версии недостаточно для работы. Некоторые, давайте немного усложним!

Когда списки просто не урезают

Для большинства графиков список ребер не будет самым эффективным выбором. Итак, мы можем поднять его на ступеньку выше и перейти от списка к матрице - то есть матрице смежности!

Матрица смежности - это матричное представление того, какие узлы в графе содержат ребра между собой. Матрица похожа на таблицу поиска: как только мы определили два узла, между которыми мы хотим найти границу, мы смотрим на значение на пересечении этих двух узлов. Значения в матрице смежности подобны индикаторам логических флагов; они либо присутствуют, либо нет. Если значение равно 1, это означает, что между двумя узлами есть ребро; если значение равно 0, это означает, что между ними не существует ребра.

Давайте рассмотрим пример, чтобы сделать это немного понятнее. Мы будем работать с тем же графом, который использовали ранее, только с тремя узлами (1, 2 и 3) снова.

На этой иллюстрации мы видим, что матрица смежности всегда имеет главную диагональ, которая будет иметь значение 0 по диагонали, поскольку большинство графов, с которыми мы имеем дело, не будут ссылочными. Другими словами, поскольку узел 2 не может иметь ссылку на себя, если мы проведем линию от столбца 2 к строке 2, значение будет 0. Однако, если бы мы хотели узнать, подключен ли узел 3 к узлу 1, мы могли бы найти столбец 3, строку 1 и увидеть, что значение равно 1, что означает, что между этими двумя узлами действительно есть граница.

В представлении графа матрицей смежности интересно то, что, просто взглянув на них, мы можем определить, является ли граф направленным или неориентированным. Мы можем определить эту характеристику графа в зависимости от того, является ли его матрица смежности симметричной или нет. Если значения на обеих сторонах главной диагонали матрицы смежности одинаковы, матрица является симметричной. Другими словами, если мы найдем строку x, столбец y, она будет содержать то же значение, что и все, что было в строке y, столбце x. Если бы это было верно для всех строк и столбцов матрицы, матрица была бы симметричной, каково наше конкретное графическое представление.

В следующем разделе станет более ясно, как симметрия матрицы связана с «прямотой» графа.

Матрицы смежности, безусловно, являются шагом вперед по сравнению со списком ребер. Во-первых, их довольно легко представить; наша матрица смежности будет выглядеть так:

[
  [0, 1, 1],
  [1, 0, 1],
  [1, 1, 0]  
]

Добавление или удаление ребра из графа также легко выполнить с помощью этого представления, поскольку для поиска потенциального узла между двумя ребрами требуется только знание двух узлов, нахождение соответствующего индекса для каждого и нахождение значения на пересечении между ними. два. Большинство операций с матрицей смежности можно выполнить за постоянное или за O (1) время.

Однако что бы произошло, если бы у нас был разреженный график? Как бы выглядела наша матрица смежности, если бы у нашего графа было очень мало ребер по сравнению с узлами? Что ж, мы, вероятно, можем представить его, даже не вынимая его: в основном он будет заполнен значениями 0. Но из-за того, как структурирована матрица, нам все равно нужно было построить ее целиком!

Проблема с матрицами смежности в том, что они всегда будут требовать O (V²) количества места, что, в зависимости от того, как выглядит наш график, может означать много потраченного впустую места. ! Итак, какой бы прекрасной ни была матрица смежности, она не всегда является правильным представлением для графа (особенно, если этот граф разреженный).

Что ж, не волнуйтесь. Когда дело доходит до графического представления, есть еще один вариант - и он самый интересный из всех!

Списки смежности: гибридный выбор

Что нам делать, когда нам кажется, что и списки ребер, и матрицы смежности подводят нас? Разумеется, объедините их вместе! Именно это и есть список смежности - гибрид между списком границ и матрицей смежности. Список смежности - это массив связанных списков, который служит представлением графа, но также позволяет легко увидеть, какие другие вершины смежны с другими вершинами.

Список смежности является наиболее популярным и часто используемым представлением графа, поскольку большинство проблем обхода графа (которые мы увидим гораздо больше позже в этой серии!) Требуют, чтобы мы могли легко определить, какие узлы являются соседи другого узла. В большинстве сценариев обхода графа нам даже не нужно строить весь граф; нам просто нужно знать, куда мы можем путешествовать - другими словами, кто являются соседями узла. Это довольно легко определить при использовании списка смежности, поскольку каждый отдельный узел / вершина имеет ссылку на всех своих соседей через смежный связанный список.

Давайте рассмотрим пример, чтобы увидеть, как это выглядит на практике.

На приведенной здесь иллюстрации каждой вершине присваивается индекс в ее списке, и все ее соседние вершины хранятся в виде связанного списка (который также может быть массивом), примыкающим к нему. Например, последним элементом в списке является вершина 3, которая имеет указатель на связанный список своих соседей. Связанный список, смежный с вершиной 3, содержит ссылки на две другие вершины: 1 и 2, которые являются двумя узлами, которые связаны с узлом 3. Таким образом, просто посмотрев на узел 3, мы можем определить, кто он является соседом, и с помощью прокси-сервера быстро определить, что к нему подключены два ребра.

Мы видим, что благодаря структуре списка смежности очень легко определить всех соседей одной конкретной вершины. Фактически, получение соседей одного узла занимает константу, O (1) времени, поскольку все, что нам действительно нужно сделать, это найти индекс узел, который мы ищем, и вытащите его список смежных вершин.

Но что, если мы хотим найти конкретное ребро или проверить, существует ли ребро между двумя узлами? Это было легко сделать с помощью матрицы смежности… но насколько легко это сделать со списком смежности?

Что ж, чтобы найти конкретное ребро - например, (x, y) - нам нужно найти вершину x в списке смежности, который, как мы уже знаем, требует постоянного времени O (1) для поиска в качестве индекса. На втором этапе проверяется, находится ли y в списке смежности для узла x. Это можно сделать довольно быстро, особенно если y стоит первым в списке или если это единственный элемент в списке.

Но как насчет худшего сценария? Что ж, y потенциально может находиться в самом конце связанного списка. А может и не существовать! В этом случае нам придется перебирать весь связанный список, чтобы проверить его, что займет у нас O (d) время, где d - степень вершины x. степень вершины - это количество ребер, которые у нее есть, которое также известно как количество соседних узлов, которые у нее есть.

Итак, насколько велика наша степень? Ну, максимально возможное значение степени (d) любой вершины в графе никогда не может быть больше, чем (|V| — 1), где V - общее количество вершин в графе. . Если подумать, это имеет смысл; максимальное количество потенциальных соседей, которое может когда-либо иметь узел, - это каждый отдельный узел в графе, кроме самого себя! Минимально возможное значение для d - 0, поскольку у нас всегда может быть граф, который имеет только одну вершину, что означает, что у него 0 ребер и 0 соседних узлов.

Хорошо, теперь, когда мы знаем, сколько времени может потребоваться у нас, чтобы перебирать список смежности, как насчет того, сколько места это занимает?

Для самого списка смежности потребуется | V | количество места для списка, так как для каждой отдельной вершины потребуется собственный индекс и место в списке. Вершина также будет нуждаться в ссылке указателя на связанный список / массив соседей, но указатель занимает незначительное количество места в памяти. Так что насчет самого связанного списка? Мы уже определили, что в худшем случае самый длинный связанный список соседних узлов может быть (| V | -1).

Но здесь есть одно дополнительное предостережение: общее количество элементов для каждого ребра, представленного в списке смежности, зависит от того, является ли граф направленным или неориентированным.

Это становится более очевидным, когда мы сравниваем представление неориентированного графа с представлением ориентированного графа! Итак, давайте посмотрим, как они будут сравниваться.

В этом примере неориентированного графа у нас есть пять узлов и восемь неориентированных ребер.

Поскольку мы знаем, что существует три разных способа представления этого графика, давайте рассмотрим все эти форматы на этом одном примере. Список ребер - самый простой из трех: это массив из восьми ребер, что объясняет, почему его индексы варьируются от 0-7. Если мы посмотрим на матрицу смежности для этого неориентированного графа, мы заметим, что она симметрична. Учтите, что каждый отдельный узел, который подключен к соседнему узлу в неориентированном графе, имеет свое ребро, отраженное в соседнем узле; вот почему неориентированный граф всегда будет иметь симметричную матрицу смежности.

Теперь, чтобы ответить на наш последний вопрос: как наш список смежности изменяется в размере в зависимости от прямолинейности нашего графа? Что ж, если мы посмотрим на этот пример списка смежности, мы заметим, что каждое ребро появляется дважды. Например, список смежности вершины 2 содержит ссылку на вершину 5; аналогично, список смежности вершины 5 содержит ссылку на вершину 2. Каждое ребро представлено дважды, поэтому общее количество элементов, для которых нам нужно будет выделить место в списке смежности, на самом деле составляет 2 (| E |) элемента, где E - общее количество ребер в неориентированном графе.

Теперь, когда мы рассмотрели все три представления неориентированного графа, мы уже могли догадаться, как сравнивается направленный граф.

На этой иллюстрации у нас есть пять узлов и семь ребер. Представление списка ребер этого графа, как и следовало ожидать, состоит из семи элементов с индексами в диапазоне от 0-6, по одному для каждого из направленных ребер.

Мы заметим, что матрица смежности для ориентированного графа немного отличается от всех, что мы видели раньше! Это потому, что он несимметричный. Если мы посмотрим на (0, 1), мы увидим, что значение равно 0, но если мы посмотрим на (1, 0), мы увидим, что значение равно 1! Это из-за направленного потока ребер в этом графе; не каждый узел имеет двунаправленную ссылку на соседний узел, и макет матрицы смежности прекрасно это отображает.

Наконец, представление этого ориентированного графа в списке смежности также отличается от того, что мы видели ранее в неориентированном графе. Мы заметим, что список содержит только количество элементов | E |, где E - общее количество ребер. Если мы немного подумаем об этом, это имеет смысл; ребра не являются двунаправленными в этом графе, поэтому нам не нужно представлять их дважды для каждого узла; скорее, это односторонние соединения между узлами, поэтому нам нужно представить их только один раз, для любого узла, связанного со своим соседом.

Таким образом, представление графа (и сколько места оно занимает) зависит от того, как он выглядит, и от того, что мы пытаемся сделать! Как и в большинстве случаев в информатике, ответ на вопрос «какое представление мы должны использовать?» буквально: это зависит от того, что вы хотите сделать!

Для целей этой серии и понимания алгоритмов обхода графов и проблем раскраски графов мы, скорее всего, будем использовать списки смежности. Но, как всегда, они всего лишь один инструмент в работе. Однако самое важное - гораздо более важное, чем то, какое представление мы выберем для использования, - это то, что мы знаем, как претворить теорию в практику!

Ресурсы

Понимание основ теории графов очень важно для распаковки некоторых из самых сложных и известных проблем информатики. Но знание всей этой теории бесполезно, если вы не можете ее применить! К счастью, есть много хороших ресурсов, которые показывают, как представить график в программных терминах. Если вы хотите понять еще больше, это несколько хороших мест для начала.

  1. Граф и его представления, Geeksforgeeks
  2. Представляющие графы, Академия Хана.
  3. Представление графов - алгоритмы на графах, Coursera
  4. Представление графа - Список смежности, mycodeschool
  5. Графические визуализации, VisuAlgo