$G = (V, E)$ ... množina vrcholov a hrán
$|V| = n$
$|E| = m$
vrcholy ... susedné hrana+vrchol ... incidentné
multihrany, slučka
sled, ťah, cesta
stupeň vrchola
cesta ... postupnosť vrcholov a hrán
cena hrany
orientovanosť
súvislosť
počet komponentov (súvislosti)| zápis grafu | u,v sú susedné | zoznam susedov |
|---|---|---|
| matica susednosti | $O(1)$ | $O(n)$ |
| množina vrcholov a hrán | $O(m)$ | $O(m)$ |
| zoznam susedov | $O(\deg_G v)$ | . |
| matica incidencie | $O(m)$ | $O(m+n.\deg_G v)$ |
počet komponentov ... prehľadávanie z každého vrcholu (ktorý ešte nebol navštívený)
#Počet komponentov
#DFS - prehladavanie do hlbky
ads = Queue() #vytvorime prazdny RAD
navstivene = [False for v in range(n)] #pre kazdy vrchol si budeme pamatat ci uz bol navstiveny/spracovany
pocet = 0
for vrchol in range(n):
if not navstivene[vrchol]: #ak este nebol navstiveny
komponent = []
ads.put(vrchol) #zacneme v jednom vrchole a chceme prehladat komponent suvislosti z neho
while not ads.empty():
v = ads.get() #vyberieme dalsi vrchol a ideme ho spracovat
if not navstivene[v]: #ak sme vlozili viackrat pred spracovanim (vid vrchol 1 v obrazku), tak spracujeme iba raz
komponent.append(v)
navstivene[v] = True
for sused in susedia[v]: #prejdeme vsetkych susedov
if not navstivene[sused]:
ads.put(sused) #vlozime suseda do ADS
print(komponent)
pocet += 1
pocet
from queue import Queue
n, m = 8, 11
bludisko= [[znak for znak in riadok] for riadok in '''
...........
...........
....#......
....#......
....#.#....
....#.#....
......#....
......#....
'''.split()]
rS, sS = 6,2
def da_sa(r, s):
return 0 <= r < n and 0 <= s < m and bludisko[r][s] == '.'
pohyby = [ (0, 1), (0, -1), (-1, 0), (1, 0) ]
rad = Queue()
rad.put( (rS, sS) )#zaciname v startovacom policku
bludisko[rS][sS] = 0
#postupne prechadzame rad
while not rad.empty():
#vyberieme jedno policko
r, s = rad.get()
#vlozime vsetkych jeho susedov, kde sa da ist vo vzdialenosti o jedna vacsej
for posun_r, posun_s in pohyby:
n_r, n_s = r+posun_r, s+posun_s
if da_sa(n_r, n_s):
bludisko[n_r][n_s] = bludisko[r][s]+1 # o jedno viac
rad.put( (n_r, n_s) ) #pridame do radu
pohyby = [ (0, 1), (0, -1), (-1, 0), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1) ]
pohyby = [ (2, 1), (2, -1), (-1, 2), (1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2) ]
start = 'D'
from queue import PriorityQueue
rad = PriorityQueue()
navstivene = {}
for i in range(n):
navstivene[chr(ord('A')+i)] = False #prazdny zoznam susedov
rad.put( (0, start) ) #vlozime start
while not rad.empty():
vzd, v = rad.get()
if not navstivene[v]: #iba ak sme tu prvykrat
navstivene[v] = True
print(v, vzd)
for vrchol, vzdialenost in susedia[v]:
if not navstivene[vrchol]: #iba ak este nebol spracovany/navstiveny
rad.put( (vzd+vzdialenost, vrchol) )#pridame dvojicu
print('...', vrchol, vzd+vzdialenost) #aby sme videli priebeh
#matica[][] ... vaha, resp. float(inf) ak nexistuje
for i in range(n):
for j in range(n):
for k in range(n):
matica[j][k] = min(matica[j][k],
matica[j][i]+matica[i][k]) #skus cez mesto i
https://www.redblobgames.com/pathfinding/a-star/introduction.html
Niektoré políčka nemá zmysel prechádzať, lebo z nich ešte potrebujeme minimálne dosť veľa krokov do cieľa (ak by nebola žiadna prekážka) ...
Ako preferovať políčka smerom k cieľovému?
Ako spočítame minimálnu vzdialenosť, ak máme dané súradnice?
$[r_S, s_S] \rightarrow [r_C, s_C]$, napr. $[4, 2] \rightarrow [6, 8]$
$ |r_S-r_C|+|s_S-s_C| = 2+6 = 8$
Môžeme to použiť ako heuristiku, teda odhad celkovej vzdialenosti ... v prioritnom rade si budeme usporiadavať podľa odhadovanej vzdialenosti
Spanning tree¶