Teória grafov

  • načítanie grafu (n, m a potom hrany - indexy vrcholov číslované od 0)

Graf

In [1]:
n, m = [int(_) for _ in input().split()] #pocet vrcholov a hran
7 6
In [2]:
sused = [[] for v in range(n)]
In [3]:
for i in range(m):
    u, v = [int(_) for _ in input().split()]
    sused[u].append(v)
    sused[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]]

Prehľadávanie grafu

pomocou dátovej štruktúry rad (Queue; BFS), resp. zásobník (Stack, DFS)

In [5]:
import queue #modul pre rad/zasobnik
In [11]:
rad = queue.Queue() #BFS
navstiveny = [ False for v in range(n)] #vrchol v bol navstiveny
rad.put(0) #zacinajuci vrchol
while not rad.empty():
    v = rad.get()
    if navstiveny[v]: #ak sme prisli k uz spracovanemu vrcholu, tak ho preskocime/ignorujeme
        continue
    print(v)
    navstiveny[v] = True
    for u in sused[v]: #vrchol u = sused vrchola v
        if not navstiveny[u]:
            rad.put(u)
0
3
4
1
2
In [13]:
rad = queue.LifoQueue() #BFS
navstiveny = [ False for v in range(n)] #vrchol v bol navstiveny
rad.put(0) #zacinajuci vrchol
while not rad.empty():
    v = rad.get()
    if navstiveny[v]: #ak sme prisli k uz spracovanemu vrcholu, tak ho preskocime/ignorujeme
        continue
    print(v)
    navstiveny[v] = True
    for u in sused[v]: #vrchol u = sused vrchola v
        if not navstiveny[u]:
            rad.put(u)
0
3
1
2
4

Môžeme spočítať počet komponentov súvislosti. (napr. úloha Palma-18D1-E ㉍. výročie)

In [16]:
rad = queue.Queue() #BFS
navstiveny = [ False for v in range(n)] #vrchol v bol navstiveny
komponentov = 0
for vrchol in range(n): #zacneme v kazdom vrchole
    if not navstiveny[vrchol]: #ktory este nie je spracovany
        rad.put(vrchol) #zacinajuci vrchol
        komponentov += 1
        while not rad.empty():
            v = rad.get()
            if navstiveny[v]: #ak sme prisli k uz spracovanemu vrcholu, tak ho preskocime/ignorujeme
                continue
            navstiveny[v] = True
            for u in sused[v]: #vrchol u = sused vrchola v
                if not navstiveny[u]:
                    rad.put(u)
print(komponentov)
2

Najkratšia cesta z jedného vrchola do všetkých ostatných (Dijkstra)

Ohodnotený Graf

In [18]:
n, m = [int(_) for _ in input().split()] #pocet vrcholov a hran
sused = [[] for v in range(n)]
for i in range(m):
    u, v, w = [int(_) for _ in input().split()]
    sused[u].append([v, w])
    sused[v].append([u, w])
print(sused)
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]]]
In [21]:
rad = queue.PriorityQueue() #Prioritný rad (Dijkstra)
navstiveny = [ False for v in range(n)] #vrchol v bol navstiveny
rad.put([0, 3]) #pociatocna vzdialenost, zacinajuci vrchol
while not rad.empty():
    d, v = rad.get() #vyberieme vrchol s najmensou hodnotou-vzdialenostou d
    if navstiveny[v]: #ak sme prisli k uz spracovanemu vrcholu, tak ho preskocime/ignorujeme
        continue
    print(v, d)
    navstiveny[v] = True
    for u, w in sused[v]: #vrchol u = sused vrchola v, vaha w
        if not navstiveny[u]:
            rad.put([d+w, u])
3 0
0 5
5 6
1 9
4 14
2 17
6 17

Kostra grafu (Spanning tree)

In [25]:
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