n, m = [int(_) for _ in input().split()] #pocet vrcholov a hran
sused = [[] for v in range(n)]
for i in range(m):
u, v = [int(_) for _ in input().split()]
sused[u].append(v)
sused[v].append(u)
print(sused)
pomocou dátovej štruktúry rad (Queue; BFS), resp. zásobník (Stack, DFS)
import queue #modul pre rad/zasobnik
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)
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)
Môžeme spočítať počet komponentov súvislosti. (napr. úloha Palma-18D1-E ㉍. výročie)
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)
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)
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])
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)