Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Grafy - Wprowadzenie
Reprezentacje grafu
zajęcia 5.
Przeszukiwanie
grafu
Wstęp
DFS
BFS
Problemy
Marcin Andrychowicz, Tomasz Kulczyński, Błażej
Osiński
Co to jest graf?
Grafy - Wpro-
wadzenie
Graf
Wstęp
jest to obiekt matematyczny, który można wyobrażać
Podstawowe pojęcia
Rodzaje grafów
sobie jako mapę, zawierającą miasta i drogi
Problemy grafowe
Reprezentacje grafu
składa się ze zbioruwierzchołków(miast) i
Przeszukiwanie
grafu krawędzi(dróg)
Wstęp
DFS
dla wygody wierzchołki będziemy numerować kolejnymi
BFS
liczbami naturalnymi 1, 2, . . .
Problemy
oto przykładowy graf o 7 wierzchołkach i 8
krawędziach:
1 2 3 6
5 4 7
Co to jest graf?
Grafy - Wpro-
wadzenie
Graf
Wstęp
jest to obiekt matematyczny, który można wyobrażać
Podstawowe pojęcia
Rodzaje grafów
sobie jako mapę, zawierającą miasta i drogi
Problemy grafowe
Reprezentacje grafu
składa się ze zbioruwierzchołków(miast) i
Przeszukiwanie
grafu krawędzi(dróg)
Wstęp
DFS
dla wygody wierzchołki będziemy numerować kolejnymi
BFS
liczbami naturalnymi 1, 2, . . .
Problemy
oto przykładowy graf o 7 wierzchołkach i 8
krawędziach:
1 2 3 6
5 4 7
Co to jest graf?
Grafy - Wpro-
wadzenie
Graf
Wstęp
jest to obiekt matematyczny, który można wyobrażać
Podstawowe pojęcia
Rodzaje grafów
sobie jako mapę, zawierającą miasta i drogi
Problemy grafowe
Reprezentacje grafu
składa się ze zbioruwierzchołków(miast) i
Przeszukiwanie
grafu krawędzi(dróg)
Wstęp
DFS
dla wygody wierzchołki będziemy numerować kolejnymi
BFS
liczbami naturalnymi 1, 2, . . .
Problemy
oto przykładowy graf o 7 wierzchołkach i 8
krawędziach:
1 2 3 6
5 4 7
Co to jest graf?
Grafy - Wpro-
wadzenie
Graf
Wstęp
jest to obiekt matematyczny, który można wyobrażać
Podstawowe pojęcia
Rodzaje grafów
sobie jako mapę, zawierającą miasta i drogi
Problemy grafowe
Reprezentacje grafu
składa się ze zbioruwierzchołków(miast) i
Przeszukiwanie
grafu krawędzi(dróg)
Wstęp
DFS
dla wygody wierzchołki będziemy numerować kolejnymi
BFS
liczbami naturalnymi 1, 2, . . .
Problemy
oto przykładowy graf o 7 wierzchołkach i 8
krawędziach:
1 2 3 6
5 4 7
Gdzie występują grafy?
Grafy - Wpro-
wadzenie
Przykładowe zastosowania grafów:
Wstęp
Podstawowe pojęcia
Mamy daną mapę i chcemy wiedzieć czy z miasta A da
Rodzaje grafów
Problemy grafowe
się dojechać do miasta B.
Reprezentacje grafu
Przeszukiwanie
Mamy daną mapę i chcemy dowiedzieć się jak
grafu
Wstęp
najszybciej można przejechać z miasta A do miasta B.
DFS
BFS
Mamy dany zbiór zadań do wykonania i zbiór
Problemy
pracowników. Dla każdego zadania, wiemy, którzy
pracownicy potrafią je wykonać. Chcemy wiedzieć, czy
da się przydzielić każdemu pracownikowi co najwyżej
jedno zadanie, tak aby wszystkie zadania zostały
wykonane.
Gdzie występują grafy?
Grafy - Wpro-
wadzenie
Przykładowe zastosowania grafów:
Wstęp
Podstawowe pojęcia
Mamy daną mapę i chcemy wiedzieć czy z miasta A da
Rodzaje grafów
Problemy grafowe
się dojechać do miasta B.
Reprezentacje grafu
Przeszukiwanie
Mamy daną mapę i chcemy dowiedzieć się jak
grafu
Wstęp
najszybciej można przejechać z miasta A do miasta B.
DFS
BFS
Mamy dany zbiór zadań do wykonania i zbiór
Problemy
pracowników. Dla każdego zadania, wiemy, którzy
pracownicy potrafią je wykonać. Chcemy wiedzieć, czy
da się przydzielić każdemu pracownikowi co najwyżej
jedno zadanie, tak aby wszystkie zadania zostały
wykonane.
Gdzie występują grafy?
Grafy - Wpro-
wadzenie
Przykładowe zastosowania grafów:
Wstęp
Podstawowe pojęcia
Mamy daną mapę i chcemy wiedzieć czy z miasta A da
Rodzaje grafów
Problemy grafowe
się dojechać do miasta B.
Reprezentacje grafu
Przeszukiwanie
Mamy daną mapę i chcemy dowiedzieć się jak
grafu
Wstęp
najszybciej można przejechać z miasta A do miasta B.
DFS
BFS
Mamy dany zbiór zadań do wykonania i zbiór
Problemy
pracowników. Dla każdego zadania, wiemy, którzy
pracownicy potrafią je wykonać. Chcemy wiedzieć, czy
da się przydzielić każdemu pracownikowi co najwyżej
jedno zadanie, tak aby wszystkie zadania zostały
wykonane.
Oznaczenia
Grafy - Wpro-
wadzenie
Oznaczenia
Wstęp
Podstawowe pojęcia
V (G) - zbiór wierzchołków grafu G
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
E(G) - zbiór krawędzi grafu G
Przeszukiwanie
grafu notacja skrócona: V i E
Wstęp
DFS
przykład:
BFS
1 2 3 6
Problemy
5 4 7
V = {1, 2, 3, 4, 5, 6, 7}
E = {(1, 2), (2, 3), (3, 4), (4, 5), (2, 5), (3, 6), (6, 7)}
Oznaczenia
Grafy - Wpro-
wadzenie
Oznaczenia
Wstęp
Podstawowe pojęcia
V (G) - zbiór wierzchołków grafu G
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
E(G) - zbiór krawędzi grafu G
Przeszukiwanie
grafu notacja skrócona: V i E
Wstęp
DFS
przykład:
BFS
1 2 3 6
Problemy
5 4 7
V = {1, 2, 3, 4, 5, 6, 7}
E = {(1, 2), (2, 3), (3, 4), (4, 5), (2, 5), (3, 6), (6, 7)}
Oznaczenia
Grafy - Wpro-
wadzenie
Oznaczenia
Wstęp
Podstawowe pojęcia
V (G) - zbiór wierzchołków grafu G
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
E(G) - zbiór krawędzi grafu G
Przeszukiwanie
grafu notacja skrócona: V i E
Wstęp
DFS
przykład:
BFS
1 2 3 6
Problemy
5 4 7
V = {1, 2, 3, 4, 5, 6, 7}
E = {(1, 2), (2, 3), (3, 4), (4, 5), (2, 5), (3, 6), (6, 7)}
Oznaczenia
Grafy - Wpro-
wadzenie
Oznaczenia
Wstęp
Podstawowe pojęcia
V (G) - zbiór wierzchołków grafu G
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
E(G) - zbiór krawędzi grafu G
Przeszukiwanie
grafu notacja skrócona: V i E
Wstęp
DFS
przykład:
BFS
1 2 3 6
Problemy
5 4 7
V = {1, 2, 3, 4, 5, 6, 7}
E = {(1, 2), (2, 3), (3, 4), (4, 5), (2, 5), (3, 6), (6, 7)}
Ścieżka
Grafy - Wpro-
wadzenie
Wstęp Ścieżka
Podstawowe pojęcia
Rodzaje grafów
ścieżkąłączącą wierzchołki v0 i vn nazywamy ciąg
Problemy grafowe
Reprezentacje grafu
(v0, v1, . . . , vn), taki, że każde dwa kolejne wierzchołki,
Przeszukiwanie
tego ciągu są połączone krawędzią
grafu
Wstęp
ścieżka (1, 2, 3, 4) łączącą wierzchołki 1 i 4:
DFS
BFS
1 2 3 6
Problemy
5 4 7
długościąścieżki nazywamy ilość krawędzi na tej
ścieżce; powyższa ścieżka ma długość 3
Ścieżka
Grafy - Wpro-
wadzenie
Wstęp Ścieżka
Podstawowe pojęcia
Rodzaje grafów
ścieżkąłączącą wierzchołki v0 i vn nazywamy ciąg
Problemy grafowe
Reprezentacje grafu
(v0, v1, . . . , vn), taki, że każde dwa kolejne wierzchołki,
Przeszukiwanie
tego ciągu są połączone krawędzią
grafu
Wstęp
ścieżka (1, 2, 3, 4) łączącą wierzchołki 1 i 4:
DFS
BFS
1 2 3 6
Problemy
5 4 7
długościąścieżki nazywamy ilość krawędzi na tej
ścieżce; powyższa ścieżka ma długość 3
Ścieżka
Grafy - Wpro-
wadzenie
Wstęp Ścieżka
Podstawowe pojęcia
Rodzaje grafów
ścieżkąłączącą wierzchołki v0 i vn nazywamy ciąg
Problemy grafowe
Reprezentacje grafu
(v0, v1, . . . , vn), taki, że każde dwa kolejne wierzchołki,
Przeszukiwanie
tego ciągu są połączone krawędzią
grafu
Wstęp
ścieżka (1, 2, 3, 4) łączącą wierzchołki 1 i 4:
DFS
BFS
1 2 3 6
Problemy
5 4 7
długościąścieżki nazywamy ilość krawędzi na tej
ścieżce; powyższa ścieżka ma długość 3
Droga
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Droga
Problemy grafowe
Reprezentacje grafu
jest to ścieżka, której wszystkie wierzchołki są różne
Przeszukiwanie
grafu
ścieżka (1, 2, 3, 6, 7, 3, 4), NIE będą drogą, łączącą
Wstęp
DFS
wierzchołki 1 i 4:
BFS
1 2 3 6
Problemy
5 4 7
Droga
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Droga
Problemy grafowe
Reprezentacje grafu
jest to ścieżka, której wszystkie wierzchołki są różne
Przeszukiwanie
grafu
ścieżka (1, 2, 3, 6, 7, 3, 4), NIE będą drogą, łączącą
Wstęp
DFS
wierzchołki 1 i 4:
BFS
1 2 3 6
Problemy
5 4 7
Cykl
Grafy - Wpro-
wadzenie
Wstęp
Cykl
Podstawowe pojęcia
Rodzaje grafów
jest to ścieżka, której pierwszy i ostatni wierzchołek są
Problemy grafowe
Reprezentacje grafu
takie same
Przeszukiwanie
grafu
przykładowy cykl długości 4:
Wstęp
DFS
1 2 3 6
BFS
Problemy
5 4 7
cyklprostyto cykl na którym wierzchołki się nie
powtarzają (nie licząc pierwszego i ostatniego)
Cykl
Grafy - Wpro-
wadzenie
Wstęp
Cykl
Podstawowe pojęcia
Rodzaje grafów
jest to ścieżka, której pierwszy i ostatni wierzchołek są
Problemy grafowe
Reprezentacje grafu
takie same
Przeszukiwanie
grafu
przykładowy cykl długości 4:
Wstęp
DFS
1 2 3 6
BFS
Problemy
5 4 7
cyklprostyto cykl na którym wierzchołki się nie
powtarzają (nie licząc pierwszego i ostatniego)
Cykl
Grafy - Wpro-
wadzenie
Wstęp
Cykl
Podstawowe pojęcia
Rodzaje grafów
jest to ścieżka, której pierwszy i ostatni wierzchołek są
Problemy grafowe
Reprezentacje grafu
takie same
Przeszukiwanie
grafu
przykładowy cykl długości 4:
Wstęp
DFS
1 2 3 6
BFS
Problemy
5 4 7
cyklprostyto cykl na którym wierzchołki się nie
powtarzają (nie licząc pierwszego i ostatniego)
Stopień wierzchołka
Grafy - Wpro-
wadzenie
Wstęp Stopień wierzchołka
Podstawowe pojęcia
Rodzaje grafów
to liczba wychodzących z niego krawędzi
Problemy grafowe
Reprezentacje grafu
stopień wierzchołka i oznaczamy deg[i]
Przeszukiwanie
grafu
przykładowy graf i stopnie poszczególnych
Wstęp
DFS
wierzchołków:
BFS
1 2 3 6
Problemy
5 4 7
i 1 2 3 4 5 6 7
deg[i] 1 3 4 2 2 2 2
Stopień wierzchołka
Grafy - Wpro-
wadzenie
Wstęp Stopień wierzchołka
Podstawowe pojęcia
Rodzaje grafów
to liczba wychodzących z niego krawędzi
Problemy grafowe
Reprezentacje grafu
stopień wierzchołka i oznaczamy deg[i]
Przeszukiwanie
grafu
przykładowy graf i stopnie poszczególnych
Wstęp
DFS
wierzchołków:
BFS
1 2 3 6
Problemy
5 4 7
i 1 2 3 4 5 6 7
deg[i] 1 3 4 2 2 2 2
Stopień wierzchołka
Grafy - Wpro-
wadzenie
Wstęp Stopień wierzchołka
Podstawowe pojęcia
Rodzaje grafów
to liczba wychodzących z niego krawędzi
Problemy grafowe
Reprezentacje grafu
stopień wierzchołka i oznaczamy deg[i]
Przeszukiwanie
grafu
przykładowy graf i stopnie poszczególnych
Wstęp
DFS
wierzchołków:
BFS
1 2 3 6
Problemy
5 4 7
i 1 2 3 4 5 6 7
deg[i] 1 3 4 2 2 2 2
Spójność
Grafy - Wpro-
wadzenie
Spójność
Wstęp
graf nazywamy spójnym, jeśli istnieje ścieżka łącząca
Podstawowe pojęcia
Rodzaje grafów
dowolne dwa jego wierzchołki
Problemy grafowe
Reprezentacje grafu
przykład grafu spójnego:
Przeszukiwanie
grafu
1 2 3 6
Wstęp
DFS
BFS
5 4 7
Problemy
przykład grafu niespójnego:
1 2 3 6
5 4 7
Spójność
Grafy - Wpro-
wadzenie
Spójność
Wstęp
graf nazywamy spójnym, jeśli istnieje ścieżka łącząca
Podstawowe pojęcia
Rodzaje grafów
dowolne dwa jego wierzchołki
Problemy grafowe
Reprezentacje grafu
przykład grafu spójnego:
Przeszukiwanie
grafu
1 2 3 6
Wstęp
DFS
BFS
5 4 7
Problemy
przykład grafu niespójnego:
1 2 3 6
5 4 7
Spójność
Grafy - Wpro-
wadzenie
Spójność
Wstęp
graf nazywamy spójnym, jeśli istnieje ścieżka łącząca
Podstawowe pojęcia
Rodzaje grafów
dowolne dwa jego wierzchołki
Problemy grafowe
Reprezentacje grafu
przykład grafu spójnego:
Przeszukiwanie
grafu
1 2 3 6
Wstęp
DFS
BFS
5 4 7
Problemy
przykład grafu niespójnego:
1 2 3 6
5 4 7
Multigrafy
Grafy - Wpro-
wadzenie
Multigraf
Wstęp
to graf w którym parę wierzchołków może łączyć więcej
Podstawowe pojęcia
Rodzaje grafów
niż jedna krawędz
(tzw.krawędzie wielokrotne):
Problemy grafowe
Reprezentacje grafu
1 2 3 6
Przeszukiwanie
grafu
Wstęp
5
DFS 4 7
BFS
Problemy
lub zawierający krawędz
łączącą wierzchołek z samym
sobą (tzw.pętla):
1 2 3 6
5 4 7
Multigrafy
Grafy - Wpro-
wadzenie
Multigraf
Wstęp
to graf w którym parę wierzchołków może łączyć więcej
Podstawowe pojęcia
Rodzaje grafów
niż jedna krawędz
(tzw.krawędzie wielokrotne):
Problemy grafowe
Reprezentacje grafu
1 2 3 6
Przeszukiwanie
grafu
Wstęp
5
DFS 4 7
BFS
Problemy
lub zawierający krawędz
łączącą wierzchołek z samym
sobą (tzw.pętla):
1 2 3 6
5 4 7
Digrafy
Grafy - Wpro-
wadzenie
Digraf  graf skierowany
Wstęp
to graf którego krawędzie sąskierowane, czyli
Podstawowe pojęcia
Rodzaje grafów
posiadają wyróżniony początek i koniec
Problemy grafowe
Reprezentacje grafu
skierowanie może przykładowo oznaczać, że dana
Przeszukiwanie
grafu
droga jest jednokierunkowa
Wstęp
DFS
przykładowy digraf:
BFS
1 2 3 6
Problemy
5 4 7
nowa definicja ścieżki
(2, 3, 6) NIE jest ścieżką
(2, 5, 4, 3, 6) jest ścieżką
Digrafy
Grafy - Wpro-
wadzenie
Digraf  graf skierowany
Wstęp
to graf którego krawędzie sąskierowane, czyli
Podstawowe pojęcia
Rodzaje grafów
posiadają wyróżniony początek i koniec
Problemy grafowe
Reprezentacje grafu
skierowanie może przykładowo oznaczać, że dana
Przeszukiwanie
grafu
droga jest jednokierunkowa
Wstęp
DFS
przykładowy digraf:
BFS
1 2 3 6
Problemy
5 4 7
nowa definicja ścieżki
(2, 3, 6) NIE jest ścieżką
(2, 5, 4, 3, 6) jest ścieżką
Digrafy
Grafy - Wpro-
wadzenie
Digraf  graf skierowany
Wstęp
to graf którego krawędzie sąskierowane, czyli
Podstawowe pojęcia
Rodzaje grafów
posiadają wyróżniony początek i koniec
Problemy grafowe
Reprezentacje grafu
skierowanie może przykładowo oznaczać, że dana
Przeszukiwanie
grafu
droga jest jednokierunkowa
Wstęp
DFS
przykładowy digraf:
BFS
1 2 3 6
Problemy
5 4 7
nowa definicja ścieżki
(2, 3, 6) NIE jest ścieżką
(2, 5, 4, 3, 6) jest ścieżką
Digrafy
Grafy - Wpro-
wadzenie
Digraf  graf skierowany
Wstęp
to graf którego krawędzie sąskierowane, czyli
Podstawowe pojęcia
Rodzaje grafów
posiadają wyróżniony początek i koniec
Problemy grafowe
Reprezentacje grafu
skierowanie może przykładowo oznaczać, że dana
Przeszukiwanie
grafu
droga jest jednokierunkowa
Wstęp
DFS
przykładowy digraf:
BFS
1 2 3 6
Problemy
5 4 7
nowa definicja ścieżki
(2, 3, 6) NIE jest ścieżką
(2, 5, 4, 3, 6) jest ścieżką
Digrafy
Grafy - Wpro-
wadzenie
Digraf  graf skierowany
Wstęp
to graf którego krawędzie sąskierowane, czyli
Podstawowe pojęcia
Rodzaje grafów
posiadają wyróżniony początek i koniec
Problemy grafowe
Reprezentacje grafu
skierowanie może przykładowo oznaczać, że dana
Przeszukiwanie
grafu
droga jest jednokierunkowa
Wstęp
DFS
przykładowy digraf:
BFS
1 2 3 6
Problemy
5 4 7
nowa definicja ścieżki
(2, 3, 6) NIE jest ścieżką
(2, 5, 4, 3, 6) jest ścieżką
Digrafy
Grafy - Wpro-
wadzenie
Digraf  graf skierowany
Wstęp
to graf którego krawędzie sąskierowane, czyli
Podstawowe pojęcia
Rodzaje grafów
posiadają wyróżniony początek i koniec
Problemy grafowe
Reprezentacje grafu
skierowanie może przykładowo oznaczać, że dana
Przeszukiwanie
grafu
droga jest jednokierunkowa
Wstęp
DFS
przykładowy digraf:
BFS
1 2 3 6
Problemy
5 4 7
nowa definicja ścieżki
(2, 3, 6) NIE jest ścieżką
(2, 5, 4, 3, 6) jest ścieżką
Drzewa
Grafy - Wpro-
wadzenie
Przykładowe drzewo
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Drzewo to graf
DFS
BFS
spójny niezawierający cykli prostych (tzw.
Problemy
acykliczny)
w którym dokładnie jedna droga łączy każdą parę
wierzchołków
spójny, ale usunięcie dowolnej krawędzi rozspójnia go
wszystkie powyższe definicje są równoważne!
dla drzewa D, zachodzi |E(D)| = |V (D)| - 1
Drzewa
Grafy - Wpro-
wadzenie
Przykładowe drzewo
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Drzewo to graf
DFS
BFS
spójny niezawierający cykli prostych (tzw.
Problemy
acykliczny)
w którym dokładnie jedna droga łączy każdą parę
wierzchołków
spójny, ale usunięcie dowolnej krawędzi rozspójnia go
wszystkie powyższe definicje są równoważne!
dla drzewa D, zachodzi |E(D)| = |V (D)| - 1
Drzewa
Grafy - Wpro-
wadzenie
Przykładowe drzewo
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Drzewo to graf
DFS
BFS
spójny niezawierający cykli prostych (tzw.
Problemy
acykliczny)
w którym dokładnie jedna droga łączy każdą parę
wierzchołków
spójny, ale usunięcie dowolnej krawędzi rozspójnia go
wszystkie powyższe definicje są równoważne!
dla drzewa D, zachodzi |E(D)| = |V (D)| - 1
Drzewa
Grafy - Wpro-
wadzenie
Przykładowe drzewo
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Drzewo to graf
DFS
BFS
spójny niezawierający cykli prostych (tzw.
Problemy
acykliczny)
w którym dokładnie jedna droga łączy każdą parę
wierzchołków
spójny, ale usunięcie dowolnej krawędzi rozspójnia go
wszystkie powyższe definicje są równoważne!
dla drzewa D, zachodzi |E(D)| = |V (D)| - 1
Drzewa
Grafy - Wpro-
wadzenie
Przykładowe drzewo
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Drzewo to graf
DFS
BFS
spójny niezawierający cykli prostych (tzw.
Problemy
acykliczny)
w którym dokładnie jedna droga łączy każdą parę
wierzchołków
spójny, ale usunięcie dowolnej krawędzi rozspójnia go
wszystkie powyższe definicje są równoważne!
dla drzewa D, zachodzi |E(D)| = |V (D)| - 1
Drzewa
Grafy - Wpro-
wadzenie
Przykładowe drzewo
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Drzewo to graf
DFS
BFS
spójny niezawierający cykli prostych (tzw.
Problemy
acykliczny)
w którym dokładnie jedna droga łączy każdą parę
wierzchołków
spójny, ale usunięcie dowolnej krawędzi rozspójnia go
wszystkie powyższe definicje są równoważne!
dla drzewa D, zachodzi |E(D)| = |V (D)| - 1
Drzewa
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Drzewo rozpinające
Problemy grafowe
Reprezentacje grafu
drzewo A rozpina graf B, wtw. gdy V (A) = V (B) i
Przeszukiwanie
grafu E(A) �" E(B)
Wstęp
DFS
przykład:
BFS
1 2 3 6
Problemy
5 4 7
Drzewa
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Drzewo rozpinające
Problemy grafowe
Reprezentacje grafu
drzewo A rozpina graf B, wtw. gdy V (A) = V (B) i
Przeszukiwanie
grafu E(A) �" E(B)
Wstęp
DFS
przykład:
BFS
1 2 3 6
Problemy
5 4 7
Drzewa
Grafy - Wpro-
Przykładowe drzewo ukorzenione
wadzenie
1
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
2 5
Reprezentacje grafu
Przeszukiwanie
grafu
3 4 6
Wstęp
DFS
BFS
Definicje
Problemy
drzewoukorzenioneto drzewo, którego jeden z
wierzchołków został wyszczególniony (tzw.korzeń)
ojcemwierzchołka v nazywamy najbliższy wierzchołek
na ścieżce od v do korzenia
synemwierzchołka v nazywamy dowolny wierzchołek,
którego ojcem jest v
Drzewa
Grafy - Wpro-
Przykładowe drzewo ukorzenione
wadzenie
1
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
2 5
Reprezentacje grafu
Przeszukiwanie
grafu
3 4 6
Wstęp
DFS
BFS
Definicje
Problemy
drzewoukorzenioneto drzewo, którego jeden z
wierzchołków został wyszczególniony (tzw.korzeń)
ojcemwierzchołka v nazywamy najbliższy wierzchołek
na ścieżce od v do korzenia
synemwierzchołka v nazywamy dowolny wierzchołek,
którego ojcem jest v
Drzewa
Grafy - Wpro-
Przykładowe drzewo ukorzenione
wadzenie
1
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
2 5
Reprezentacje grafu
Przeszukiwanie
grafu
3 4 6
Wstęp
DFS
BFS
Definicje
Problemy
drzewoukorzenioneto drzewo, którego jeden z
wierzchołków został wyszczególniony (tzw.korzeń)
ojcemwierzchołka v nazywamy najbliższy wierzchołek
na ścieżce od v do korzenia
synemwierzchołka v nazywamy dowolny wierzchołek,
którego ojcem jest v
Przykładowe problemy grafowe
Grafy - Wpro-
wadzenie
Graf
Wstęp 1 2 3 6
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
5 4 7
Przeszukiwanie
grafu
Wstęp
Problemy grafowe
DFS
BFS
czy istnieje ścieżką łącząca 1 i 5?
Problemy
jaka jest najkrótsza ścieżka łącząca 1 i 5?
czy graf jest spójny?
czy graf jest acykliczny?
Odpowiedz

Przykładowe problemy grafowe
Grafy - Wpro-
wadzenie
Graf
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Problemy grafowe
DFS
BFS
czy istnieje ścieżką łącząca 1 i 5?
Problemy
jaka jest najkrótsza ścieżka łącząca 1 i 5?
czy graf jest spójny?
czy graf jest acykliczny?
Odpowiedz

TAK
Przykładowe problemy grafowe
Grafy - Wpro-
wadzenie
Graf
Wstęp 1 2 3 6
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
5 4 7
Przeszukiwanie
grafu
Wstęp
Problemy grafowe
DFS
BFS
czy istnieje ścieżką łącząca 1 i 5?
Problemy
jaka jest najkrótsza ścieżka łącząca 1 i 5?
czy graf jest spójny?
czy graf jest acykliczny?
Odpowiedz

Przykładowe problemy grafowe
Grafy - Wpro-
wadzenie
Graf
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Problemy grafowe
DFS
BFS
czy istnieje ścieżką łącząca 1 i 5?
Problemy
jaka jest najkrótsza ścieżka łącząca 1 i 5?
czy graf jest spójny?
czy graf jest acykliczny?
Odpowiedz

(1, 2, 5)
Przykładowe problemy grafowe
Grafy - Wpro-
wadzenie
Graf
Wstęp 1 2 3 6
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
5 4 7
Przeszukiwanie
grafu
Wstęp
Problemy grafowe
DFS
BFS
czy istnieje ścieżką łącząca 1 i 5?
Problemy
jaka jest najkrótsza ścieżka łącząca 1 i 5?
czy graf jest spójny?
czy graf jest acykliczny?
Odpowiedz

Przykładowe problemy grafowe
Grafy - Wpro-
wadzenie
Graf
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Problemy grafowe
DFS
BFS
czy istnieje ścieżką łącząca 1 i 5?
Problemy
jaka jest najkrótsza ścieżka łącząca 1 i 5?
czy graf jest spójny?
czy graf jest acykliczny?
Odpowiedz

NIE
Przykładowe problemy grafowe
Grafy - Wpro-
wadzenie
Graf
Wstęp 1 2 3 6
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
5 4 7
Przeszukiwanie
grafu
Wstęp
Problemy grafowe
DFS
BFS
czy istnieje ścieżką łącząca 1 i 5?
Problemy
jaka jest najkrótsza ścieżka łącząca 1 i 5?
czy graf jest spójny?
czy graf jest acykliczny?
Odpowiedz

Przykładowe problemy grafowe
Grafy - Wpro-
wadzenie
Graf
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Problemy grafowe
DFS
BFS
czy istnieje ścieżką łącząca 1 i 5?
Problemy
jaka jest najkrótsza ścieżka łącząca 1 i 5?
czy graf jest spójny?
czy graf jest acykliczny?
Odpowiedz

NIE
Reprezentacje grafu
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
Reprezentacje grafu
Przeszukiwanie
konieczność przyjęcia jakiegoś sposobu opisywania
grafu
Wstęp
grafów na wejściu
DFS
BFS
reprezentacja w programie:
Problemy
macierz sąsiedztwa
listy sąsiedztwa
Reprezentacje grafu
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
Reprezentacje grafu
Przeszukiwanie
konieczność przyjęcia jakiegoś sposobu opisywania
grafu
Wstęp
grafów na wejściu
DFS
BFS
reprezentacja w programie:
Problemy
macierz sąsiedztwa
listy sąsiedztwa
Reprezentacje grafu
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
Reprezentacje grafu
Przeszukiwanie
konieczność przyjęcia jakiegoś sposobu opisywania
grafu
Wstęp
grafów na wejściu
DFS
BFS
reprezentacja w programie:
Problemy
macierz sąsiedztwa
listy sąsiedztwa
Reprezentacje grafu
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
Reprezentacje grafu
Przeszukiwanie
konieczność przyjęcia jakiegoś sposobu opisywania
grafu
Wstęp
grafów na wejściu
DFS
BFS
reprezentacja w programie:
Problemy
macierz sąsiedztwa
listy sąsiedztwa
Reprezentacje grafu
Grafy - Wpro-
wadzenie
Graf
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Opis grafu
DFS
BFS
7 8
Problemy
2 1
2 3
3 4
4 5
5 2
3 6
. . .
Reprezentacje grafu
Grafy - Wpro-
wadzenie
Graf
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Opis grafu
DFS
BFS
7 8
Problemy
2 1
2 3
3 4
4 5
5 2
3 6
. . .
Reprezentacje grafu
Grafy - Wpro-
wadzenie
Graf
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Opis grafu
DFS
BFS
7 8
Problemy
2 1
2 3
3 4
4 5
5 2
3 6
. . .
Reprezentacje grafu
Grafy - Wpro-
wadzenie
Graf
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp
Opis grafu
DFS
BFS
7 8
Problemy
2 1
2 3
3 4
4 5
5 2
3 6
. . .
Macierz sąsiedztwa
Grafy - Wpro-
wadzenie
Graf
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Jego macierz sąsiedztwa
Wstęp
DFS
BFS
1 2 3 4 5 6 7
Problemy
1 0 1 0 0 0 0 0
2 1 0 1 0 1 0 0
3 0 1 0 1 0 1 1
4 0 0 1 0 1 0 0
5 0 1 0 1 0 0 0
6 0 0 1 0 0 0 1
7 0 0 1 0 0 1 0
Macierz sąsiedztwa
Grafy - Wpro-
wadzenie
Graf
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Jego macierz sąsiedztwa
Wstęp
DFS
BFS
1 2 3 4 5 6 7
Problemy
1 0 1 0 0 0 0 0
2 1 0 1 0 1 0 0
3 0 1 0 1 0 1 1
4 0 0 1 0 1 0 0
5 0 1 0 1 0 0 0
6 0 0 1 0 0 0 1
7 0 0 1 0 0 1 0
Macierz sąsiedztwa
Grafy - Wpro-
wadzenie
Graf
1 2 3 6
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
5 4 7
Reprezentacje grafu
Przeszukiwanie
grafu
Jego macierz sąsiedztwa
Wstęp
DFS
BFS
1 2 3 4 5 6 7
Problemy
1 0 1 0 0 0 0 0
2 1 0 1 0 1 0 0
3 0 1 0 1 0 1 1
4 0 0 1 0 1 0 0
5 0 1 0 1 0 0 0
6 0 0 1 0 0 0 1
7 0 0 1 0 0 1 0
Implementacja
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
Implementacja
grafu
Wstęp
Kod programu tworzącego reprezentację grafu w postaci
DFS
BFS
macierzy sąsiedztwa znajduje się w notatkach.
Problemy
Listy sąsiedztwa
Grafy - Wpro-
wadzenie
Graf
Wstęp
1 2 3 6
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
5 4 7
Przeszukiwanie
grafu
Wstęp
DFS Jego listy sąsiedztwa
BFS
1: 2
Problemy
2: 1 5 3
3: 2 5 4 6
4: 3 5
5: 2 4
6: 7 3
7: 3 6
Listy sąsiedztwa
Grafy - Wpro-
wadzenie
Graf
Wstęp
1 2 3 6
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
5 4 7
Przeszukiwanie
grafu
Wstęp
DFS Jego listy sąsiedztwa
BFS
1: 2
Problemy
2: 1 5 3
3: 2 5 4 6
4: 3 5
5: 2 4
6: 7 3
7: 3 6
Implementacja
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
Implementacja
grafu
Wstęp
Kod programu tworzącego reprezentację grafu w postaci list
DFS
BFS
sąsiedztwa znajduje się w notatkach.
Problemy
Przeszukiwanie grafu
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia Przeszukiwanie grafu
Rodzaje grafów
Problemy grafowe
to poruszanie się od wierzchołka do wierzchołka
Reprezentacje grafu
wzdłuż krawędzi
Przeszukiwanie
grafu
Wstęp przypomina to odkrywanie labiryntu
DFS
BFS
wiele algorytmów grafowych używa takiego modelu
Problemy
postępowania
2 podstawowe rodzaje przeszukiwań:
DFS
BFS
Przeszukiwanie grafu
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia Przeszukiwanie grafu
Rodzaje grafów
Problemy grafowe
to poruszanie się od wierzchołka do wierzchołka
Reprezentacje grafu
wzdłuż krawędzi
Przeszukiwanie
grafu
Wstęp przypomina to odkrywanie labiryntu
DFS
BFS
wiele algorytmów grafowych używa takiego modelu
Problemy
postępowania
2 podstawowe rodzaje przeszukiwań:
DFS
BFS
Przeszukiwanie grafu
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia Przeszukiwanie grafu
Rodzaje grafów
Problemy grafowe
to poruszanie się od wierzchołka do wierzchołka
Reprezentacje grafu
wzdłuż krawędzi
Przeszukiwanie
grafu
Wstęp przypomina to odkrywanie labiryntu
DFS
BFS
wiele algorytmów grafowych używa takiego modelu
Problemy
postępowania
2 podstawowe rodzaje przeszukiwań:
DFS
BFS
Przeszukiwanie grafu
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia Przeszukiwanie grafu
Rodzaje grafów
Problemy grafowe
to poruszanie się od wierzchołka do wierzchołka
Reprezentacje grafu
wzdłuż krawędzi
Przeszukiwanie
grafu
Wstęp przypomina to odkrywanie labiryntu
DFS
BFS
wiele algorytmów grafowych używa takiego modelu
Problemy
postępowania
2 podstawowe rodzaje przeszukiwań:
DFS
BFS
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Strategia
Reprezentacje grafu
jesteś w komnacie K
Przeszukiwanie
grafu
Wstęp
jeśli z K istnieje korytarz do komnaty, w której jeszcze
DFS
BFS
nie byłeś, to przejdz
do tej komnaty
Problemy
jeśli takiego korytarza nie ma, to wróć korytarzem,
którym po raz pierwszy wszedłeś do K
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Strategia
Reprezentacje grafu
jesteś w komnacie K
Przeszukiwanie
grafu
Wstęp
jeśli z K istnieje korytarz do komnaty, w której jeszcze
DFS
BFS
nie byłeś, to przejdz
do tej komnaty
Problemy
jeśli takiego korytarza nie ma, to wróć korytarzem,
którym po raz pierwszy wszedłeś do K
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Strategia
Reprezentacje grafu
jesteś w komnacie K
Przeszukiwanie
grafu
Wstęp
jeśli z K istnieje korytarz do komnaty, w której jeszcze
DFS
BFS
nie byłeś, to przejdz
do tej komnaty
Problemy
jeśli takiego korytarza nie ma, to wróć korytarzem,
którym po raz pierwszy wszedłeś do K
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
Odkrywanie labiryntu
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
DFS
Grafy - Wpro-
wadzenie
DFS
Wstęp
Przedstawiony schemat nosi nazwęDFS (deapth-first
Podstawowe pojęcia
Rodzaje grafów
search), czyli przeszukiwania w głąb.
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
Jak zapisać to na komputerze?
grafu
Wstęp
DFS
Aby zbadać wierzchołek K :
BFS
oznacz K jako odwiedzony
Problemy
zbadaj rekurencyjnie wszystkie nieodwiedzone
wierzchołki sąsiadujące z K
Choć może to wyglądać zaskakująco, powyższy algorytm to
ten sam schemat postępowania. Spójrzmy na przykład raz
jeszcze.
DFS
Grafy - Wpro-
wadzenie
DFS
Wstęp
Przedstawiony schemat nosi nazwęDFS (deapth-first
Podstawowe pojęcia
Rodzaje grafów
search), czyli przeszukiwania w głąb.
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
Jak zapisać to na komputerze?
grafu
Wstęp
DFS
Aby zbadać wierzchołek K :
BFS
oznacz K jako odwiedzony
Problemy
zbadaj rekurencyjnie wszystkie nieodwiedzone
wierzchołki sąsiadujące z K
Choć może to wyglądać zaskakująco, powyższy algorytm to
ten sam schemat postępowania. Spójrzmy na przykład raz
jeszcze.
DFS
Grafy - Wpro-
wadzenie
DFS
Wstęp
Przedstawiony schemat nosi nazwęDFS (deapth-first
Podstawowe pojęcia
Rodzaje grafów
search), czyli przeszukiwania w głąb.
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
Jak zapisać to na komputerze?
grafu
Wstęp
DFS
Aby zbadać wierzchołek K :
BFS
oznacz K jako odwiedzony
Problemy
zbadaj rekurencyjnie wszystkie nieodwiedzone
wierzchołki sąsiadujące z K
Choć może to wyglądać zaskakująco, powyższy algorytm to
ten sam schemat postępowania. Spójrzmy na przykład raz
jeszcze.
DFS
Grafy - Wpro-
wadzenie
DFS
Wstęp
Przedstawiony schemat nosi nazwęDFS (deapth-first
Podstawowe pojęcia
Rodzaje grafów
search), czyli przeszukiwania w głąb.
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
Jak zapisać to na komputerze?
grafu
Wstęp
DFS
Aby zbadać wierzchołek K :
BFS
oznacz K jako odwiedzony
Problemy
zbadaj rekurencyjnie wszystkie nieodwiedzone
wierzchołki sąsiadujące z K
Choć może to wyglądać zaskakująco, powyższy algorytm to
ten sam schemat postępowania. Spójrzmy na przykład raz
jeszcze.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
DFS
Grafy - Wpro-
Przykład
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
Wstęp 1 7
DFS
BFS
Problemy
3
5 4
Zagadka
Co tworzą krawędzie po których przeszliśmy (pogrubione)?
Drzewo rozpinające całego grafu.
Implementacja
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
Implementacja
grafu
Wstęp
DFS
Kod algorytmu DFS znajduje się w notatkach.
BFS
Problemy
DFS
Grafy - Wpro-
wadzenie
Analiza złożoności czasowej
każdy wierzchołek raz odwiedzamy i oznaczamy jako
Wstęp
Podstawowe pojęcia
odwiedzony  O(|V |)
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu dla każdego wierzchołka musimy przejrzeć wszystkich
Przeszukiwanie jego sąsiadów; ile to trwa? To już zależy od
grafu
reprezentacji grafu:
Wstęp
DFS
w przypadku macierzy sąsiedztwa: O(|V |) dla jednego
BFS
wierzchołka, czyli łącznie O(|V |2)
Problemy
w przypadku list sąsiedztwa: O(deg[K ]) dla jednego
wierzchołka, czyli łącznie O(|E|)
Podsumowując, złożoność czasowa algorytmu DFS
wynosi O(|V |2) dla grafu w postaci macierzy
sąsiedztwa i O(|E| + |V |) dla grafu w postaci list
sąsiedztwa.
DFS
Grafy - Wpro-
wadzenie
Analiza złożoności czasowej
każdy wierzchołek raz odwiedzamy i oznaczamy jako
Wstęp
Podstawowe pojęcia
odwiedzony  O(|V |)
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu dla każdego wierzchołka musimy przejrzeć wszystkich
Przeszukiwanie jego sąsiadów; ile to trwa? To już zależy od
grafu
reprezentacji grafu:
Wstęp
DFS
w przypadku macierzy sąsiedztwa: O(|V |) dla jednego
BFS
wierzchołka, czyli łącznie O(|V |2)
Problemy
w przypadku list sąsiedztwa: O(deg[K ]) dla jednego
wierzchołka, czyli łącznie O(|E|)
Podsumowując, złożoność czasowa algorytmu DFS
wynosi O(|V |2) dla grafu w postaci macierzy
sąsiedztwa i O(|E| + |V |) dla grafu w postaci list
sąsiedztwa.
DFS
Grafy - Wpro-
wadzenie
Analiza złożoności czasowej
każdy wierzchołek raz odwiedzamy i oznaczamy jako
Wstęp
Podstawowe pojęcia
odwiedzony  O(|V |)
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu dla każdego wierzchołka musimy przejrzeć wszystkich
Przeszukiwanie jego sąsiadów; ile to trwa? To już zależy od
grafu
reprezentacji grafu:
Wstęp
DFS
w przypadku macierzy sąsiedztwa: O(|V |) dla jednego
BFS
wierzchołka, czyli łącznie O(|V |2)
Problemy
w przypadku list sąsiedztwa: O(deg[K ]) dla jednego
wierzchołka, czyli łącznie O(|E|)
Podsumowując, złożoność czasowa algorytmu DFS
wynosi O(|V |2) dla grafu w postaci macierzy
sąsiedztwa i O(|E| + |V |) dla grafu w postaci list
sąsiedztwa.
DFS
Grafy - Wpro-
wadzenie
Analiza złożoności czasowej
każdy wierzchołek raz odwiedzamy i oznaczamy jako
Wstęp
Podstawowe pojęcia
odwiedzony  O(|V |)
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu dla każdego wierzchołka musimy przejrzeć wszystkich
Przeszukiwanie jego sąsiadów; ile to trwa? To już zależy od
grafu
reprezentacji grafu:
Wstęp
DFS
w przypadku macierzy sąsiedztwa: O(|V |) dla jednego
BFS
wierzchołka, czyli łącznie O(|V |2)
Problemy
w przypadku list sąsiedztwa: O(deg[K ]) dla jednego
wierzchołka, czyli łącznie O(|E|)
Podsumowując, złożoność czasowa algorytmu DFS
wynosi O(|V |2) dla grafu w postaci macierzy
sąsiedztwa i O(|E| + |V |) dla grafu w postaci list
sąsiedztwa.
DFS
Grafy - Wpro-
wadzenie
Analiza złożoności czasowej
każdy wierzchołek raz odwiedzamy i oznaczamy jako
Wstęp
Podstawowe pojęcia
odwiedzony  O(|V |)
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu dla każdego wierzchołka musimy przejrzeć wszystkich
Przeszukiwanie jego sąsiadów; ile to trwa? To już zależy od
grafu
reprezentacji grafu:
Wstęp
DFS
w przypadku macierzy sąsiedztwa: O(|V |) dla jednego
BFS
wierzchołka, czyli łącznie O(|V |2)
Problemy
w przypadku list sąsiedztwa: O(deg[K ]) dla jednego
wierzchołka, czyli łącznie O(|E|)
Podsumowując, złożoność czasowa algorytmu DFS
wynosi O(|V |2) dla grafu w postaci macierzy
sąsiedztwa i O(|E| + |V |) dla grafu w postaci list
sąsiedztwa.
DFS  analiza złożoności pamięciowej
Grafy - Wpro-
wadzenie
Potrzebujemy pamięci na:
Wstęp
Podstawowe pojęcia
tablicę wartości logicznych, mówiących czy
Rodzaje grafów
Problemy grafowe
odwiedziliśmy dany wierzchołek  O(|V |)
Reprezentacje grafu
wywołania rekurencyjne  O(|V |)
Przeszukiwanie
grafu
reprezentację grafu; ile ona zajmuje? To już zależy od
Wstęp
DFS
reprezentacji grafu:
BFS
Problemy w przypadku macierzy sąsiedztwa: O(|V |) dla jednego
wierzchołka, czyli łącznie O(|V |2)
w przypadku list sąsiedztwa: O(deg[K ]) dla jednego
wierzchołka, czyli łącznie O(|E|)
Podsumowując, złożoność pamięciowa algorytmu DFS
jest taka sama jak czasowa.
DFS  analiza złożoności pamięciowej
Grafy - Wpro-
wadzenie
Potrzebujemy pamięci na:
Wstęp
Podstawowe pojęcia
tablicę wartości logicznych, mówiących czy
Rodzaje grafów
Problemy grafowe
odwiedziliśmy dany wierzchołek  O(|V |)
Reprezentacje grafu
wywołania rekurencyjne  O(|V |)
Przeszukiwanie
grafu
reprezentację grafu; ile ona zajmuje? To już zależy od
Wstęp
DFS
reprezentacji grafu:
BFS
Problemy w przypadku macierzy sąsiedztwa: O(|V |) dla jednego
wierzchołka, czyli łącznie O(|V |2)
w przypadku list sąsiedztwa: O(deg[K ]) dla jednego
wierzchołka, czyli łącznie O(|E|)
Podsumowując, złożoność pamięciowa algorytmu DFS
jest taka sama jak czasowa.
DFS  analiza złożoności pamięciowej
Grafy - Wpro-
wadzenie
Potrzebujemy pamięci na:
Wstęp
Podstawowe pojęcia
tablicę wartości logicznych, mówiących czy
Rodzaje grafów
Problemy grafowe
odwiedziliśmy dany wierzchołek  O(|V |)
Reprezentacje grafu
wywołania rekurencyjne  O(|V |)
Przeszukiwanie
grafu
reprezentację grafu; ile ona zajmuje? To już zależy od
Wstęp
DFS
reprezentacji grafu:
BFS
Problemy w przypadku macierzy sąsiedztwa: O(|V |) dla jednego
wierzchołka, czyli łącznie O(|V |2)
w przypadku list sąsiedztwa: O(deg[K ]) dla jednego
wierzchołka, czyli łącznie O(|E|)
Podsumowując, złożoność pamięciowa algorytmu DFS
jest taka sama jak czasowa.
DFS  analiza złożoności pamięciowej
Grafy - Wpro-
wadzenie
Potrzebujemy pamięci na:
Wstęp
Podstawowe pojęcia
tablicę wartości logicznych, mówiących czy
Rodzaje grafów
Problemy grafowe
odwiedziliśmy dany wierzchołek  O(|V |)
Reprezentacje grafu
wywołania rekurencyjne  O(|V |)
Przeszukiwanie
grafu
reprezentację grafu; ile ona zajmuje? To już zależy od
Wstęp
DFS
reprezentacji grafu:
BFS
Problemy w przypadku macierzy sąsiedztwa: O(|V |) dla jednego
wierzchołka, czyli łącznie O(|V |2)
w przypadku list sąsiedztwa: O(deg[K ]) dla jednego
wierzchołka, czyli łącznie O(|E|)
Podsumowując, złożoność pamięciowa algorytmu DFS
jest taka sama jak czasowa.
DFS  analiza złożoności pamięciowej
Grafy - Wpro-
wadzenie
Potrzebujemy pamięci na:
Wstęp
Podstawowe pojęcia
tablicę wartości logicznych, mówiących czy
Rodzaje grafów
Problemy grafowe
odwiedziliśmy dany wierzchołek  O(|V |)
Reprezentacje grafu
wywołania rekurencyjne  O(|V |)
Przeszukiwanie
grafu
reprezentację grafu; ile ona zajmuje? To już zależy od
Wstęp
DFS
reprezentacji grafu:
BFS
Problemy w przypadku macierzy sąsiedztwa: O(|V |) dla jednego
wierzchołka, czyli łącznie O(|V |2)
w przypadku list sąsiedztwa: O(deg[K ]) dla jednego
wierzchołka, czyli łącznie O(|E|)
Podsumowując, złożoność pamięciowa algorytmu DFS
jest taka sama jak czasowa.
DFS  analiza złożoności pamięciowej
Grafy - Wpro-
wadzenie
Potrzebujemy pamięci na:
Wstęp
Podstawowe pojęcia
tablicę wartości logicznych, mówiących czy
Rodzaje grafów
Problemy grafowe
odwiedziliśmy dany wierzchołek  O(|V |)
Reprezentacje grafu
wywołania rekurencyjne  O(|V |)
Przeszukiwanie
grafu
reprezentację grafu; ile ona zajmuje? To już zależy od
Wstęp
DFS
reprezentacji grafu:
BFS
Problemy w przypadku macierzy sąsiedztwa: O(|V |) dla jednego
wierzchołka, czyli łącznie O(|V |2)
w przypadku list sąsiedztwa: O(deg[K ]) dla jednego
wierzchołka, czyli łącznie O(|E|)
Podsumowując, złożoność pamięciowa algorytmu DFS
jest taka sama jak czasowa.
Zastosowania algorytmu DFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problem
Problemy grafowe
Reprezentacje grafu
Czy istnieje ścieżka łącząca wierzchołki A i B.
Przeszukiwanie
grafu
Wstęp
DFS
Rozwiązanie
BFS
Uruchamiamy algorytm DFS z wierzchołka A a następnie
Problemy
sprawdzamy czy wierzchołek B jest oznaczony jako
odwiedzony.
Zastosowania algorytmu DFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problem
Problemy grafowe
Reprezentacje grafu
Czy istnieje ścieżka łącząca wierzchołki A i B.
Przeszukiwanie
grafu
Wstęp
DFS
Rozwiązanie
BFS
Uruchamiamy algorytm DFS z wierzchołka A a następnie
Problemy
sprawdzamy czy wierzchołek B jest oznaczony jako
odwiedzony.
Zastosowania algorytmu DFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problem
Problemy grafowe
Reprezentacje grafu
Czy graf jest spójny?
Przeszukiwanie
grafu
Wstęp
DFS
Rozwiązanie
BFS
Uruchamiamy algorytm DFS z dowolnego wierzchołka a
Problemy
następnie sprawdzamy czy wszystkie wierzchołki są
oznaczone jako odwiedzone.
Zastosowania algorytmu DFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problem
Problemy grafowe
Reprezentacje grafu
Czy graf jest spójny?
Przeszukiwanie
grafu
Wstęp
DFS
Rozwiązanie
BFS
Uruchamiamy algorytm DFS z dowolnego wierzchołka a
Problemy
następnie sprawdzamy czy wszystkie wierzchołki są
oznaczone jako odwiedzone.
Zastosowania algorytmu DFS
Grafy - Wpro-
wadzenie
Wstęp
Problem
Podstawowe pojęcia
Rodzaje grafów
Znalez
ć dowolną ścieżkę łączącą wierzchołki A lub B, bądz

Problemy grafowe
Reprezentacje grafu
stwierdzić, że taka nie istnieje.
Przeszukiwanie
grafu
Wstęp
Rozwiązanie
DFS
BFS
W tym celu, w trakcie działania algorytmu DFS,
Problemy
zapamiętamy dla każdego wierzchołka v numer wierzchołka
z którego wywołaliśmyDFS(v). Oznaczymy go ojc[v] i
nazwiemyojcemwierzchołka v. Skąd się wzięła ta nazwa?.
Znajdz
my ścieżkę łączącą 3 i 8 w widzianym ostatnio grafie.
Zastosowania algorytmu DFS
Grafy - Wpro-
wadzenie
Wstęp
Problem
Podstawowe pojęcia
Rodzaje grafów
Znalez
ć dowolną ścieżkę łączącą wierzchołki A lub B, bądz

Problemy grafowe
Reprezentacje grafu
stwierdzić, że taka nie istnieje.
Przeszukiwanie
grafu
Wstęp
Rozwiązanie
DFS
BFS
W tym celu, w trakcie działania algorytmu DFS,
Problemy
zapamiętamy dla każdego wierzchołka v numer wierzchołka
z którego wywołaliśmyDFS(v). Oznaczymy go ojc[v] i
nazwiemyojcemwierzchołka v. Skąd się wzięła ta nazwa?.
Znajdz
my ścieżkę łączącą 3 i 8 w widzianym ostatnio grafie.
Szukanie ścieżki
Grafy - Wpro-
DFS
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
1 7
Wstęp
DFS
BFS
Problemy
3
5 4
Tablica ojców
i 1 2 3 4 5 6 7 8
ojc[i] 7 8 4 6 4 2 4 x
Szukanie ścieżki
Grafy - Wpro-
DFS
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
1 7
Wstęp
DFS
BFS
Problemy
3
5 4
Tablica ojców
i 1 2 3 4 5 6 7 8
ojc[i] 7 8 4 6 4 2 4 x
Szukanie ścieżki
Grafy - Wpro-
DFS
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
1 7
Wstęp
DFS
BFS
Problemy
3
5 4
Tablica ojców
i 1 2 3 4 5 6 7 8
ojc[i] 7 8 4 6 4 2 4 x
Szukanie ścieżki
Grafy - Wpro-
DFS
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
1 7
Wstęp
DFS
BFS
Problemy
3
5 4
Tablica ojców
i 1 2 3 4 5 6 7 8
ojc[i] 7 8 4 6 4 2 4 x
Szukanie ścieżki
Grafy - Wpro-
DFS
wadzenie
8 2
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
6
Reprezentacje grafu
Przeszukiwanie
grafu
1 7
Wstęp
DFS
BFS
Problemy
3
5 4
Tablica ojców
i 1 2 3 4 5 6 7 8
ojc[i] 7 8 4 6 4 2 4 x
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
BFS
Rodzaje grafów
Problemy grafowe
BFS (breadth-first search), czyli przeszukiwanie
Reprezentacje grafu
Przeszukiwanie wszerz:
grafu
Wstęp
zaczynamy od dowolnego wierzchołka K
DFS
BFS
odwiedzamy wszystkich sąsiadów K
Problemy
odwiedzamy wszystkich sąsiadów sąsiadów K
odwiedzamy wszystkich sąsiadów sąsiadów sąsiadów
K . . .
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
BFS
Rodzaje grafów
Problemy grafowe
BFS (breadth-first search), czyli przeszukiwanie
Reprezentacje grafu
Przeszukiwanie wszerz:
grafu
Wstęp
zaczynamy od dowolnego wierzchołka K
DFS
BFS
odwiedzamy wszystkich sąsiadów K
Problemy
odwiedzamy wszystkich sąsiadów sąsiadów K
odwiedzamy wszystkich sąsiadów sąsiadów sąsiadów
K . . .
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
BFS
Rodzaje grafów
Problemy grafowe
BFS (breadth-first search), czyli przeszukiwanie
Reprezentacje grafu
Przeszukiwanie wszerz:
grafu
Wstęp
zaczynamy od dowolnego wierzchołka K
DFS
BFS
odwiedzamy wszystkich sąsiadów K
Problemy
odwiedzamy wszystkich sąsiadów sąsiadów K
odwiedzamy wszystkich sąsiadów sąsiadów sąsiadów
K . . .
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
BFS
Rodzaje grafów
Problemy grafowe
BFS (breadth-first search), czyli przeszukiwanie
Reprezentacje grafu
Przeszukiwanie wszerz:
grafu
Wstęp
zaczynamy od dowolnego wierzchołka K
DFS
BFS
odwiedzamy wszystkich sąsiadów K
Problemy
odwiedzamy wszystkich sąsiadów sąsiadów K
odwiedzamy wszystkich sąsiadów sąsiadów sąsiadów
K . . .
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
BFS
Rodzaje grafów
Problemy grafowe
BFS (breadth-first search), czyli przeszukiwanie
Reprezentacje grafu
Przeszukiwanie wszerz:
grafu
Wstęp
zaczynamy od dowolnego wierzchołka K
DFS
BFS
odwiedzamy wszystkich sąsiadów K
Problemy
odwiedzamy wszystkich sąsiadów sąsiadów K
odwiedzamy wszystkich sąsiadów sąsiadów sąsiadów
K . . .
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
Podstawowe pojęcia
Rodzaje grafów
8 2
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
grafu
6
Wstęp
DFS
BFS
1 7
Problemy
3
5 4
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
Kolejka
Przeszukiwanie
grafu
Przejdziemy teraz do dokładniejszego opisu algorytmu BFS.
Wstęp
DFS
Będzie on korzystał zkolejki FIFO, więc jest to dobry
BFS
Problemy moment, aby ją przypomnieć.
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Jak to zapisać na komputerze?
Problemy grafowe
Reprezentacje grafu
tworzymy pustą kolejkę
Przeszukiwanie
grafu
wrzucamy do niej dowolny wierzchołek
Wstęp
DFS
dopóki kolejka nie jest pusta
BFS
Problemy
wyciągnij wierzchołek z kolejki (oznaczmy go v)
rozpatrz każdego sąsiada v i jeśli nie był jeszcze
wrzucony do kolejki, to wrzuć go do kolejki
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Jak to zapisać na komputerze?
Problemy grafowe
Reprezentacje grafu
tworzymy pustą kolejkę
Przeszukiwanie
grafu
wrzucamy do niej dowolny wierzchołek
Wstęp
DFS
dopóki kolejka nie jest pusta
BFS
Problemy
wyciągnij wierzchołek z kolejki (oznaczmy go v)
rozpatrz każdego sąsiada v i jeśli nie był jeszcze
wrzucony do kolejki, to wrzuć go do kolejki
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Jak to zapisać na komputerze?
Problemy grafowe
Reprezentacje grafu
tworzymy pustą kolejkę
Przeszukiwanie
grafu
wrzucamy do niej dowolny wierzchołek
Wstęp
DFS
dopóki kolejka nie jest pusta
BFS
Problemy
wyciągnij wierzchołek z kolejki (oznaczmy go v)
rozpatrz każdego sąsiada v i jeśli nie był jeszcze
wrzucony do kolejki, to wrzuć go do kolejki
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Jak to zapisać na komputerze?
Problemy grafowe
Reprezentacje grafu
tworzymy pustą kolejkę
Przeszukiwanie
grafu
wrzucamy do niej dowolny wierzchołek
Wstęp
DFS
dopóki kolejka nie jest pusta
BFS
Problemy
wyciągnij wierzchołek z kolejki (oznaczmy go v)
rozpatrz każdego sąsiada v i jeśli nie był jeszcze
wrzucony do kolejki, to wrzuć go do kolejki
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Jak to zapisać na komputerze?
Problemy grafowe
Reprezentacje grafu
tworzymy pustą kolejkę
Przeszukiwanie
grafu
wrzucamy do niej dowolny wierzchołek
Wstęp
DFS
dopóki kolejka nie jest pusta
BFS
Problemy
wyciągnij wierzchołek z kolejki (oznaczmy go v)
rozpatrz każdego sąsiada v i jeśli nie był jeszcze
wrzucony do kolejki, to wrzuć go do kolejki
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
8
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
DFS
1 7
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
2 5 7
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
5 7
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
5 7 6
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
7 6
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
7 6 3 4
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
6 3 4
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
6 3 4 1
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
3 4 1
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
3 4 1
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
4 1
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
4 1
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
1
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
1 7
DFS
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
1
BFS
Grafy - Wpro-
wadzenie
Przykład
Wstęp
8 2
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
6
Przeszukiwanie
grafu
Wstęp
DFS
1 7
BFS
Problemy
3
5 4
Kolejka (przód z lewej)
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu Analiza złożoności
Przeszukiwanie
Złożoność algorytmu BFS, zarówno czasowa jak i
grafu
Wstęp
pamięciowa, jest taka sama jak algorytmu DFS, czyli
DFS
BFS
O(|V |2) dla macierzy sąsiedztwa
Problemy
O(|V | + |E|) dla list sąsiedztwa
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu Analiza złożoności
Przeszukiwanie
Złożoność algorytmu BFS, zarówno czasowa jak i
grafu
Wstęp
pamięciowa, jest taka sama jak algorytmu DFS, czyli
DFS
BFS
O(|V |2) dla macierzy sąsiedztwa
Problemy
O(|V | + |E|) dla list sąsiedztwa
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu Analiza złożoności
Przeszukiwanie
Złożoność algorytmu BFS, zarówno czasowa jak i
grafu
Wstęp
pamięciowa, jest taka sama jak algorytmu DFS, czyli
DFS
BFS
O(|V |2) dla macierzy sąsiedztwa
Problemy
O(|V | + |E|) dla list sąsiedztwa
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie Zastosowania
grafu
Wstęp
zamiast algorytmu DFS
DFS
BFS
do wyszukiwania najkrótszych ścieżek
Problemy
BFS
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie Zastosowania
grafu
Wstęp
zamiast algorytmu DFS
DFS
BFS
do wyszukiwania najkrótszych ścieżek
Problemy
Implementacja
Grafy - Wpro-
wadzenie
Wstęp
Podstawowe pojęcia
Rodzaje grafów
Problemy grafowe
Reprezentacje grafu
Przeszukiwanie
Implementacja
grafu
Wstęp
DFS
Kod algorytmu BFS znajduje się w notatkach.
BFS
Problemy
Problemy
Grafy - Wpro-
wadzenie
Wstęp
Problemy
Podstawowe pojęcia
Rodzaje grafów
oszacuj czas działania algorytmu DFS dla grafu o:
Problemy grafowe
Reprezentacje grafu
3000 wierzchołków i 1mln krawędzi
Przeszukiwanie
1mln wierzchołków i 1mln krawędzi
grafu
Wstęp
DFS
zliczanie spójnych składowych
BFS
czy graf jest acykliczny?
Problemy
czy graf jest drzewem?
liczenie odległości od A do B
liczenie średnicy grafu