Графы деревья поиск пути

Нахождение всех возможных путей из одной точки в другую в дереве — Python

Я пытаюсь изменить его, чтобы найти все возможные пути. Застрял на следующем моменте: как вернуть строку с уже найденным путем для следующей итерации цикла поиска из уже пройденной вершины — подставив в эту строку путь только до текущей вершины. Так же вопрос: как положить объявление списка всех путей внутрь функции, чтобы он потом не обнулялся при итерировании.

newpaths = [] # !ОБЪЯВЛЕНИЕ СПИСКА def search_all_paths(graph, start, end, path=[]): path += start if start == end: return path if start not in graph: return None for node in graph[start]: if node not in path: newpath = search_all_paths(graph, node, end, path) if newpath: print(newpath, newpaths, path) if newpath != newpaths: newpaths.append(newpath) newpath = [] path = [] # **!ВОТ ЭТОТ ПУТЬ. ** print('. ', newpath, newpaths, path) return newpaths 

2 ответа 2

В дереве путь между вершинами всегда единственный

Если задача всё-таки стоит для графа общего вида (судя по тому, что в C входят две дуги):

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

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

Двумерный массив Adj работает как словарь со списками, shl — битовый сдвиг влево

Забит граф в виде шестиугольника с большим циклом 013652, и вершина 4 соединена с 0,3,5

var Adj: array of array of Byte; Src, Dest: Integer; procedure FindRoute(V: Integer; Used: Integer; Route: string); var i, W: Integer; begin if V = Dest then Memo1.Lines.Add(Route) else for i := 0 to High(Adj[V]) do begin W := Adj[V, i]; if (Used and (1 shl W)) = 0 then FindRoute(W, Used or (1 shl W), Route + IntToStr(W) + ' '); end; end; begin SetLength(Adj, 7); SetLength(Adj[0], 3); SetLength(Adj[1], 2); SetLength(Adj[2], 2); SetLength(Adj[3], 3); SetLength(Adj[4], 3); SetLength(Adj[5], 3); SetLength(Adj[6], 2); Adj[0, 0] := 1; Adj[1, 0] := 0; Adj[0, 1] := 2; Adj[2, 0] := 0; Adj[0, 2] := 4; Adj[4, 0] := 0; Adj[1, 1] := 3; Adj[3, 0] := 1; Adj[2, 1] := 5; Adj[5, 0] := 2; Adj[3, 1] := 4; Adj[4, 1] := 3; Adj[3, 2] := 6; Adj[6, 0] := 3; Adj[4, 2] := 5; Adj[5, 1] := 4; Adj[5, 2] := 6; Adj[6, 1] := 5; Src := 0; Dest := 3; FindRoute(Src, 1 shl Src, IntToStr(Src) + ' '); end; выдача 0 1 3 0 2 5 4 3 0 2 5 6 3 0 4 3 0 4 5 6 3 

# -*- coding: utf-8 -*- # Вывод всех путей из источника в пункт назначения. # Этот код предоставлен Neelam Yadav # Адаптирован Александром Драгункиным from collections import defaultdict # Класс направленного графа, использует представление списка смежности class Graph: def __init__(self, vertices): # Нет. вершин self.V = vertices # словарь по умолчанию для хранения графа self.graph = defaultdict(list) # функция добавления ребра в граф def addEdge(self, u, v): self.graph[u].append(v) '''Рекурсивная функция для печати всех путей от 'u' до 'd'. visit [] отслеживает вершины в текущем пути. path [] хранит актуальные вершины, а path_index является текущим индексом в path[]''' def printAllPathsUtil(self, u, d, visited, path): # Пометить текущий узел как посещенный и сохранить в path visited[list(self.graph.keys()).index(u)] = True path.append(u) # Если текущая вершина совпадает с точкой назначения, то # print(current path[]) if u == d: print(path) else: # Если текущая вершина не является пунктом назначения # Повторить для всех вершин, смежных с этой вершиной for i in self.graph[u]: if visited[list(self.graph.keys()).index(i)] == False: self.printAllPathsUtil(i, d, visited, path) # Удалить текущую вершину из path[] и пометить ее как непосещенную path.pop() visited[list(self.graph.keys()).index(u)] = False # Печатает все пути от 's' до 'd' def printAllPaths(self, s, d): # Отметить все вершины как не посещенные visited = [False] * (self.V) # Создать массив для хранения путей path = [] # Рекурсивный вызов вспомогательной функции печати всех путей self.printAllPathsUtil(s, d, visited, path) # Создаём граф graph = g = Graph(len(graph.keys())) for i, v in graph.items(): for e in v: g.addEdge(i, e) s = 'A' d = 'C' print ("Ниже приведены все различные пути от <> до <> :".format(s, d)) g.printAllPaths(s, d) 

Ниже приведены все различные пути от A до C : ['A', 'B', 'C'] ['A', 'B', 'D', 'C'] ['A', 'C'] 

