Select Git revision
abstraktni-seznamy.py
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)