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

как использовать алгоритмы на графах Программирование и разработка

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

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

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

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

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

Алгоритмы графов используются для решения проблем представления

Алгоритмы графов используются для решения проблем представления графов в виде сетей, таких как рейсы авиакомпаний, подключение к Интернету или подключение к социальным сетям на 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
Читайте также:  Объектно-ориентированное программирование на Python

Tree

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

Loop

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

В графе, если ребро проведено от вершины к самому себе

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

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

Adjacency Matrix

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

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

  a b c d e
1 1 - - -
- - 1 - -
- - - 1 -
- 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 = data
        self.next = None
class Graph:
    «»»
    Graph Class ADT
    «»»
    def __init__(self, vertices):
        «»»
        Constructor
        :param vertices : Total vertices in a graph
        «»»
        self.V = vertices
        self.graph = [None] * self.V
        # Function to add an edge in an undirected graph
    def add_edge(self, source, destination):
        «»»
        add edge
        :param source: Source Vertex
        :param destination: Destination Vertex
        «»»
        # Adding the node to the source node
        node = 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] = node
    def 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.next
            print(» \n»)
# Main program
if __name__ == «__main__»:
    V = 5  # Total vertices
    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»
  • 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 visited
    visited = [False] * (len(my_graph.graph))
    # Create a stack for DFS
    stack = []
    # Result string
    result = «»
    # Push the source
    stack.append(source)
    while stack:
        # Pop a vertex from stack
        source = 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 it
        while my_graph.graph[source] is not None:
            data = my_graph.graph[source].vertex
            if not visited[data]:
                stack.append(data)
            my_graph.graph[source] = my_graph.graph[source].next
    return result
# Main to test the above program
if __name__ == «__main__»:
    V = 5
    g = 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 visited
    visited = [False] * (len(my_graph.graph))
    # Create a stack for DFS
    stack = []
    # Result string
    result = «»
    # Push the source
    stack.append(source)
    while stack:
        # Pop a vertex from stack
        source = 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 it
        while my_graph.graph[source] is not None:
            data = my_graph.graph[source].vertex
            if not visited[data]:
                stack.append(data)
            my_graph.graph[source] = my_graph.graph[source].next
    return result
# Main to test the above program
if __name__ == «__main__»:
    V = 5
    g = 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.
Оцените статью
bestprogrammer.ru
Добавить комментарий