do-sirky-matice.py 976 Bytes
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#!/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)