Rozwiązania zadań 17...20 - BFS

Zadanie 17

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.

obrazek      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

 

Zadanie 18

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

 

obrazek
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

 

Zadanie 19

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:

  1. 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.

  2. Uruchamiamy BFS od wierzchołka drugiego.

  3. 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.

  4. 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.

 

obrazek
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

 

Zadanie 20

Napisz program z przejściem BFS, który tworzy od zadanego wierzchołka drzewo rozpinające BFS.

obrazek
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   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

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