OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie
Ogólne zalecenia do przesyłanych programów.
(1) Katalog z programem powinien zawierać Makefile i pliki źródłowe.
(2) Program powinien kompilować się poleceniem make.
(3) Nie używać deklaracji using namespace std;.
(4) Zalecane są testy automatyczne z assert().
Przeszukiwanie (przechodzenie) grafu to czynność polegająca na odwiedzeniu w usystematyzowany sposób wszystkich wierzchołków grafu w celu zebrania potrzebnych informacji [Wikipedia]. Często podczas przejścia grafu rozwiązujemy już jakiś problem, ale przeważnie jest to tylko wstęp do wykonania właściwego algorytmu.
Powszechnie stosuje się dwie metody przeszukiwania grafów:
przeszukiwanie wszerz (ang. breadth-first search, BFS),
przeszukiwanie w głąb (ang. depth-first search, DFS).
Są jeszcze inne sposoby odwiedzania wierzchołków grafu,
o specjalnych właściwościach, takie jak:
lexicographic breadth first search (LexBFS),
maximum cardinality search (MCS).
# Wersja pseudokodu z kolorami wierzchołków.
Input: A graph G.
Output: BFS tree (Parent), distances (Distance).
Algorithm BFS(G):
let Color[] be an empty table for vertex colors
let Parent[] be an empty table for links
let Distance[] be an empty table for distances
for each vertex u in V(G) do
set Color[u] to WHITE
set Distance[u] to infinity
set Parent[u] to None
for each vertex u in V(G) do
if Color[u] is WHITE then
call BFSVisit(G,u)
Input: A graph G and a starting vertex s of G.
Output: Shortest paths to s for all vertices (Parent), distances (Distance).
Algorithm BFSVisit(G,s):
set Color[s] to GREY
call pre_action(s) # Preorder.append(s)
set Parent[s] to None
set Distance[s] to 0
let Q be an empty queue
Q.put(s)
while Q is not empty do
set u to Q.get()
for each edge (u,v) in E(G) do # adjacency list
if Color[v] is WHITE then
set Color[v] to GREY
call pre_action(v) # Preorder.append(v)
set Parent[v] to u
set Distance[v] to Distance[u] + 1
Q.put(v)
set Color[u] to BLACK
call post_action(u) # Postorder.append(u)
# W kolejce Q są jedynie szare wierzchołki (niezmiennik pętli).
# Cormen udowadnia, że BFS wyznacza najkrótsze ścieżki do s.
# Cormen pisze, że rozróżnianie szarych i czarnych wierzchołków nie jest
# konieczne, ale pomaga w zrozumieniu BFS.
# Algorytm wypisywania najkrótszej ścieżki z s do t.
Algorithm PrintPath(G,s,t): # wersja rekurencyjna
if s equals t then
print s
else if Parent[t] is None then
print "no path"
else
call PrintPath(G,s,Parent[t])
print t # kolejność wyświetlania: s, ..., Parent[t], t
# Przykład. Wierzchołki grafu numerowane w kolejności napotkania w BFS (preorder). # 0 2(1) 5(2) drzewo BFS 0 2 5 # o---o---o o---o---o # | / | \ | | \ # 1(1)o | o6(2) 1o o6 # | \ | / | | \ # o---o---o o o---o # 3(2) 4(2) 7(3) 3 4 7
Wybór kolejności sąsiadów wierzchołka v w pętli for nie jest określony, w praktyce zależy od implementacji grafu.
Czasowa złożoność obliczeniowa BFS to O(n+m) w reprezentacji list
sąsiedztwa [Cormen].
Pamięciowa złożoność obliczeniowa BFS to O(n).
Uporządkowanie BFS to takie uporządkowanie wierzchołków grafu, że jest to możliwa kolejność odwiedzania wierzchołków algorytmem BFS.
Wybrane zastosowania BFS:
wyznaczanie najkrótszych ścieżek w grafie (w sensie przeskoków),
wyznaczanie spójnych składowych grafu nieskierowanego,
wykrywanie grafu dwudzielnego,
wyznaczanie największego przepływu w sieciach przepływowych,
generowanie labiryntu.
# Wersja Cormena z kolorowaniem wierzchołków.
Input: A graph G.
Output: DFS tree (Parent).
Algorithm DFS(G):
let Color[] be an empty table for node colors
let Parent[] be an empty table for links
for each node u in V(G) do
set Color[u] to WHITE
set Parent[u] to None
for each node u in V(G) do
if Color[u] is WHITE then
call DFSVisit(G,u)
return Parent
Algorithm DFSVisit(G,u):
set Color[u] to GREY
call pre_action(u) # Preorder.append(u)
for each edge (u,v) in E(G) do
if Color[v] is WHITE then # adjacency list
set Parent[v] to u
call DFSVisit(G,v)
set Color[u] to BLACK
call post_action(u) # Postorder.append(u)
# Cormen dla każdego wierzchołka wyznacza czas odwiedzenia (wierzchołek
# staje się GREY) i czas przetworzenia (wierzchołek staje się BLACK).
# Przykład. Wierzchołki grafu numerowane w kolejności napotkania w DFS (preorder). # 0 5 4 drzewo DFS 0 5 4 # o---o---o o o---o # | / | \ | | | # 1o | o3 1o o3 # | \ | / | \ / | # o---o---o o---o o # 7 2 6 7 2 6
Czasowa złożoność obliczeniowa DFS to O(n+m) w reprezentacji list
sąsiedztwa [Cormen].
Pamięciowa złożoność obliczeniowa DFS to O(n).
Wybrane zastosowania DFS:
wyznaczanie składowych spójnych grafu nieskierowanego,
wykrywanie grafu dwudzielnego,
sortowanie topologiczne wierzchołków grafu,
testowanie planarności grafu,
wyznaczanie mostów i punktów artykulacji grafu,
wykrywanie cykli w grafie,
wyznaczanie silnie spójnych składowych w grafie skierowanym,
generowanie labiryntu (zwykle z dodaniem przypadkowości).
Wygenerować graf przypadkowy spójny z n=10. Znaleźć kolejność odkrywania wierzchołków grafu przez BFS.
// bfs.hpp
template<typename T, typename G> // node type, graph type
class BFS {
G& graph;
std::unordered_map<T, bool> visited;
public:
std::vector<T> preorder;
std::vector<T> postorder;
BFS(G& g) : graph(g) {
for (auto n_it = graph.node_begin();
n_it != graph.node_end();
++n_it) {
visited[*n_it] = false;
}
}
~BFS() = default; // destruktor
void run(T u = T()) {
if (u != T()) { // badamy jedną składową spójną
visit(u);
} else {
for (auto n_it = graph.node_begin();
n_it != graph.node_end();
++n_it) {
if (!visited[*n_it])
visit(*n_it);
} // for
} // if
}
void visit(T s);
};
// Usage:
// auto algorithm = BFS<int,Graph>(graph); // macierz sąsiedztwa
// auto algorithm = BFS<char,Graph<char>>(graph); // lista sąsiedztwa
// algorithm.run(start_node);
// for (auto& node : algorithm.preorder) { ... }
// for (auto& node : algorithm.postorder) { ... }
Wygenerować graf przypadkowy spójny z n=10. Znaleźć kolejność odkrywania wierzchołków grafu przez DFS.
// dfs.hpp
template<typename T, typename G> // node type, graph type
class DFS {
G& graph;
std::unordered_map<T, bool> visited;
public:
std::vector<T> preorder;
std::vector<T> postorder;
DFS(G& g) : graph(g) {
for (auto n_it = graph.node_begin();
n_it != graph.node_end();
++n_it) {
visited[*n_it] = false;
}
}
~DFS() = default; // destruktor
void run(T u = T()) {
if (u != T()) { // badamy jedną składową spójną
visit(u);
} else {
for (auto n_it = graph.node_begin();
n_it != graph.node_end();
++n_it) {
if (!visited[*n_it])
visit(*n_it);
} // for
} // if
}
void visit(T u);
};
// Usage:
// auto algorithm = DFS<int,Graph>(graph); // macierz sąsiedztwa
// auto algorithm = DFS<char,Graph<char>>(graph); // lista sąsiedztwa
// algorithm.run(start_node);
// for (auto& node : algorithm.preorder) { ... }
// for (auto& node : algorithm.postorder) { ... }
Zaimplementować BFS lub DFS w taki sposób, aby oprócz kolejności napotykanych wierzchołków wyznaczać ich odległość od wierzchołka startowego.