Учебники

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

Декабрь 19, 2018

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

Глубина первого прохождения:

Также называемый поиском по глубине (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")

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

65
Share: