Реализация BFS и DFS
Топологический вид DAG — это частичное линейное упорядочение его узлов, такое что, если этот граф имеет ребро, направленное от u к v, u должны быть расположены в порядке перед v. Частичный порядок очень полезен во многих ситуациях. Планирование проблем, разрешение зависимостей.
Некоторые полезные термины для графиков
- Inстепень — количество ребер, указывающих на него.
- Outgrade — количество ребер, выходящих из вершины.
- Исходная вершина — вершина без ребер, указывающих на нее. У него есть края, которые направлены только наружу.
- Sink Vertex — вершина без исходящих ребер. У него есть края, которые указывают только на него.
Алгоритм Кана (BFS)
Шаги
- Сохраните степени входа всех узлов в графе.
- Определите узлы со степенью вхождения 0. Добавьте каждый узел в очередь, которая будет повторяться.
- Пока набор, содержащий узлы со степенью вхождения 0, не пуст, удалите узел. Сохраните узел в списке результатов. Для каждого удаленного узла выполните итерацию по его краям, уменьшая степень вхождения каждого целевого узла на краю. Если узел теперь имеет степень вхождения 0, добавьте его в очередь и список на шаге 2.
- Наконец, верните список, к которому добавлен каждый узел. Это будет содержать топологический порядок узлов.
Реализация кода
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices
def add_edge(self, u, v):
self.graph[u-1].append(v-1)
def topological_sort(self):
in_degree = [0]*(self.V)
visited = [0]*(self.V)
for i in self.graph:
for j in self.graph[i]:
in_degree[j] += 1
top_order = []
queue = []
from heapq import heappush, heappop
for i in range(self.V):
if in_degree[i] == 0:
heappush(queue, i)
while queue:
u = heappop(queue)
if not visited[u]:
top_order.append(u+1)
for i in self.graph[u]:
in_degree[i] -= 1
if in_degree[i] == 0:
heappush(queue, i)
visited[u] = 1
return top_order
## Driver code
A = 6
B = [[6, 3], [6, 1], [5, 1], [5, 2], [3, 4], [4, 2]]
graph = Graph(A)
for u, v in B:
graph.add_edge(u, v)
res = graph.topological_sort()
print(res) # [5, 6, 1, 3, 4, 2]
В приведенной выше реализации я использовал heapq, так как хотел, чтобы результат был лексикографически наименьшим, если у нас есть несколько заказов. Кроме того, я использовал (u-1 и v-1), так как я использую индексирование узлов на основе 1.
Модифицированный поиск в глубину
Шаги
- Начните с любой вершины и вызовите на ней функцию DFS.
- Продолжайте двигаться по этому пути, пока не найдете узел, у которого больше нет исходящих ребер.
- Добавляем его в топологический порядок (вставляем в стек по 0-му индексу, иначе получим обратный порядок).
- Возврат к предыдущему узлу с дальнейшими непосещенными потомками.
- Продолжайте, пока не посетите все узлы.
Реализация кода
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices
def add_edge(self, u, v):
self.graph[u-1].append(v-1)
def helper(self,u,visited, res):
visited[u] = True
for i in self.graph[u]:
if visited[i] == False:
self.helper(i, visited, res)
res.insert(0, u+1)
def topological_sort(self):
visited = [False]*self.V
res =[]
for i in reversed(range(self.V)):
if visited[i] == False:
self.helper(i, visited, res)
return res
## Driver code
A = 6
B = [[6, 3], [6, 1], [5, 1], [5, 2], [3, 4], [4, 2]]
graph = Graph(A)
for u, v in B:
graph.add_edge(u, v)
res = graph.topological_sort()
print(res) # [5, 6, 1, 3, 4, 2]
В приведенной выше реализации я использовал reverse(range(self.V)) , так как хотел, чтобы результат был лексикографически наименьшим, если у нас есть несколько заказов.
Удачного кодирования!
Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter и LinkedIn. Посетите наш Community Discord и присоединитесь к нашему Коллективу талантов.
