Рубрики
Без рубрики

Графики на Java

Автор оригинала: Olivera Popović.

Вступление

Графики-это удобный способ хранения определенных типов данных. Концепция была “украдена” из математики и присвоена для нужд информатики.

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

Упрощенные Графики

Каждый граф состоит из узлов (также называемых вершинами) и ребер . Мы можем рассматривать узлы как “фрагменты данных”, а ребра-как “отношения между этими фрагментами данных”.

Если мы хотим указать, что два блока данных каким – то образом связаны друг с другом, мы бы соединили их ребром. Узлы обычно представлены в виде кругов с опознавательной меткой на них, чтобы мы могли различать узлы, а ребра представлены линиями (или стрелками, как мы увидим позже), которые соединяют два узла.

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

На этом графике показано, какие у нас разные автобусные остановки и как они связаны. Например, мы видим, что, используя эту автобусную линию, чтобы добраться от Автобусной остановки A до Автобусной остановки C , нам придется пройти Автобусную остановку B – мы не можем добраться туда другим способом.

Взвешенные Графики

Графики очень универсальны, и это одна из причин, по которой они так популярны. Допустим, мы хотели добавить информацию о том, сколько времени в среднем (в минутах) ушло на то, чтобы добраться от одной автобусной остановки до другой. Мы бы добавили “веса” к нашим краям:

Теперь наш график показывает еще больше информации, чем раньше, мы видим, сколько времени требуется, чтобы добраться от одной остановки до другой. Мы можем сделать вывод, что дорога от Автобусной остановки A до Автобусной остановки C займет 23 минуты, так как нам нужно будет “пересечь” границу, соединяющую Автобусную остановку A и Автобусную остановку B , которая имеет вес 15, и ( Автобусная остановка B -> Автобусная остановка C ), которая имеет вес 8.

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

Направленные и неориентированные графики

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

Точнее, когда наш автобус начинается с Автобусной остановки A , он проходит через B , C и заканчивается на D ; однако в другом направлении он проходит не через C , а через совершенно другую автобусную остановку E , прежде чем пройти через B . Мы могли бы сделать что-то вроде этого:

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

Именно здесь в игру вступают направленные графики. Ребра в ориентированных графиках представлены стрелками вместо линий, стрелка, указывающая от A до B , означает “мы можем перейти от A к B , но не наоборот”. Если бы мы хотели сказать, что мы можем получить как от A до B , так и от B до A , мы бы использовали двустороннюю стрелку.

Теперь цикл больше не является двусмысленным:

Теперь ясно , что мы не можем перейти от B к E или от D к C и т. Д. Ясно, что мы можем создавать графики настолько простые или настолько сложные, насколько захотим. В нашем примере мы могли бы сделать еще один шаг вперед, если бы по какой-то причине путешествие между некоторыми автобусными остановками заняло разное время в зависимости от направления, в котором мы едем.

Применение графиков

Вот несколько примеров данных, которые можно удобно хранить/представлять с помощью графиков:

  • Набор людей и их принадлежность: Это можно сделать с помощью неориентированного графика, поскольку мы предполагаем , что если человек A знает человека B , то же самое верно и наоборот. Разные люди будут представлены узлами, и если человек A знает человека B , то будет ребро, соединяющее два узла.
  • Структура веб-сайта: Разные страницы на этом веб-сайте являются узлами, и между страницей A и страницей B есть направленное ребро, если на странице A существует ссылка на страницу B . Например, страница главная часто содержит ссылки на страницу “О нас” и “Контакты”.
  • Взаимозависимые задачи: Мы можем представить, какие задачи необходимо выполнить до выполнения задачи A и какие задачи не могут быть выполнены до выполнения A следующим образом – если есть направленное ребро от B до A , то A не может быть завершено до завершения B ; если есть направленное ребро от A до C , то C не может быть завершено до завершения A :

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

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

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

Графики по сравнению с деревьями

Если вы знакомы с деревьями, графики легко понять – деревья-это особый вид графика, т. Е. Графики с определенными ограничениями. Каждое дерево-это график, но не каждый график является деревом.

По определению, деревья-это неориентированные графики, которые:

  • Являются ациклическими, т. Е. мы не можем вернуться к любому выбранному нами стартовому узлу без возврата
  • Цикл создается путем добавления любого ребра в существующее дерево
  • Путь между любыми двумя узлами уникален
  • Существует отдельный корневой узел
  • Граф связан (между каждыми двумя узлами есть путь)

Или в очень упрощенных терминах – деревья-это связанные графики без циклов. Для графиков мы просто избавляемся от всех этих ограничений и сохраняем концепцию узлов и ребер.

Графики как математический термин

Все вышеперечисленное происходит от математического термина графа. Граф представляет собой упорядоченную пару G = (V, E) , где V – набор вершин, а E – набор ребер.

Undirected Graphs://In the case of undirected graph |//E//имеет следующее определение//E {{х, у} | (Х, У) V V^2} . Sometimes an extra condition is added if we want to avoid edges that have the same start and end point(i. e.//x y и//).

Направленные графики: E ⊆ {(x, y) | (x, y) ∈ V^2} , здесь также мы можем добавить условие, что x ≠ y , если мы хотим избежать ребер, которые начинаются и заканчиваются в одном и том же узле/вершине.

Как мы можем видеть в предыдущих определениях множества ребер E , единственное различие заключается в том,что в случае ориентированных графов (x, y) является упорядоченной парой,в то время как в неориентированных графах пара {x, y} неупорядочена. Это означает, что в неориентированном графике важно то, что x и y связаны, а не в “каком порядке”. Таким образом,мы могли бы написать {y,x} вместо {x,y} , в то время как мы могли бы не написать (y, x) вместо (x,y) для ориентированного графика.

Все это приводит нас к нескольким важным темам, когда речь заходит о обходе графиков в Java – Представление графиков в коде , Поиск по ширине , Поиск по глубине и Алгоритм Дейкстры .

Представление графиков в коде

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

  • Графики в Java: Представление графиков в коде

Поиск по глубине (DFS)

Поиск по глубине (DFS) выполняет поиск как можно дальше вдоль ветви, а затем возвращается к поиску как можно дальше в следующей ветви. Это означает, что на следующем графике он начинается с первого соседа и продолжается вниз по линии, насколько это возможно.

  • Графики в Java: Поиск по глубине

Поиск по ширине (BFS)

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

BFS посещает “слой за слоем”. Это означает, что он сначала посещает все дочерние элементы начального (корневого) узла. Эти дети рассматриваются как “второй слой”, после чего их детей посещают таким же образом.

  • Графики на Java: Поиск по ширине

Алгоритм Дейкстры

Алгоритм Дейкстры -очень известный алгоритм обхода графа для нахождения кратчайшего пути от заданного узла/вершины к другому.

Существует несколько реализаций этого алгоритма, и некоторые даже используют разные структуры данных и имеют разные приложения.

Дейкстра работает по-другому, чем предыдущие алгоритмы. Вместо того, чтобы начинать с корневого узла, он начинается с целевого узла и возвращается к исходному узлу.

  • Графики на Java: алгоритм Дейкстры

ДФС против БФС

Вопрос, который, скорее всего, пришел вам на ум, когда вы читали о DFS и BFS, был:

“В чем практическая разница?”

Теория ясна; BFS сначала посещает узлы, ближайшие к нашему стартовому узлу, в то время как DFS проникает как можно глубже в график (как можно дальше от нашего начального узла), прежде чем продолжить работу с другими узлами, близкими к нашему стартовому узлу.

Давайте рассмотрим несколько примеров:

  • Если все, что вы хотите сделать, это проверить, связаны ли вообще два узла в графике, что не дает вам четкой причины предпочесть тот или иной алгоритм обхода графа – либо один
  • Если вы “знаете”, что ваши два узла находятся близко друг к другу, если они вообще связаны – например, ищете членов семьи в графе знакомств – используйте BFS
  • Если вы хотите подсчитать все возможные способы перехода с одного узла на другой – DFS
  • Если вам нужен кратчайший путь (путь, проходящий через наименьшее количество узлов) от одного узла к другому – BFS
  • DFS также может использоваться для некоторых слегка продвинутых задач, таких как обнаружение цикла в графике или для проверки сильно связанных компонентов (математический термин, означающий, что “каждый узел доступен из любого другого узла”), которые позже могут быть использованы для решения задач 2-выполнимости (2-SAT).

Вывод

Графики-это удобный способ хранения определенных типов данных. Каждый граф состоит из узлов (также называемых вершинами) и ребер . Мы можем рассматривать узлы как “фрагменты данных”, а ребра-как “отношения между этими фрагментами данных”.

Алгоритмы обхода графов, такие как BFS, DFS, алгоритм Дейкстры и A*, очень часто используются во многих областях науки о данных и машинного обучения.