Алгоритмы — одна из самых распространенных тем на собеседованиях по кодированию. Чтобы получить преимущество на собеседовании, важно хорошо знать основные алгоритмы и их реализации.
В сегодняшнем руководстве мы будем изучать алгоритмы графа. Мы начнем с введения в теорию графов и алгоритмы графов. Далее мы узнаем, как реализовать граф. Наконец, мы рассмотрим типичные проблемы с графами, которые вы можете ожидать увидеть на собеседовании по кодированию.
Что такое графовые алгоритмы?
Алгоритм — это математический процесс для решения проблемы с использованием четко определенного или оптимального количества шагов. Это просто базовая техника, используемая для выполнения конкретной работы.
Граф — это абстрактное обозначение, используемое для представления связи между всеми парами объектов. Графы — это широко используемые математические структуры, визуализируемые двумя основными компонентами: узлами и ребрами.
Алгоритмы графов используются для решения проблем представления графов в виде сетей, таких как рейсы авиакомпаний, подключение к Интернету или подключение к социальным сетям на Facebook. Они также популярны в НЛП и машинном обучении для формирования сетей.
Некоторые из лучших алгоритмов графа включают в себя:
- Реализовать обход в ширину
- Реализовать обход в глубину
- Вычислить количество узлов на уровне графа
- Найдите все пути между двумя узлами
- Найдите все компоненты связности графа
- Алгоритм Дейкстры для поиска кратчайшего пути в данных графа
- Удалить край
Хотя графики являются неотъемлемой частью дискретной математики, они также имеют практическое применение в информатике и программировании, включая следующее:
- Отношения вызывающий-вызываемый в компьютерной программе, представленной в виде графика
- Ссылочная структура веб-сайта может быть представлена ориентированным графом.
- Нейронные сети реализованы с использованием
Свойства графа
Граф, обозначенный G, представлен набором вершин (V) или узлов, соединенных ребрами (E). Количество ребер зависит от вершин. Края могут быть направленными или ненаправленными.
В ориентированном графе узлы связаны в одном направлении. Края здесь показывают одностороннюю связь.
В неориентированном графе ребра двунаправлены, показывая двустороннюю связь.
Пример. Хорошим вариантом использования неориентированного графа является алгоритм предложения друзей в Facebook. Пользователь (узел) имеет ребро, ведущее к другу A (другому узлу), который, в свою очередь, соединен (или имеет ребро) с другом B. Затем пользователю предлагается друг B.
Есть много других сложных типов графов, которые попадают в разные подмножества. Например, ориентированный граф имеет компоненты сильной связности, когда каждая вершина достижима из любой другой вершины.
Vertex
Вершина — это точка пересечения нескольких прямых. Его еще называют узлом.
Edge
Ребро — это математический термин, используемый для линии, соединяющей две вершины. Из одной вершины можно образовать множество ребер. Однако без вершины не может быть образовано ребро. T здесь должна быть начальной и конечной вершинами для каждого ребра.
Path
Путь в графе G = (V, E)G = ( V, E ) последовательность вершин v1, v2,…, vk, обладающая тем свойством, что между viv я а также vi + 1v я + 1. Мы говорим, что путь идет отv1v 1 к vkv k.
Последовательность 6,4,5,1,26,4,5,1,2 определяет путь от узла 6 к узлу 2.
Точно так же можно создать другие пути, пересекая края графа. Путь считается простым, если все его вершины разные.
Walk
Прогулки — это пути, но они не требуют последовательности отдельных вершин.
Connected graph
Граф связен, если для каждой пары вершин тыты а также vv, есть путь от тыты к vv.
Cycle
Цикл — это путь v1, v2,…, vk, для которого справедливо следующее:
- к> 2к> 2к > 2 к > 2
- Первые k − 1 вершина все разные
- v1 = vkv 1 = v k
Tree
Дерево — это связный граф, не содержащий цикла.
Loop
В графе, если ребро проведено от вершины к самому себе, это называется петлей. На иллюстрации V — вершина, ребро которой (V, V) образует петлю.
Как представлять графики в коде
Прежде чем мы перейдем к решению проблем с использованием алгоритмов графов, важно сначала узнать, как представлять графы в коде. Графы могут быть представлены в виде матрицы смежности или списка смежности.
Adjacency Matrix
Матрица смежности — это квадратная матрица, помеченная вершинами графа, и используется для представления конечного графа. Элементы матрицы указывают, является ли пара вершин смежной или нет в графе.
В представлении матрицы смежности вам нужно будет перебрать все узлы, чтобы идентифицировать их соседей.
a b c d e a 1 1 - - - b - - 1 - - c - - - 1 - d - 1 1 - -
Adjacency List
Список смежности используется для представления конечного графа. Представление списка смежности позволяет легко перебирать соседей узла. Каждый индекс в списке представляет вершину, а каждый узел, связанный с этим индексом, представляет свои соседние вершины.
1 a -> { a b } 2 b -> { c } 3 c -> { d } 4 d -> { b c }
Для базового класса графа, приведенного ниже, мы будем использовать реализацию списка смежности, поскольку она работает быстрее для решений алгоритмов, представленных далее в этой статье.
The Graph Class
Требования к реализации нашего графа довольно просты. Нам понадобятся два элемента данных: общее количество вершин в графе и список для хранения смежных вершин. Нам также нужен метод добавления ребер или набор ребер.
class AdjNode:«»»A class to represent the adjacency list of the node«»»def __init__(self, data):«»»Constructor:param data : vertex«»»self.vertex = dataself.next = Noneclass Graph:«»»Graph Class ADT«»»def __init__(self, vertices):«»»Constructor:param vertices : Total vertices in a graph«»»self.V = verticesself.graph = [None] * self.V# Function to add an edge in an undirected graphdef add_edge(self, source, destination):«»»add edge:param source: Source Vertex:param destination: Destination Vertex«»»# Adding the node to the source nodenode = AdjNode(destination)node.next = self.graph[source]self.graph[source] = node# Adding the source node to the destination if undirected graph# Intentionally commented the lines#node = AdjNode(source)#node.next = self.graph[destination]#self.graph[destination] = nodedef print_graph(self):«»»A function to print a graph«»»for i in range(self.V):print(«Adjacency list of vertex {}\n head».format(i), end=»»)temp = self.graph[i]while temp:print(» -> {}».format(temp.vertex), end=»»)temp = temp.nextprint(» \n»)# Main programif __name__ == «__main__»:V = 5 # Total verticesg = 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»
- or
- result = «01234»
Взгляните и спроектируйте пошаговый алгоритм, прежде чем переходить к реализации. Попробуйте сначала решить ее самостоятельно. Если вы застряли, вы всегда можете обратиться к решению, приведенному в разделе решения.
def dfs(graph, source):«»»Function to print a DFS of graph:param graph: The graph:param source: starting vertex:return:«»»# Write your code here!pass
Solution
def dfs(my_graph, source):«»»Function to print a DFS of graph:param graph: The graph:param source: starting vertex:return: returns the traversal in a string«»»# Mark all the vertices as not visitedvisited = [False] * (len(my_graph.graph))# Create a stack for DFSstack = []# Result stringresult = «»# Push the sourcestack.append(source)while stack:# Pop a vertex from stacksource = stack.pop()if not visited[source]:result += str(source)visited[source] = True# Get all adjacent vertices of the popped vertex source.# If a adjacent has not been visited, then push itwhile my_graph.graph[source] is not None:data = my_graph.graph[source].vertexif not visited[data]:stack.append(data)my_graph.graph[source] = my_graph.graph[source].nextreturn result# Main to test the above programif __name__ == «__main__»:V = 5g = Graph(V)g.add_edge(0, 1)g.add_edge(0, 2)g.add_edge(1, 3)g.add_edge(1, 4)print(dfs(g, 0))
Мы начинаем с выбранного узла и обходим граф по слоям. Исследуются все соседние узлы. Затем мы переходим на следующий уровень. Мы перемещаемся по графику по горизонтали, иначе говоря, по каждому слою.
Граф может содержать циклы. Чтобы избежать повторной обработки одного и того же узла, мы можем использовать логический массив, который отмечает посещенные массивы. Вы можете использовать очередь, чтобы сохранить узел и пометить его как посещенный. Очередь должна соответствовать методу организации очереди «первым пришел — первым обслужен» (FIFO).
Как реализовать обход в глубину
В этой задаче необходимо реализовать обход в глубину. Для решения этой проблемы уже предоставлен ранее реализованный класс графа.
Вход: граф, представленный в виде списка смежности и начальной вершины.
Выход: строка, содержащая вершины графа, перечисленные в правильном порядке обхода.
Пример вывода:
result = "01342" or result = "02143"
Взгляните и спроектируйте пошаговый алгоритм, прежде чем переходить к реализации. Попробуйте сначала решить ее самостоятельно. Если вы застряли, вы всегда можете обратиться к решению, приведенному в разделе решения.
def dfs(graph, source):«»»Function to print a DFS of graph:param graph: The graph:param source: starting vertex:return:«»»# Write your code here!pass
Решение
def dfs(my_graph, source):«»»Function to print a DFS of graph:param graph: The graph:param source: starting vertex:return: returns the traversal in a string«»»# Mark all the vertices as not visitedvisited = [False] * (len(my_graph.graph))# Create a stack for DFSstack = []# Result stringresult = «»# Push the sourcestack.append(source)while stack:# Pop a vertex from stacksource = stack.pop()if not visited[source]:result += str(source)visited[source] = True# Get all adjacent vertices of the popped vertex source.# If a adjacent has not been visited, then push itwhile my_graph.graph[source] is not None:data = my_graph.graph[source].vertexif not visited[data]:stack.append(data)my_graph.graph[source] = my_graph.graph[source].nextreturn result# Main to test the above programif __name__ == «__main__»:V = 5g = Graph(V)g.add_edge(0, 1)g.add_edge(0, 2)g.add_edge(1, 3)g.add_edge(1, 4)print(dfs(g, 0))
Алгоритм графа в глубину использует идею поиска с возвратом. Здесь «backtrack» означает движение вперед до тех пор, пока на текущем пути больше нет узлов, а затем движение назад по тому же пути, чтобы найти узлы для прохождения.
Как убрать лезвие
В этой проблеме вы должны реализовать remove_edgeфункцию, которая принимает в качестве аргументов источник и пункт назначения. Если между ними существует край, его следует удалить.
Входные данные: график, источник (целое число) и пункт назначения (целое число).
Выход: обход графа BFS с удаленным ребром между источником и местом назначения.
Во-первых, внимательно изучите эту проблему и разработайте пошаговый алгоритм, прежде чем переходить к реализации. Попробуйте сами, прежде чем проверять решение!
def remove_edge(graph, source, destination):«»»A function to remove an edge:param graph: A graph:param source: Source Vertex:param destination: Destination Vertex«»»# Write your code here!pass
Решение
Эта задача очень похожа на удаление в связанном списке, если вы с ним знакомы.
Наши вершины хранятся в связанном списке. Сначала мы получаем доступ к sourceсвязанному списку. Если в головном узле исходного связанного списка содержится ключ, который нужно удалить, мы сдвигаем головку на один шаг вперед и возвращаем график.
Если удаляемый ключ находится в середине связанного списка, мы отслеживаем предыдущий узел и соединяем предыдущий узел со следующим узлом, когда встречается пункт назначения.
Еще вопросы на собеседовании
Ниже приведены другие вопросы собеседования, в решении которых вы можете попробовать свои силы:
- Проверьте, сильно ли связан граф.
- Подсчитайте все возможные пути между двумя вершинами.
- Подсчитайте количество узлов на заданном уровне в дереве, используя поиск в ширину (BFS)
- Подсчитайте количество деревьев в лесу.
- Определите цикл на графике.
- Найдите материнскую вершину в графе.
- Найдите K ядер неориентированного графа.
- Найдите путь в прямоугольнике с кругами.
- Используйте минимальное остовное дерево для проектирования сети
- Найдите кратчайший путь к переходу от одного простого числа к другому, меняя по одной цифре за раз.
- Найдите наименьшее двоичное число, кратное заданному числу.
- Высота общего дерева из родительского массива.
- Итеративный поиск в глубину (DFS).
- Используйте алгоритм Краскала, чтобы найти минимальный остовный лес неориентированного взвешенного по ребрам графа
- Используйте жадный алгоритм минимального связующего дерева Prim (MST)
- Минимум начальных вершин для обхода всей матрицы с заданными условиями.
- Используйте алгоритм Беллмана — Форда для вычисления кратчайших путей от вершины к другим вершинам взвешенного графа.
- Переставьте график.
- Проблема с кувшином для воды при использовании BFS.
