[BrakWolnegoLoginu]

Jest ktoś w stanie mi sprawdzić poprawność działania algorytmu BFS który napisałem? Muszę to znać na studia, a nie wiem czy dobrze zrozumiałem. Całość pisałem sam, chodzi tylko o poprawność, nie zwracajcie uwagi na nazwy zmiennych.

https://pastebin.com/Ct0gBcVE

#naukaprogramowania #python #programowanie #studia #stubaza

[zwei]

@BrakWolnegoLoginu: co to ma być ta drukowana tablica booli?

BFS to po prostu znaczy że algorytm najpierw sprawdza kolejny node zamiast się w niego zagnieżdżać. W przeciwieństwie do DFS, ktory najpierw zagnieżdża się w pierwszego napotkanego node'a, a dopiero potem sprawdza kolejny na tym samym poziomie.

[BrakWolnegoLoginu]

@zwei: Prowadzącemu chodziło o to, żeby sprawdzić czy z pierwszego wierzchołka jest osiągalny każdy inny wierzchołek. Jeśli nie to to wartość w tablicy = False

[zwei]

Prowadzącemu chodziło o to, żeby sprawdzić czy z pierwszego wierzchołka jest osiągalny każdy inny wierzchołek.

@BrakWolnegoLoginu: następnym razem umieszczaj takie dość istotne informacje w pierwszym poście :) Rozumiem, że ta lista to lista sąsiedztwa grafu, a wierzchołki liczone są od 1, tak?

[Krolik]

@BrakWolnegoLoginu: zamiast pierwszego fora możesz wrzucić to kolejki tylko sam startowy element (kolejka.append(1))

[BrakWolnegoLoginu]

@zwei: Tak, dokładnie.
@Krolik No ale wtedy nie będę chyba miał w kolejce wierzchołków które sąsiadują z 1 wierzchołkiem?

[Krolik]

@BrakWolnegoLoginu: w kolejnym kroku będziesz mieć.

[pielgrzym_wladca_egiptu]

@BrakWolnegoLoginu: git dla grafu spojnego, lepiej zaczac wrzucajac node 1 na poczatku, tez jak sprawdzasz czy byl odwiedzony to lepiej sie czyta if visited[node]: continue, a dalej robisz reszte nie zagniezdzajac, i jesli to ma byc algo w pythonie to jeszcze kolejka = deque() i przy sciagniu popleft(), pop(0) w liscie zajmuje O(n)