Так много вещей в мире никогда бы не возникло, если бы не было проблемы, требующей решения. Эта истина применима ко всему, но мальчик, это очевидно в мире информатики.
Кому-то нужен был способ отслеживать порядок вещей, поэтому они экспериментировали и создавали разные структуры данных, пока не нашли ту, которая лучше всего работает для конкретной проблемы, которую они пытались решить. Кому-то нужен был хороший способ хранения данных, поэтому они поиграли с разными системами счисления, пока не нашли ту, которая лучше всего подходит для той информации, которую они хотели содержать. Людям нужен был хороший способ маркировки и обработки задач, поэтому они нашли способ опираться на инструменты, которые у них были, и создали способ совмещать все вещи, которые должна была выполнять одна единственная система, в любой момент времени.
Конечно, информатика - не единственная единственная область, в которой можно вводить новшества и опираться на то, что было до нее, но я действительно думаю, что она уникальна в одном отношении: инновации информатики основываются на своих собственные абстракции.
Я много говорил об абстракциях в этой серии, потому что, в конечном счете, это то, о чем эта серия : найти радость в абстракциях, которые лежат в основе вещей, которые все мы используем каждый божий день. . И, как бы то ни было, когда я говорю «нас», я лишь частично говорю о нас как программистах, производителях технологий - я также имею в виду нас как пользователей. , потребители техники.
Итак, о какой удивительной абстракции мы узнаем дальше? Что ж, теперь, когда мы являемся экспертами в древовидных структурах данных, кажется правильным понять, откуда пришли деревья. На самом деле деревья - это подмножество того, о чем вы, возможно, уже слышали: графики. Но для того, чтобы по-настоящему понять, почему мы используем графики и что они из себя представляют, нам нужно углубиться в самые корни того, что происходит из дискретной математики: теории графов.
Если это ваш самый первый набег на дискретную математику, не бойтесь - она тоже моя! Давайте вместе займемся этим - и постараемся не потерять рассудок в процессе.
Графики Луси – Гуси
Когда мы впервые начали изучать нелинейные структуры, мы узнали об их самой фундаментальной характеристике: их данные не следуют порядку - по крайней мере, не очевидному числовому, как мы видим в массивах или связанных списках. Деревья, как мы узнали, начинаются с корневого узла и могут подключаться к другим узлам, что означает, что они могут содержать поддеревья внутри них. Деревья определяются определенным набором правил: один корневой узел может или не может соединяться с другими, но в конечном итоге все они происходят из одного конкретного места. Некоторые деревья имеют даже больше конкретных правил, таких как бинарные деревья поиска, которые могут иметь только две ссылки на два узла в любой момент времени. .
Но что, если мы сделаем что-то безумное и просто… выбросим эти правила в окно? Что ж, как оказалось, мы полностью можем это сделать! Просто мы больше не будем иметь дело с деревьями - мы будем иметь дело с чем-то, что называется графом.
Деревья - это не что иное, как ограниченные типы графиков, просто с множеством других правил, которым нужно следовать. Дерево всегда будет графом, но не все графы будут деревьями.
Итак, что же отличает дерево от большого зонтика графов?
Ну, с одной стороны, дерево может течь только в одном направлении, от корневого узла к листовым узлам или дочерним узлам. Дерево также может иметь только односторонние соединения - дочерний узел может иметь только одного родителя, а дерево не может иметь никаких циклов или циклических связей.
С графиками все эти ограничения исчезают прямо из окна. Графы не имеют понятия «корневой» узел. И зачем им это? На самом деле, узлы могут быть связаны любым способом. Один узел может быть связан с пятью другими! Графики также не имеют понятия «однонаправленный» поток - вместо этого они могут иметь направление или вообще не иметь направления. Или, чтобы еще больше усложнить ситуацию, у них могут быть одни ссылки, которые имеют направление, а другие - нет! Но сегодня мы не будем вдаваться в подробности.
Давайте начнем с простых вещей.
Графики с направлением и графики без
Итак, мы знаем, что графики в значительной степени нарушают все известные нам правила. Однако есть одна характеристика, которую должен иметь каждый граф: каждый граф всегда должен иметь, по крайней мере, один единственный узел. Подобно тому, как деревьям нужен хотя бы один корневой узел, чтобы считаться «деревом», аналогично графу нужен хотя бы один узел, чтобы считаться «графом». Граф с одним узлом обычно называется одноэлементным графом, хотя мы не будем иметь дело с ними.
Большинство графиков, с которыми мы будем иметь дело, немного сложнее. Но не беспокойтесь - сегодня мы не будем углубляться в сверхсложные графики. И поверьте мне, некоторые графики действительно сложны!
Вместо этого давайте рассмотрим два типа графов, которые довольно легко обнаружить и которые также довольно часто встречаются в задачах теории графов: ориентированные графы и неориентированные графы.
Как мы знаем, не существует реальных правил того, как один узел соединяется с другим узлом в графе. Ребра (иногда называемые ссылками) могут соединять узлы любым возможным способом.
Когда дело доходит до распознавания и определения графов, очень важны разные типы ребер. Фактически, это одно из самых больших и очевидных отличий одного графа от другого: типы ребер, которые у него есть. По большей части (за исключением одного исключения, которое мы не будем рассматривать сегодня) графы могут иметь два типа ребер: ребро, имеющее направление или поток, и ребро, у которого нет направления или потока. Мы уважительно называем их направленными и неориентированными ребрами.
В направленном ребре два узла связаны очень специфическим образом. В приведенном ниже примере узел A подключается к узлу B; существует только один способ перемещения между этими двумя узлами - только одно направление, по которому мы можем двигаться. Довольно часто узел, с которого мы начинаем, называется origin, а узел, к которому мы перемещаемся , - пунктом назначения . На направленном краю мы можем путешествовать только от пункта отправления до пункта назначения и никогда не можем двигаться в обратном направлении.
Однако это совсем другая история с ненаправленными краями. В ненаправленном ребре путь, по которому мы можем идти, идет в обе стороны. То есть путь между двумя узлами является двунаправленным, что означает, что исходный и целевой узлы не фиксированы.
Это различие на самом деле очень важно, потому что ребра в графе определяют, как этот граф называется. Если все ребра в графе ориентированы, он называется ориентированным графом, также называемым орграфом . Если все ребра в графе неориентированные, граф считается - как вы уже догадались - неориентированным графом! Иди прикинь, правда?
Это все очень круто, но на данный момент я хочу знать две вещи - откуда именно взялись все эти графические материалы? И… почему нам должно быть до этого дело?
Давай займемся расследованиями.
Действуйте осторожно: мы сейчас в стране-графике
Информатика любит брать вещи взаймы. В частности, он заимствовал множество концепций из логики и математики. Оказывается, именно так и обстоит дело с графиками.
Структуры графических данных, которые мы называем информатикой, на самом деле происходят из математики и изучения графов, которое называется теорией графов.
В математике графики - это способ формального представления сети, которая, по сути, представляет собой просто набор взаимосвязанных объектов.
Как оказалось, когда компьютерные ученые применили теорию графов к коду (и в конечном итоге реализовали графы как структуры данных), они не сильно изменились. Итак, многие термины, которые мы используем для описания и реализации графов, являются точными терминами, которые мы находим в математических справочниках по теории графов.
Например, с математической точки зрения мы описываем графики как упорядоченные пары. Помните школьную алгебру, когда мы узнали о координатах упорядоченных пар (x, y)? Здесь аналогично, с одним отличием: вместо x и y части графика: v для вершин и e для его ребер.
Формальное математическое определение графа таково: G = (V, E). Вот и все! Действительно. Я обещаю.
Но подождите секунду - что, если у нашего графа более одного узла и более одного ребра! Фактически ... он будет почти всегда иметь несколько ребер, если у него более одного узла. Как вообще работает это определение?
Что ж, это работает, потому что эта упорядоченная пара - (V, E) - на самом деле состоит из двух объектов: set вершин и набор ребер.
Хорошо, теперь это имеет для меня больше смысла. Но было бы намного понятнее, если бы у меня был пример и я написал определение графа! Так что мы и сделаем это. В приведенном ниже примере у нас есть неориентированный граф с 8 вершинами и 11 ребрами.
Так что здесь происходит?
Итак, мы выписали нашу упорядоченную пару (V, E), но поскольку каждый из этих элементов является объектом, нам пришлось выписать и их. Мы определили V как неупорядоченный набор ссылок на наши 8 вершин. «Неупорядоченная» часть здесь действительно важна, потому что помните, в отличие от деревьев, здесь нет иерархии узлов! Это означает, что нам не нужно их заказывать, поскольку порядок здесь не имеет значения.
Мы также должны были определить E как объект, который содержит в себе группу граничных объектов. Еще раз обратите внимание, что наши граничные объекты также неупорядочены. Почему это могло быть? Ну что это за граф? Есть ли направление или поток? Есть ли фиксированное ощущение «происхождения» и «назначения»?
Нет, нет! Это неориентированный граф, что означает, что ребра двунаправлены, а исходный узел и целевой узел не фиксированы. Итак, каждый из наших краевых объектов также является неупорядоченными парами.
Эта особенность, конечно, заставляет задуматься: что, если бы это был направленный граф? Пришло время для другого примера! Вот ориентированный граф с тремя вершинами и тремя ребрами:
То, как мы определяем вершины здесь, ничем не отличается, но давайте более внимательно рассмотрим наше определение ребер. Наши граничные объекты в этом случае являются упорядоченными парами, потому что в этом случае действительно имеет значение направление! Поскольку мы можем перемещаться только от исходного узла к конечному узлу, наши ребра должны быть упорядочены так, чтобы исходный узел был первым из двух узлов в каждом из наших определений ребер.
Круто, вот как мы определяем графики. Но… когда же мы действительно использовать графики? Что ж, вы, наверное, использовали один сегодня. Возможно, вы еще этого не знаете! Пора это изменить.
Суперсоциальные графики
Графики окружают нас повсюду, просто мы не всегда видим их такими, какие они есть.
Фактически, читая этот пост, вы прямо сейчас буквально на графике. Интернет представляет собой массивную графическую структуру! Когда мы нажимаем между веб-сайтами и перемещаемся между URL-адресами, мы на самом деле просто перемещаемся по графику. Иногда в этих графах есть узлы с ненаправленными ребрами - я могу переходить от одной веб-страницы к другой - и другие, которые являются направленными - я могу перейти только с веб-страницы A на веб-страницу B, и никогда наоборот.
Но есть еще лучший пример, который прекрасно иллюстрирует наше повседневное взаимодействие с графиками: социальные сети.
Facebook, огромная социальная сеть, представляет собой разновидность графа. И если мы больше задумаемся о его реальных функциях, мы начнем лучше понимать, как мы можем определить, и какой именно тип графа. На Facebook, если я добавлю вас в друзья, вы должны принять мой запрос. Я не могу быть твоим другом в сети, если ты тоже не мой. Отношения между двумя пользователями (читай: узлы или вершины в терминах графа!) Являются двунаправленными. Нет понятия «исходный» и «целевой» узел - вместо этого вы мой друг, а я ваш.
Сможете угадать, в виде какого типа графа реализован Facebook?
Если вы угадали неориентированный график, то вы правы! Отличная работа. Отношения двусторонние, поэтому, если бы мы определили сеть друзей Facebook как граф, все его ребра оказались бы неупорядоченными парами, когда мы их выписали.
Twitter, с другой стороны, работает совсем не так, как Facebook. Я могу следовать за вами, но вы не можете последовать за мной в ответ. Показательный пример: я слежу за Бейонсе, но она определенно не подписывается на меня (к сожалению).
Мы могли бы представить Twitter в виде направленного графика. Каждое ребро, которое мы создаем, представляет собой одностороннюю связь. Когда вы следите за мной в Твиттере, вы создаете ребро в графе, используя вашу учетную запись в качестве исходного узла, а мою учетную запись в качестве узла назначения.
Так что же произойдет, когда я последую за тобой в ответ? Могу ли я изменить край, который вы создали, когда следовали за мной? Он вдруг стал двунаправленным? Ну, нет, потому что я могу отписаться от вас в любой момент. Когда я следую за вами назад в Твиттере, я создаю второе ребро с моей учетной записью в качестве исходного узла, а ваша - в качестве пункта назначения.
Та же модель применима и к Medium, что позволяет вам подписываться на авторов и отписываться от них! Фактически, эта сетевая модель повсюду. И все, что получилось, если абстрагироваться от всех слоев, - это график. И действительно, какая это мощная вещь.
Ресурсы
О графиках написано очень много целых книг. Я определенно не привел здесь достаточно информации, чтобы заполнить книгу, но это не значит, что вы не можете продолжать изучать графики! Наполните свой разум еще большим количеством удивительных идей теории графов, начиная с замечательных ссылок ниже.
- Разница между деревьями и графами, Пунам Дханвани
- В чем разница между деревом структуры данных и графиком?, StackOverflow
- Применение теории графов в информатике: обзор, С.Г. Ширинивас и др. al.
- Обход графа, профессор Джонатан Коэн
- Структуры данных: Введение в графики, mycodeschool
