Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2011 mgr
Jerzy Wałaszek
|
Napisz program z przejściem BFS, w którym graf jest reprezentowany macierzą sąsiedztwa i macierzą incydencji.
Dane do programu definiują graf - pierwsze dwie liczby to n - liczba wierzchołków oraz m - liczba krawędzi. Następnie mamy m par liczb, które określają krawędzie. Na końcu jest podany numer wierzchołka startowego, od którego rozpocznie się przejście BFS.
7 12 0 1 0 3 0 4 0 6 1 2 1 5 2 3 2 4 2 5 2 6 3 5 4 6 5 |
Code::Blocks |
// Przejście BFS // Graf nieskierowany - macierz sąsiedztwa // (C)2011 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <queue> using namespace std; int main() { int ** A; // Macierz sąsiedztwa int n,m,i,j,v1,v2; queue<int>Q; // Kolejka dla dla BFS // Odczytujemy n i m cin >> n >> m; // Tworzymy dynamicznie macierz n x n A = new int * [n]; for(i = 0; i < n; i++) { A[i] = new int [n]; for(j = 0; j < n; j++) A[i][j] = 0; } // Wczytujemy kolejne krawędzie i umieszczamy je w macierzy for(i = 0; i < m; i++) { cin >> v1 >> v2; A[v1][v2] = A[v2][v1] = 1; // krawędź v1-->v2 oraz v1<--v2 } // Tworzymy tablicę odwiedzin wierzchołków bool * visited = new bool [n]; // Zerujemy tablicę odwiedzin wierzchołków for(i = 0; i < n; i++) visited[i] = false; // Odczytujemy wierzchołek startowy cin >> v1; // Zaznaczmy go jako odwiedzonego visited[v1] = true; // i umieszczamy w kolejce Q.push(v1); // Przejście BFS cout << endl; while(!Q.empty()) // Dopóki kolejka zawiera wierzchołki { v1 = Q.front(); // Odczytujemy wierzchołek z początku kolejki Q.pop(); // Odczytany wierzchołek usuwamy z kolejki cout << v1 << " "; // Wypisujemy wierzchołek // Nieodwiedzonych sąsiadów wierzchołka oznaczamy jako odwiedzonych i umieszczamy w kolejce for(i = 0; i < n; i++) if(A[v1][i] && !visited[i]) // Jeśli istnieje krawędź v1-->vi oraz vi nie jest odwiedzony { visited[i] = true; // Odwiedzamy vi Q.push(i); // vi umieszczamy w kolejce } } cout << endl << endl; // Usuwamy tablice dynamiczne delete [] visited; for(i = 0; i < n; i++) delete [] A[i]; delete [] A; return 0; } |
7 12 0 1 0 3 0 4 0 6 1 2 1 5 2 3 2 4 2 5 2 6 3 5 4 6 5 5 1 2 3 0 4 6 |
Code::Blocks |
// Przejście BFS // Graf nieskierowany - macierz incydencji // (C)2011 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <queue> using namespace std; int main() { int ** A; // Macierz incydencji int n,m,i,j,v1,v2; queue<int>Q; // Kolejka dla dla BFS // Odczytujemy n i m cin >> n >> m; // Tworzymy dynamicznie macierz n x m A = new int * [n]; for(i = 0; i < n; i++) { A[i] = new int [m]; for(j = 0; j < m; j++) A[i][j] = 0; } // Wczytujemy kolejne krawędzie i umieszczamy je w macierzy incydencji for(i = 0; i < m; i++) { cin >> v1 >> v2; A[v1][i] = A[v2][i] = 1; // krawędź i-ta jest incydentna z v1 i v2 } // Tworzymy tablicę odwiedzin wierzchołków bool * visited = new bool [n]; // Zerujemy tablicę odwiedzin wierzchołków for(i = 0; i < n; i++) visited[i] = false; // Odczytujemy wierzchołek startowy cin >> v1; // Zaznaczmy go jako odwiedzonego visited[v1] = true; // i umieszczamy w kolejce Q.push(v1); // Przejście BFS cout << endl; while(!Q.empty()) // Dopóki kolejka zawiera wierzchołki { v1 = Q.front(); // Odczytujemy wierzchołek z początku kolejki Q.pop(); // Odczytany wierzchołek usuwamy z kolejki cout << v1 << " "; // Wypisujemy wierzchołek // Nieodwiedzonych sąsiadów wierzchołka oznaczamy jako odwiedzonych i // umieszczamy w kolejce for(i = 0; i < m; i++) // Sprawdzamy, czy i-ta krawędź jest incydentna z v1 if(A[v1][i]) // Jeśli jest, szukamy jej drugiego wierzchołka (sąsiada v1) for(j = 0; j < n; j++) if(j != v1 && A[j][i]) { if(!visited[j]) // Jeśli wierzchołek nie jest odwiedzony { visited[j] = true; // Odwiedzamy go Q.push(j); // i umieszczamy w kolejce } break; // Przerywamy pętlę wyszukującą sąsiada } } cout << endl << endl; // Usuwamy tablice dynamiczne delete [] visited; for(i = 0; i < m; i++) delete [] A[i]; delete [] A; return 0; } |
7 12 0 1 0 3 0 4 0 6 1 2 1 5 2 3 2 4 2 5 2 6 3 5 4 6 5 5 1 2 3 0 4 6 |
Napisz program z przejściem BFS nie korzystający z klasy queue - zaprojektuj odpowiednie operacje przy wykorzystaniu tablicy na kolejkę.
Kolejkę możemy utworzyć w tablicy. W algorytmie BFS potrzebne są trzy operacje:
- test, czy kolejka zawiera wierzchołki
- zapis danych do kolejki
- odczyt danych z kolejki
Oprócz tablicy tworzymy dwie dodatkowe zmienne:
pk - zawiera indeks komórki będącej początkiem kolejki
kk - zawiera indeks komórki będącej końcem kolejki
↑ pk |
↑ kk |
pk zawsze wskazuje komórkę, z której będą odczytywane dane. Po odczycie danych pk jest zwiększane o 1 i wskazuje kolejne dane. Jeśli pk wyjdzie poza ostatni element tablicy, to zostaje wyzerowane i będzie wskazywało na początek tablicy.
kk zachowuje się podobnie, tylko wskazuje wolną komórkę - czyli poza ostatni element kolejki. Zapisywaną daną umieszczamy w komórce kk i kk zwiększamy o 1. Jeśli wyjdzie poza koniec tablicy, kk zerujemy.
Kolejka jest pusta, jeśli pk i kk wskazują tę samą komórkę tablicy.
Pozostaje jeszcze pytanie o wielkość tablicy z kolejką. Aby nie doszło do nadpisania początku kolejki przez jej koniec, tablica powinna zawierać tyle komórek, ile jest wierzchołków w grafie - czyli n. Ponieważ każdy wierzchołek jest umieszczany w kolejce tylko jeden raz, indeksy pk oraz kk nigdy się nie przewiną na początek tak dużej tablicy. Dzięki temu operacje zapisu i odczytu będzie można uprościć - nie musimy sprawdzać, czy indeksy te wyszły poza ostatni element tablicy.
Dane wejściowe są zdefiniowane identycznie jak w poprzednim zadaniu - graf, na końcu numer wierzchołka startowego
Graf nr 8 |
14 22 0 1 0 2 0 3 0 4 1 2 1 10 2 5 3 4 3 5 4 6 4 7 5 6 5 8 5 9 6 7 7 9 8 10 8 11 9 12 9 13 11 12 12 13 5 |
Code::Blocks |
// Przejście BFS // Graf nieskierowany - kolejka w tablicy // (C)2011 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <list> using namespace std; int main() { int n,m,i,v1,v2; // Odczytujemy n i m cin >> n >> m; // Tworzymy dynamicznie tablicę list sąsiedztwa list<int> * A = new list<int> [n]; // Wczytujemy kolejne krawędzie i umieszczamy je na listach sąsiedztwa for(i = 0; i < m; i++) { cin >> v1 >> v2; A[v1].push_back(v2); A[v2].push_back(v1); } // Tworzymy tablicę odwiedzin wierzchołków bool * visited = new bool [n]; // Zerujemy tablicę odwiedzin wierzchołków for(i = 0; i < n; i++) visited[i] = false; // Tworzymy tablicę dla kolejki int * Q = new int [n]; // Tworzymy indeksy int pk = 0; int kk = 0; // Odczytujemy wierzchołek startowy cin >> v1; // Zaznaczmy go jako odwiedzonego visited[v1] = true; // i umieszczamy w kolejce Q[kk++] = v1; // Przejście BFS cout << endl; while(pk != kk) // Dopóki kolejka zawiera wierzchołki { v1 = Q[pk++]; // Odczytujemy wierzchołek z początku kolejki cout << v1 << " "; // Wypisujemy wierzchołek // Nieodwiedzonych sąsiadów wierzchołka oznaczamy jako odwiedzonych i umieszczamy w kolejce for(list<int>::iterator it = A[v1].begin(); it != A[v1].end(); it++) if(!visited[*it]) { visited[*it] = true; Q[kk++] = * it; } } cout << endl << endl; // Usuwamy tablice dynamiczne delete [] visited; delete [] A; delete [] Q; return 0; } |
14 22 0 1 0 2 0 3 0 4 1 2 1 10 2 5 3 4 3 5 4 6 4 7 5 6 5 8 5 9 6 7 7 9 8 10 8 11 9 12 9 13 11 12 12 13 5 5 2 3 6 8 9 0 1 4 7 10 11 12 13 |
Napisz program z przejściem BFS, który wyszukuje najkrótszą ścieżkę pomiędzy zadanymi dwoma wierzchołkami grafu.
Postępujemy następująco:
Tworzymy tablicę poprzedników (jest to taki odpowiednik drzewa rozpinającego). Tablica ta zawiera n komórek, gdzie n oznacza liczbę wierzchołków w grafie. I-ty element tej tablicy będzie zawierał informację, z którego wierzchołka grafu BFS przyszło do wierzchołka i-tego. Tablicę tę tworzymy na bieżąco przeglądając sąsiadów wierzchołka i umieszczając je w kolejce.
Uruchamiamy BFS od wierzchołka drugiego.
W trakcie działania BFS w tablicy poprzedników umieszcza informację, z którego wierzchołka następuje przejście do sąsiadów. BFS przerywa przeszukiwanie grafu po dojściu do wierzchołka pierwszego ścieżki lub po przeglądnięciu całego grafu - w tym drugim przypadku ścieżka nie istnieje.
Gdy BFS dojdzie do wierzchołka 1, to wykorzystując tablicę poprzedników, cofa się do wierzchołka 2, wypisując mijane po drodze wierzchołki - to będzie nasza najkrótsza ścieżka.
Program ten jest dokładnym odpowiednikiem programu demonstrującego wyszukiwanie najkrótszej drogi w labiryncie - tutaj zamiast labiryntu mamy graf (tak naprawdę labirynt też jest grafem). Dane dla programu składają się z definicji grafu oraz dwóch liczb określających kolejno wierzchołek 1 i wierzchołek 2 poszukiwanej ścieżki.
Graf nr 8 |
14 22 0 1 0 2 0 3 0 4 1 2 1 10 2 5 3 4 3 5 4 6 4 7 5 6 5 8 5 9 6 7 7 9 8 10 8 11 9 12 9 13 11 12 12 13 13 4 |
Code::Blocks |
// Wyszukiwanie najkrótszej ścieżki // Graf nieskierowany // (C)2011 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <list> #include <queue> using namespace std; int main() { int n,m,i,v1,v2,v; queue<int> Q; // Kolejka // Odczytujemy n i m cin >> n >> m; // Tworzymy dynamicznie tablicę list sąsiedztwa list<int> * A = new list<int> [n]; // Wczytujemy kolejne krawędzie i umieszczamy je na listach sąsiedztwa for(i = 0; i < m; i++) { cin >> v1 >> v2; A[v1].push_back(v2); A[v2].push_back(v1); } // Tworzymy tablicę odwiedzin wierzchołków bool * visited = new bool [n]; // Zerujemy tablicę odwiedzin wierzchołków for(i = 0; i < n; i++) visited[i] = false; // Tworzymy tablicę poprzedników int * P = new int [n]; // Odczytujemy wierzchołek startowy i końcowy ścieżki cin >> v1 >> v2; // Przeglądanie BFS rozpoczynamy od v2 visited[v2] = true; // Oznaczamy go jako odwiedzony Q.push(v2); // i umieszczamy w kolejce while(!Q.empty()) // Dopóki kolejka nie jest pusta { v = Q.front(); // Odczytujemy z kolejki wierzchołek Q.pop(); // Usuwamy go z kolejki if(v == v1) break; // Przerywamy, gdy doszliśmy do wierzchołka v1 // Przeglądamy jego sąsiadów. for(list<int>::iterator it = A[v].begin(); it != A[v].end(); it++) if(!visited[*it]) // Jeśli sąsiad nie jest odwiedzony { visited[*it] = true; // Odwiedzamy go P[*it] = v; // Odnotowujemy, skąd przyszliśmy Q.push(*it); // Umieszczamy go w kolejce } } cout << endl; if(v == v1) // Jeśli ścieżka została znaleziona, wypisujemy ją while(true) { cout << v << " "; // Wypisujemy wierzchołek if(v == v2) break; // Przerywamy pętlę, gdy osiągniemy ostatni wierzchołek v = P[v]; // Przechodzimy do kolejnego wierzchołka ścieżki } cout << endl << endl; // Usuwamy tablice dynamiczne delete [] visited; delete [] A; delete [] P; return 0; } |
14 22 0 1 0 2 0 3 0 4 1 2 1 10 2 5 3 4 3 5 4 6 4 7 5 6 5 8 5 9 6 7 7 9 8 10 8 11 9 12 9 13 11 12 12 13 13 9 7 4 |
Napisz program z przejściem BFS, który tworzy od zadanego wierzchołka drzewo rozpinające BFS.
Graf nr 8 |
14 22 0 1 0 2 0 3 0 4 1 2 1 10 2 5 3 4 3 5 4 6 4 7 5 6 5 8 5 9 6 7 7 9 8 10 8 11 9 12 9 13 11 12 12 13 13 |
Code::Blocks |
// Drzewo rozpinające BFS // Graf nieskierowany // (C)2011 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <list> #include <queue> using namespace std; int main() { int n,m,i,v1,v2; queue<int> Q; // Kolejka // Odczytujemy n i m cin >> n >> m; // Tworzymy dynamicznie tablicę list sąsiedztwa list<int> * A = new list<int> [n]; // Wczytujemy kolejne krawędzie i umieszczamy je na listach sąsiedztwa for(i = 0; i < m; i++) { cin >> v1 >> v2; A[v1].push_back(v2); A[v2].push_back(v1); } // Tworzymy tablicę odwiedzin wierzchołków bool * visited = new bool [n]; // Zerujemy tablicę odwiedzin wierzchołków for(i = 0; i < n; i++) visited[i] = false; // Tworzymy tablicę list sąsiedztwa dla drzewa rozpinającego list<int> * T = new list<int> [n]; // Odczytujemy wierzchołek startowy cin >> v1; // Przeglądanie BFS rozpoczynamy od v1 visited[v1] = true; // Oznaczamy go jako odwiedzony Q.push(v1); // i umieszczamy w kolejce while(!Q.empty()) // Dopóki kolejka nie jest pusta { v1 = Q.front(); // Odczytujemy z kolejki wierzchołek Q.pop(); // Usuwamy go z kolejki // Przeglądamy jego sąsiadów. for(list<int>::iterator it = A[v1].begin(); it != A[v1].end(); it++) if(!visited[*it]) // Jeśli sąsiad nie jest odwiedzony { visited[*it] = true; // Odwiedzamy go T[v1].push_back(*it); // Dopisujemy sąsiada do listy v w drzewie rozpinającym Q.push(*it); // Umieszczamy go w kolejce } } // Wypisujemy zawartość tablicy list sąsiedztwa dla drzewa rozpinającego for(i = 0; i < n; i++) { cout << endl << i << " : "; for(list<int>::iterator it = T[i].begin(); it != T[i].end(); it++) cout << *it << " "; } cout << endl << endl; // Usuwamy tablice dynamiczne delete [] visited; delete [] A; delete [] T; return 0; } |
14 22 0 1 0 2 0 3 0 4 1 2 1 10 2 5 3 4 3 5 4 6 4 7 5 6 5 8 5 9 6 7 7 9 8 10 8 11 9 12 9 13 11 12 12 13 13 0 : 1 : 2 : 0 1 3 : 4 : 5 : 2 3 6 8 6 : 7 : 4 8 : 10 9 : 5 7 10 : 11 : 12 : 11 13 : 9 12 |
I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe