Advertisement
Guest User

Untitled

a guest
Nov 22nd, 2017
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.37 KB | None | 0 0
  1. #!/usr/bin/env python 3
  2. #coding: utf-8
  3.  
  4. def read_graph_as_lists():
  5.     n = int(input())
  6.     graph = {}
  7.     for edge in range(n):
  8.         u, *v = list(map(lambda x: int(x) - 1, input().split()))
  9.         graph[u] = set(v)
  10.     return graph
  11.  
  12. def dfs(graph, start):
  13.     '''Алгоритм поиска в глубину
  14.    
  15.    Заключается в последовательном переходе от одной смежной вершине к другой, пока это возможно, с откатами к другими альтернативам, в случае когда это невозможно
  16.    '''
  17.     visited, stack = set(), [start]
  18.     while stack:
  19.         vertex = stack.pop()
  20.         if vertex not in visited:
  21.             visited.add(vertex)
  22.             stack.extend(graph[vertex] - visited)
  23.     return visited
  24.            
  25. def bfs(graph, start):
  26.     ''' Алгоритм поиска в ширину
  27.    
  28.    Подразумевает постепенное увеличение расстояний от начальной вершины до рассматриваемой, что позволяет избежать проблем свойственных поиску в глубину
  29.    '''
  30.     visited, queue = set(), [start]
  31.     while queue:
  32.         vertex = queue.pop(0)
  33.         if vertex not in visited:
  34.             visited.add(vertex)
  35.             queue.extend(graph[vertex] - visited)
  36.     return visited
  37.  
  38. def transitive(graph):
  39.     '''Алгоритм нахождения транзитивного замыкания
  40.    
  41.    Транзитивное замыкание орграфа — это орграф с тем же множеством вершин, но ребро из vi в vj существует тогда и только тогда, когда существует ориентированный путь из vi в vj в начальном орграфе. При этом считается, что вершина достижима из самой себя (то есть транзитивное замыкание содержит петли).
  42.    '''
  43.     # Список списков R – это замыкание.
  44.     relation = []
  45.     for vertex in range(len(graph)):
  46.         relation.append(dfs(graph, vertex))
  47.     return relation
  48.  
  49. graph = read_graph_as_lists()
  50. transitive_graph = transitive(graph)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement