Skip to content
Snippets Groups Projects
Select Git revision
  • 2c50c6069937cab322410185c005432c52f849a6
  • master default
  • ls2021
  • ls1920
4 results

abstraktni-seznamy.py

Blame
  • abstraktni-seznamy.py 1.24 KiB
    #!/usr/bin/python3
    # Abstraktní reprezentace grafu třídou,
    # implementace třídy pomocí seznamů sousedů.
    
    from collections import deque
    
    class Graf:
        """Reprezentace grafu seznamy sousedů."""
    
        def __init__(self, n):
            self.n = n
            self.seznam_sousedu = [[] for _ in range(n)]
    
        def __repr__(self):
            return str(self.seznam_sousedu)
    
        def pridej_hranu(self, i, j):
            self.seznam_sousedu[i].append(j)
    
        # Používáme jako "for v in graf.sousede(u)"
        def sousede(self, i):
            return self.seznam_sousedu[i]
    
    
    # Původní příklad na prohledávání do šířky jsme přepsali tak,
    # aby s grafem pracoval výhradně pomocí třídy Graf.
    
    n = int(input())
    graf = Graf(n)
    for i in range(n):
        for j in input().split():
            graf.pridej_hranu(i, int(j))
    
    print(graf)
    
    def prohledej(v0):
        byl_jsem = [False] * n
        byl_jsem[v0] = True
        vzdalenost = [None] * n
        vzdalenost[v0] = 0
        fronta = deque()
        fronta.append(v0)
    
        while fronta:
            u = fronta.popleft()
            print(u, vzdalenost[u])
            for v in graf.sousede(u):
                if not byl_jsem[v]:
                    byl_jsem[v] = True
                    vzdalenost[v] = vzdalenost[u] + 1
                    fronta.append(v)
    
    prohledej(3)