Python - Графовые алгоритмы - UPROGER

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

Обход на глубину

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

Пример:

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")

Выход:

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