Temat 8

Question 1

Czym jest DAG?

Answer 1

Skierowany graf acykliczny

Question 2

Jakiem mamy reprezentacje grafu?

Answer 2

• macierz sąsiedztwa
• lista sąsiedztwa
• lista krawędzi
• macierz incydencji

Question 3

Jakie mamy algorytmy przeszukiwania grafu? Dopasuj do nich najlepszą strukturę danych?

Answer 3

• DFS (Depth-First Search) -> kolejka FIFO
• BFS (Breadth-First Search) -> stos (kolejka LIFO)
• Best-First Search -> kolejka priorytetowa

Question 4

Jaką złożoność obliczeniową ma:
- DFS
- BFS
- Macierz sasiedztwa
- Lista sasiedztwa

Answer 4

DFS –> O(V + E)
BFS –> O(V + E)
Macierz sasiedztwa:
- pamięć: O(n^2)
- dostęp do krawędzi: O(1)
- przegląd sąsiadów: O(n)
Lista sąsiedztwa:
- pamięć: O(n + m)
- dostęp do krawędzi: O(N(v))
- przegląd sąsiadów: O(N(v))

Question 5

Kiedy używamy DFS, a kiedy BFS?

Answer 5

DFS - używamy, gdy chcemy przejrzeć graf dogłębnie

BFS - jeżeli mamy graf bez wag

Question 6

Kiedy używamy Macierzy sąsiedztwa, a kiedy lepsza jest Lista sąsiedztwa?

Answer 6

Macierz sąsiedztwa jest użyteczna dla grafów gęstych oraz gdy potrzebujemy szybki dostęp do krawędzi.

Lista sąsiedztwa jest lepsza w przypadku dużej ilości danych oraz dla grafów rzadkich.