Teória grafov

$ G = (V, E) $

• vrcholy vertices, hrany edges
• jednoduchý, multigraf, orientovaný
• kompletný/úplný, bipartitný, kružnica/cyklus, cesta, strom, planárny
• 2 vrcholy ... susedné
• vrchol+hrana ... incidentné
• stupeň vrchola degree
• cesta, ťah, sled
• strom - súvislý acyklický graf
• komponenty grafu ... acyklický graf nazývame les
• hranovo/vrcholovo ohodnotený graf
• kostra grafu

• prehľadávanie grafu do hĺbky DFS, do šírky BFS
• Dijkstrov alg. - hľadanie najkratšej cesty z jedného vrcholu do všetkých (do jedného)
• Floyd-Warshall - detto medzi všetkými dvojicami vrcholov
• Jarnik/Prim, Kruskal - najlacnejšia kostra
• topologické usporiadanie

reprezentácia grafu

• zoznam hrán
• matica susednosti n x n
• matica incidencie n x m
• zoznam susedov

---

• Sú dva vrcholy $u, v$ spojené/susedné?
• Akých susedov má vrchol $v$?

reprezentácia	susedné	susedia
zoznam hrán	$O(m)$	$O(m)$
matica susednosti	$O(1)$	$O(n)$
matica incidencie	$O(m)$	$$O(n \cdot m)$$
zoznam susedov	$$O(\deg v) \subset O(n)$$	$$O(\deg 𝑣)$$

n m
i j

    7 6
    0 3
    1 2
    2 4
    4 3
    1 3
    5 6

Prehľadávanie grafu

Do šírky Breath First Search

• rad queue

Do hĺbky Depth First Search

• zásobník LifoQueue
• rekurzia

n, m = [int(_) for _ in input().split()] #pocet vrcholov a hran

7 6

susedia = [[] for v in range(n)] #zoznam susedov
for i in range(m):
    u, v = [int(_) for _ in input().split()]
    susedia[u].append(v)
    susedia[v].append(u)
print(sused)

0 3
1 2
2 4
4 3
1 3
5 6
[[3], [2, 3], [1, 4], [0, 4, 1], [2, 3], [6], [5]]

from graphviz import Graph
g = Graph()
for v in range(n):
    for sused in susedia[v]:
        if v <= sused:
            g.edge(f'{v}', f'{sused}')
g

Prehľadávanie do šírky

Počet komponentov

prehľadávanie z každého vrcholu (ktorý ešte nebol navštívený)

Najkratšia cesta

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) ]

mapa = [[znak for znak in riadok] for riadok in '''
...........
...........
....#......
....#......
....#.#....
....#.#....
......#....
......#....
'''.split()]
import queue
ciel = (6, 8)
print(ciel[0])
print(*mapa)

6
['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'] ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'] ['.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.'] ['.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.'] ['.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.'] ['.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.'] ['.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.'] ['.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.']

def da_sa(r, s): #da sa ist na poziciu [r, s]?
    if not 0 <= r < n: #cislo riadku mimo rozsah
        return False
    if not 0 <= s < m: #stlpec mimo rozsah
        return False
    return mapa[r][s] == '.'

def najdi(mapa, start, ciel): #najdi najmensi pocet krokov zo startovacie policka do cieloveho
    smery = [(0,1), (0, -1), (1, 0), (-1, 0)] #styri smery: vpravo, vlavo, dole, hore
    
    rad = queue.Queue() #do sirky
    rad.put(start)
    mapa[start[0]][start[1]] = 0
    while not rad.empty():
        r, s = rad.get()
        for smer_r, smer_s in smery:#vsetky susdne policka
            nr, ns = r+smer_r, s+smer_s #suradnice noveho policka
            if da_sa(nr, ns):
                #print(nr, ns)                
                mapa[nr][ns] = 1+ mapa[r][s]
                if nr == ciel[0] and ns == ciel[1]:
                    return mapa[nr][ns]
                rad.put( (nr, ns) ) #pridame do radu
    return -1
for riadok in mapa:
    print(*riadok)
najdi(mapa, (6, 2), (6,8))
for riadok in mapa:
    print(*riadok)

. . . . . . . . . . .
. . . . . . . . . . .
. . . . # . . . . . .
. . . . # . . . . . .
. . . . # . # . . . .
. . . . # . # . . . .
. . . . . . # . . . .
. . . . . . # . . . .
8 7 6 7 8 9 10 11 . . .
7 6 5 6 7 8 9 10 11 12 .
6 5 4 5 # 7 8 9 10 11 12
5 4 3 4 # 6 7 8 9 10 11
4 3 2 3 # 5 # 9 10 11 12
3 2 1 2 # 4 # 10 11 12 .
2 1 0 1 2 3 # 11 12 . .
3 2 1 2 3 4 # . . . .

A* algoritmus A-star

https://www.redblobgames.com/pathfinding/a-star/introduction.html

pozerá sa cez heuristický odhad vzdialenosti do cieľa a vyberá v poradí aktuálna_vzdialenosť+odhad, najjednoduchšia heuristika je https://en.wikipedia.org/wiki/Taxicab_geometry (Manhattanská vzdialenosť, L1)

def Astar(mapa, start, ciel): #najdi najmensi pocet krokov zo startovacie policka do cieloveho
    smery = [(0,1), (0, -1), (1, 0), (-1, 0)] #styri smery: vpravo, vlavo, dole, hore
    
    rad = queue.PriorityQueue() #priorita podla odhadu
    rad.put((0, start[0], start[1])) #nulova priorita/odhadovana vzdialenost, r, s
    mapa[start[0]][start[1]] = 0
    while not rad.empty():
        w, r, s = rad.get()
        for smer_r, smer_s in smery:#vsetky susedne policka
            nr, ns = r+smer_r, s+smer_s #suradnice noveho policka
            if da_sa(nr, ns):
                #print(nr, ns)                
                mapa[nr][ns] = 1+ mapa[r][s]
                if nr == ciel[0] and ns == ciel[1]:
                    return mapa[nr][ns]
                rad.put( (mapa[nr][ns]+ abs(nr-ciel[0])+abs(ns-ciel[1]), nr, ns) ) #pridame do radu
    return -1
for riadok in mapa:
    print(*riadok)
Astar(mapa, (6, 2), (6,8))
for riadok in mapa:
    print(*riadok)

. . . . . . . . . . .
. . . . . . . . . . .
. . . . # . . . . . .
. . . . # . . . . . .
. . . . # . # . . . .
. . . . # . # . . . .
. . . . . . # . . . .
. . . . . . # . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . 4 5 # 7 8 9 10 . .
. 4 3 4 # 6 7 8 9 10 .
4 3 2 3 # 5 # 9 10 11 .
3 2 1 2 # 4 # 10 11 12 .
2 1 0 1 2 3 # 11 12 . .
3 2 1 2 3 4 # . . . .

. . . . . . . . . . .
. . . . . . . . . . .
. . . . # . . . . . .
. . . . # . . . . . .
. . . . # . # . . . .
. . . . # . # . . . .
. . . . . . # . . . .
. . . . . . # . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . 4 5 # 7 8 9 10 . .
. 4 3 4 # 6 7 8 9 10 .
4 3 2 3 # 5 # 9 10 11 .
3 2 1 2 # 4 # 10 11 12 .
2 1 0 1 2 3 # 11 12 . .
3 2 1 2 3 4 # . . . .

Ohodnotené (hranovo) grafy

Floyd-Warshall

ohodnotené grafy, vzdialenosti medzi každou dvojicou vrcholov

dynamické programovanie dist[i][j][k] ... vzdialenosť z vrchola i do vrchola j ak môžeme použiť ako vrcholy na cesty vrcholy 0, ..., k

  for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) #cestu i->j rozsirime cez k, t.j. i->k->j

Dijkstra

• vypočíta najkratšie vzdialenosti z jedného vrchola do všetkých ostatných
• pri dosiahnutí cieľového vrchola sa môže ukončiť

n, m = [int(_) for _ in input().split()] #pocet vrcholov a hran
susedia = [[] for v in range(n)]
for i in range(m):
    u, v, w = [int(_) for _ in input().split()]
    susedia[u].append( (v, w) )
    susedia[v].append( (u, w) )
print(susedia)

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
5 6 11
4 6 9
[[(1, 7), (3, 5)], [(0, 7), (2, 8), (3, 9), (4, 7)], [(1, 8), (4, 5)], [(0, 5), (1, 9), (4, 15), (5, 6)], [(1, 7), (2, 5), (3, 15), (5, 8), (6, 9)], [(3, 6), (4, 8), (6, 11)], [(5, 11), (4, 9)]]

Namiesto aktualizácie doteraz najlepšej ceny vo vrchole je v nasledujúcom kóde použitý prioritný rad, ktorý vyberie najlacnejšie spojenie do nového vrcholu.

rad = queue.PriorityQueue() #Prioritný rad (Dijkstra)
navstiveny = [ False for v in range(n)] #vrchol v bol navstiveny
rad.put( (0, 3) ) #zaciname vo vrchole D, vzdialenost je nulova
while not rad.empty():
    vaha, v = rad.get() #vyberieme dalsi vrchol, teda najblizsi
    if navstiveny[v]:
        continue
    navstiveny[v] = True
    print(v, vaha) #prisli sme do vrchola v s celkovou vzdialenostou vaha
    for u, w in susedia[v]: #sused u vo vzdialenosti w
        if not navstiveny[u]:
            rad.put( (vaha+w, u) )

3 0
0 5
5 6
1 9
4 14
2 17
6 17

Dijkstra - časová zložitosť

$O\left(n^2\right)$, resp. $O\left(m + n \cdot \log n\right)$ (v závislosti od pouužitej reprezentácie)

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

$O\left(m \cdot \log^{\frac{2}{3}} n\right)$

https://arxiv.org/abs/2504.17033

Najlacnejšia kostra grafu (Mininum spanning tree)