Python - Графические алгоритмы

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

Обход в глубину:

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

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }


dfs(gdict, 'a')

Когда приведенный выше код выполняется, он дает следующий результат:

a b d e c

Первый обход в ширину

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

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

import collections
class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
        seen, queue = set([startnode]), collections.deque([startnode])
        while queue:
            vertex = queue.popleft()
            marked(vertex)
            for node in graph[vertex]:
                if node not in seen:
                    seen.add(node)
                    queue.append(node)

def marked(n):
    print(n)

# The graph dictionary
gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }

bfs(gdict, "a")

Когда приведенный выше код выполняется, он дает следующий результат:

a c b d e