Cut vertices / Bridges (Cut edges)¶https://www.ksp.sk/kucharka/mosty_a_artikulacie/
Artikulácia/most je taký/taká vrchol/hrana, ktorého/ktorej odobratím sa zvýši počet komponentov (súvislosti) grafu ("rozpadne sa na viac častí").
Prehľadávanie do hĺbky (DFS)
n, m = 8, 10
hrany = [input().split() for i in range(m)]
A B 4 A H 6 B C 9 B E 2 B H 5 D E 15 E F 8 F G 3 F H 10 G H 14
print(*hrany)
['A', 'B', '4'] ['A', 'H', '6'] ['B', 'C', '9'] ['B', 'E', '2'] ['B', 'H', '5'] ['D', 'E', '15'] ['E', 'F', '8'] ['F', 'G', '3'] ['F', 'H', '10'] ['G', 'H', '14']
zobraz_kostru([])
zobraz_kostru(['AB'], True)
zobraz_kostru(['AB','BE'], True)
zobraz_kostru(['AB','BE', 'BH'], True)
zobraz_kostru(['AB','BE', 'BH', 'EF'], True)
zobraz_kostru(['AB','BE', 'BH', 'EF', 'FG'], True)
zobraz_kostru(['AB','BE', 'BH', 'EF', 'FG', 'BC', 'DE'], True)
rad = queue.PriorityQueue() #Prioritný rad (Dijkstra)
navstiveny = [ False for v in range(n)] #vrchol v bol navstiveny
rad.put([0, 3, None]) #pociatocna vzdialenost, zacinajuci vrchol, prichadzajuci z vrchola
suma = 0
while not rad.empty():
d, v, prichod = rad.get() #vyberieme vrchol s najmensou hodnotou-vzdialenostou d
if navstiveny[v]: #ak sme prisli k uz spracovanemu vrcholu, tak ho preskocime/ignorujeme
continue
if prichod != None:
print(v, prichod, d)
suma += d
navstiveny[v] = True
for u, w in sused[v]: #vrchol u = sused vrchola v, vaha w
if not navstiveny[u]:
rad.put([w, u, v])
print("Cena kostry:", suma)
0 3 5 5 3 6 1 0 7 4 1 7 2 4 5 6 4 9 Cena kostry: 39
zobraz_kostru([])
zobraz_kostru(['BE'])
zobraz_kostru(['BE', 'FG'])
zobraz_kostru(['BE', 'FG', 'AB'])
zobraz_kostru(['BE', 'FG', 'AB', 'BH'])
Hranu AH nepridáme, lebo už sú spojené červenou cestou (už sú v jednom komponente grafu s červenými hranami). Hranu EF pridá
me.
zobraz_kostru(['BE', 'FG', 'AB', 'BH', 'EF'])
Union & Find (Disjoint-set)¶Máme prvky rozdelené do množín. Každý prvok je v práve jednej množine. Chceme vedieť efektívne zistiť, v ktorej množine je prvok a vediet efetktívne spojiť dve množiny do jednej.
MakeSet(x): z prvku vytvorí jednoprvkovú mnozinuFind(x): zisti, v ktorej množine je xUnion(x, y): spojí množiny, ktoré obsahujú x,yhttps://en.wikipedia.org/wiki/Iterated_logarithm
$$\log ^{*}n = {\begin{cases}0&{\mbox{ak }}n\leq 1\\1+\log ^{*}(\log n)&{\mbox{inak}}\end{cases}}$$rastie veľmi pomaly
$2^{65536}$ má skoro 20000 miest, zaberá 8kiB, vo vesmíre je len $2^{240}$ atómov
len(str(2**65536))
19729
(2**65536).bit_length()/8/1024
8.0001220703125
Maximum flow¶https://en.wikipedia.org/wiki/Maximum_flow_problem
https://ksp.mff.cuni.cz/kucharky/toky-v-sitich/
doprava ropy/plynu ... niektoré spojenia sú obojsmerné (je možné zapojiť reverzný tok) https://www.trend.sk/spravy/energetika-reverzny-tok-plynu-jamale-vyskocil-piatok-stvornasobok
Len jeden zdroj source a jedno ústie sink
Iterovanie, postupné vylepšovanie ... hrany nevyužité naplno:
