Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/env python 3
- #coding: utf-8
- def read_graph_as_lists():
- n = int(input())
- graph = {}
- for edge in range(n):
- u, *v = list(map(lambda x: int(x) - 1, input().split()))
- graph[u] = set(v)
- return graph
- def dfs(graph, start):
- '''Алгоритм поиска в глубину
- Заключается в последовательном переходе от одной смежной вершине к другой, пока это возможно, с откатами к другими альтернативам, в случае когда это невозможно
- '''
- visited, stack = set(), [start]
- while stack:
- vertex = stack.pop()
- if vertex not in visited:
- visited.add(vertex)
- stack.extend(graph[vertex] - visited)
- return visited
- def bfs(graph, start):
- ''' Алгоритм поиска в ширину
- Подразумевает постепенное увеличение расстояний от начальной вершины до рассматриваемой, что позволяет избежать проблем свойственных поиску в глубину
- '''
- visited, queue = set(), [start]
- while queue:
- vertex = queue.pop(0)
- if vertex not in visited:
- visited.add(vertex)
- queue.extend(graph[vertex] - visited)
- return visited
- def transitive(graph):
- '''Алгоритм нахождения транзитивного замыкания
- Транзитивное замыкание орграфа — это орграф с тем же множеством вершин, но ребро из vi в vj существует тогда и только тогда, когда существует ориентированный путь из vi в vj в начальном орграфе. При этом считается, что вершина достижима из самой себя (то есть транзитивное замыкание содержит петли).
- '''
- # Список списков R – это замыкание.
- relation = []
- for vertex in range(len(graph)):
- relation.append(dfs(graph, vertex))
- return relation
- graph = read_graph_as_lists()
- transitive_graph = transitive(graph)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement