Select Git revision
upgrade-20210819.sql
-
Martin Mareš authoredMartin Mareš authored
do-sirky-matice.py 976 B
#!/usr/bin/python3
# Prohledávání grafu do šířky
# Graf je reprezentovaný pomocí matice sousednosti
from pprint import pprint
from collections import deque
# Načteme vstup: nejprve počet vrcholů, pak n řádků se sousedy jednotlivých vrcholů
n = int(input())
matice = [[0]*n for _ in range(n)]
for i in range(n):
for j in input().split():
j = int(j)
matice[i][j] = 1
# Pro kontrolu vypíšeme reprezentaci grafu (pprint = pretty print)
pprint(matice)
# Prohledávání do šířky
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 range(n):
if matice[u][v] == 1 and not byl_jsem[v]:
byl_jsem[v] = True
vzdalenost[v] = vzdalenost[u] + 1
fronta.append(v)
prohledej(3)