Источник

Графы деревья поиск пути

2. Поиск в глубину (Depth First Searching)

Поиск в глубину или обход в глубину — это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных.

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

Простой алгоритм, который нужно запомнить, для DFS:

1. Посетите соседнюю непосещенную вершину. Отметьте как посещенную. Отобразите это. Добавьте в стек.
2. Если смежная вершина не найдена, то вершина берется из стека. Стек выведет все вершины, у которых нет смежных вершин.
3. Повторяйте шаги 1 и 2, пока стек не станет пустым.

Схематическое представление обхода DFS:

Если хочешь подтянуть свои знания по алгоритмам, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

• углубишься в теорию структур данных;
• научишься решать сложные алгоритмические задачи;
• научишься применять алгоритмы и структуры данных при разработке программ.

3. Топологическая сортировка (Topological Sorting)

Топологическая сортировка для ориентированного ациклического графа (DAG) — это линейное упорядочивание вершин, при котором вершина u предшествует v для каждого направленного ребра uv (в порядке очереди). Топологическая сортировка для графа невозможна, если граф не является DAG.

Для одного графа может применяться более одной топологической сортировки.

Простой алгоритм, который следует запомнить, для топологической сортировки:

1. Отметьте u как посещенную

2. Для всех вершин v , смежных с u , выполните:

2.1. Если v не посещенная, то:

2.2. Выполняем TopoSort (не забывая про стек)

Схематическое представление топологической сортировки:

Пример топологической сортировки для этого графа:

4. Обнаружение цикла с помощью алгоритма Кана (Kahn’s Algorithm)

Алгоритм топологической сортировки Кана — это алгоритм обнаружения циклов на базе эффективной топологической сортировки.

Работа алгоритма осуществляется путем нахождения вершины без входящих в нее ребер и удаления всех исходящих ребер из этой вершины.

5. Алгоритм Дейкстры (Dijkstra’s Algorithm)

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

Ниже проиллюстрирован алгоритм кратчайшего пути с одним источником. Здесь наличие одного источника означает, что мы должны найти кратчайший путь от источника ко всем узлам.

После применения алгоритма Дейкстры:

6. Алгоритм Беллмана-Форда (Bellman Ford’s Algorithm)

Алгоритм Беллмана-Форда помогает нам найти кратчайший путь от вершины ко всем другим вершинам взвешенного графа. Он похож на алгоритм Дейкстры, но может обнаруживать графы, в которых ребра могут иметь циклы с отрицательным весом.

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

Результат алгоритма Беллмана-Форда:

7. Алгоритм Флойда-Уоршалла (Floyd-Warshall Algorithm)

Алгоритм Флойда-Уоршалла — это алгоритм поиска кратчайшего пути между всеми парами вершин во взвешенном графе. Этот алгоритм работает как для ориентированных, так и для неориентированных взвешенных графов. Но это не работает для графов с отрицательными циклами (где сумма ребер в цикле отрицательна). Здесь будет использоваться концепция динамического программирования.

Алгоритм, лежащий в основе алгоритма Флойда-Уоршалла:

8. Алгоритм Прима (Prim’s Algorithm)

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

Простой алгоритм для алгоритма Прима, который следует запомнить:

1. Выберите минимальное остовное дерево со случайно выбранной вершиной.
2. Найдите все ребра, соединяющие дерево с новыми вершинами, найдите минимум и добавьте его в дерево.
3. Продолжайте повторять шаг 2, пока мы не получим минимальное остовное дерево.

9. Алгоритм Краскала (Kruskal’s Algorithm)

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

Простой алгоритм Краскала, который следует запомнить:

1. Сначала отсортируйте все ребра по весу (от наименьшего к наибольшему).
2. Теперь возьмите ребро с наименьшим весом и добавьте его в остовное дерево. Если добавляемое ребро создает цикл, не берите такое ребро.
3. Продолжайте добавлять ребра, пока не достигнете всех вершин и не будет создано минимальное остовное дерево.

10. Алгоритм Косараджу (Kosaraju’s Algorithm)

Если мы можем достичь каждой вершины компонента из любой другой вершины этого компонента, то он называется сильно связанным компонентом (SCC). Одиночный узел всегда является SCC. Алгоритм Флойда-Уоршалла относится к методам полного перебора. Но для получения наилучшей временной сложности мы можем использовать алгоритм Косараджу.

Простой алгоритм Косараджу, который следует запомнить:

1. Выполните обход графа DFS. Поместите узел в стек перед возвратом.
2. Найдите граф транспонирования, поменяв местами ребра.
3. Извлекайте узлы один за другим из стека и снова в DFS на модифицированном графе.

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

• живые вебинары 2 раза в неделю;
• 47 видеолекций и 150 практических заданий;
• консультации с преподавателями курса.

Материалы по теме

Источники

Источник