Алгоритмы 101: как использовать алгоритмы на графах

Что такое граф алгоритмы?

Алгоритм — это математический процесс для решения проблемы с использованием четко определенного или оптимального количества шагов. Это просто базовая техника, используемая для выполнения конкретной работы.

Граф — это абстрактное обозначение, используемое для представления связи между всеми парами объектов. Графы — это широко используемые математические структуры, визуализируемые двумя основными компонентами: узлами и ребрами .

Алгоритмы построения графиков используются для решения проблем представления графиков в виде сетей, таких как рейсы авиакомпаний, подключение к Интернету или социальные сети. возможность подключения к Facebook. Они также популярны в НЛП и машинном обучении для формирования сетей..

Некоторые из лучших алгоритмов графа включают:

• Реализовать обход в ширину
• Реализовать обход в глубину
• Вычислить количество узлов на уровне графа
• Найти все пути между двумя узлами
• Найти все компоненты связности графа
• Алгоритм Дейкстры найти кратчайший путь в данных графа
• Удалить ребро

Хотя графики являются неотъемлемой частью дискретной математики, они также имеют практическое применение в информатике и программировании, включая следующее:

• Отношения вызывающий-вызываемый в компьютерной программе, представленной как граф.
• Структура ссылок веб-сайта может быть представлена ​​ориентированным графом.
• Нейронные сети реализованы с использованием

Свойства графа

Граф, обозначенный G, представляет собой состоит из набора вершин (V) или узлов, связанных ребрами (E) . Количество ребер зависит от вершин. Ребра могут быть направленными или неориентированными.

В ориентированном графе узлы связаны в одном направлении. Ребра здесь показывают одностороннюю связь.

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

Пример: Хорошим вариантом использования неориентированного графа является алгоритм предложения друзей в Facebook. Пользователь (узел) имеет ребро, ведущее к другу A (другому узлу), который, в свою очередь, соединен (или имеет ребро) с другом B. Затем пользователю предлагается друг B.

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

Vertex

Вершина — это точка где встречаются несколько линий. Его также называют узлом.

Ребро

Ребро — это математический термин, используемый для линии, соединяющей две вершины. Из одной вершины можно образовать множество ребер. Однако без вершины не может быть образовано ребро. Здесь должна быть начальная и конечная вершины для каждого ребра.

Путь

Путь в графе G = ( V , E ) G = (V, E) G = (V, E) — это последовательность вершин v1, v2,…, vk со свойством наличия ребер между v i vi vi и v i + 1 vi + 1 vi + 1. Мы говорим, что путь идет от v1 v1 v1 to v k vk vk.

Последовательность 6,4,5,1,26,4,5, 1,2 определяет путь от узла 6 к узлу 2.

Аналогично, другие пути могут быть созданы путем обхода краев графа. Путь является простым, если все его вершины разные.

Прогулка

Прогулки — это пути, но они не требуют последовательности различных вершины.

Связанный граф

Граф является связным, если для каждой пары вершин u u u и v v v, есть путь из uu u в v v v.

Цикл

Цикл — это путь v1, v2,…, vk, для которого справедливо следующее:

• k> 2 k >2k>2k>2 k> 2k> 2
• Первые k − 1 вершина все разные
• v 1 = v k v1 = vk v1 = vk

Дерево

Дерево — это связный граф, не содержащий цикла.

Цикл

Если в графе ребро проведено от вершины к самому себе, это называется петлей. На иллюстрации V — это вершина, ребро которой (V, V) образует петлю.

Как представлять графы в коде

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

Матрица смежности

Матрица смежности — это квадратная матрица, помеченная вершинами графа, и используется для представления конечного графа. Записи матрицы указывают, является ли пара вершин смежной или нет в графе.

В представлении матрицы смежности вам нужно будет перебрать все узлы, чтобы идентифицировать соседей узла.

  abcd ea 1 1 - - -b - - 1 - -c - - - 1 -d - 1 1 - -  

Список смежности

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

  1 a -> {ab} 2 b -> {c  } 3 c -> {d} 4 d -> {bc}  

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

Класс Graph

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

 class AdjNode: "" "Класс для представления списка смежности узла" "" def __init __ (self, data): "" "Конструктор: param data: vertex"  "" self.vertex = data self.next = Noneclass Graph: "" "Graph Class ADT" "" def __init __ (self, vertices): "" "Конструктор: param vertices: Общее количество вершин в графе" "" self.V  = vertices self.graph = [None] * self.V # Функция для добавления ребра в неориентированный граф def add_edge (self, source, destination): "" "add edge: param source: Source Vertex: param destination: Destination Vertex  "" "# Добавление узла к исходному узлу node = AdjNode (destination) node.next = self.graph [source] self.graph [source] = node # Добавление исходного узла к месту назначения, если неориентированный граф # Преднамеренно прокомментировал  строки #node = AdjNode (источник) # node.next = self.graph [destin  ation] # self.graph [destination] = node def print_graph (self): "" "Функция для печати графика" "" для i в диапазоне (self.V): print ("Список смежности вершины {}  n  head ".format (i), end =" ") temp = self.graph [i] while temp: print (" -> {} ". format (temp.vertex), end =" ") temp = temp.next  print (" n") # Основная программаif __name__ == "__main__": V = 5 # Всего вершин g = Graph (V) g.add_edge (0, 1) g.add_edge (0, 4) g.add_edge (1  , 2) g.add_edge (1, 3) g.add_edge (1, 4) g.add_edge (2, 3) g.add_edge (3, 4) g.print_graph () 

В приведенном выше примере мы видим класс графа Python. Мы заложили основу нашего класса графов. Переменная V содержит целое число, определяющее общее количество вершин.

Как реализовать обход в ширину

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

Для решения этой проблемы уже добавлен ранее реализованный класс Graph.

Вход: граф, представленный в виде списка смежности и начальной вершины

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

Пример вывода:

  result = "02143" orresult = "01234"  

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

bfs
bfs
• bfs
GraphClass
• GraphClass

Решение

bfs
bfs
• bfs
Graph.py
• Graph.py

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

Граф может содержать циклы. Чтобы избежать повторной обработки одного и того же узла, мы можем использовать логический массив, который помечает посещенные массивы. Вы можете использовать очередь, чтобы сохранить узел и пометить его как посещенный. Очередь должна соответствовать методу организации очереди «первым пришел — первым обслужен» (FIFO).

Как реализовать обход в глубину

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

Входные данные: граф, представленный в виде списка смежности и начальной вершины

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

  result = "01342"  orresult = "02143"  

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

dfs
dfs
• dfs
Graph.py
• График. py

Решение

dfs
dfs
• dfs
Graph.py
• Graph.py

Алгоритм построения графа в глубину использует идею поиска с возвратом. Здесь «backtrack» означает движение вперед до тех пор, пока на текущем пути больше нет узлов, а затем перемещение назад по тому же пути, чтобы найти узлы для перемещения.

Как удалить край

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

Вход: график, источник (целое число) и место назначения (целое число)

Вывод: обход графа BFS с удаленным ребром между источником и местом назначения

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

remove_edge
remove_edge
• remove_edge
graph.py
• graph.py

Решение

Эта задача очень похожа на удаление в связанном списке, если вы с ним знакомы.

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

Если удаляемый ключ находится в середине связанного list, мы отслеживаем предыдущий узел и соединяем предыдущий узел со следующим узлом, когда встречается пункт назначения.

Еще вопросы на собеседовании

Ниже приведены другие вопросы собеседования, в решении которых вы можете попробовать свои силы:

Чему научиться дальше

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

Если вы хотите узнать больше об алгоритмах в Python, ознакомьтесь с планом обучения Educative Ace the Python Coding Interview . В этих модулях вы познакомитесь со структурами данных, алгоритмами и важным синтаксисом, попрактиковавшись в сотнях реальных вопросов на собеседовании.

К концу вы даже сможете уверенно отвечать на многопоточность и параллелизм. вопросы.

Удачного обучения!

Продолжить чтение об интервью по программированию и Python

• Трёхмесячный учебный курс по подготовке к собеседованию
• Обновления Python 3.9: топографическая сортировка и обработка строк
• 50 вопросов и ответов на собеседование по Python