Sprawdź się

Pokaż ćwiczenia:

RiyxSj6inAx6v1

Ćwiczenie 1

Ron08TgphNbVl1

Ćwiczenie 2

Ile spójnych składowych może mieć graf nieskierowany bez pętli i krwędzi wielokrotnych o 6 wierzchołkach i następującym ciągu stopni wierzchołków.

2, 2, 2, 2, 2, 2 Możliwe odpowiedzi: 1. 1, 2. 2, 3. 3, 4. 6

RU7kkL4oFSKxa2

Ćwiczenie 3

Ćwiczenie 4

RobNyF0oGKt0S11

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Ćwiczenie 5

Napisz program, który obliczy liczbę spójnych składowych grafu nieskierowanego, a następnie ją wyświetli.

Specyfikacja problemu:

Dane:

n – stała przechowująca liczbę wierzchołków grafu; liczba naturalna
macierzSasiedztwa – macierz sąsiedztwa grafu; tablica dwuwymiarowa liczb naturalnych

Wynik:

liczba spójnych składowych grafu; liczba naturalna

Działanie programu przetestuj dla następujących danych:

Graf:

RHBbzJCeoL0tO

Macierz sąsiedztwa tego grafu:

int macierzSasiedztwa[n][n] = {
    { 0, 0, 0, 0, 0, 0 },
    { 0, 0, 1, 0, 1, 0 },
    { 0, 1, 0, 1, 0, 0 },
    { 0, 0, 1, 0, 1, 0 },
    { 0, 1, 0, 1, 0, 0 },
	{ 0, 0, 0, 0, 0, 0 }
};

Przykładowy wynik dla podanych danych:

Liczba spojnych skladowych grafu: 3

R1aarL5g7wLJZ

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. using namespace std średnik. Linia 4. const int n znak równości 6 średnik. Linia 6. void przeszukaj otwórz nawias okrągły int v przecinek bool odwiedzone otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int macierzSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości true średnik. Linia 8. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. if otwórz nawias okrągły macierzSasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości 1 ampersant ampersant wykrzyknik odwiedzone otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. przeszukaj otwórz nawias okrągły i przecinek odwiedzone przecinek macierzSasiedztwa zamknij nawias okrągły średnik. Linia 11. zamknij nawias klamrowy. Linia 12. zamknij nawias klamrowy. Linia 13. zamknij nawias klamrowy. Linia 15. int liczbaSkladowych otwórz nawias okrągły int macierzSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. bool odwiedzone otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy false zamknij nawias klamrowy średnik. Linia 17. int licznikSkladowych znak równości 0 średnik. Linia 19. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. if otwórz nawias okrągły wykrzyknik odwiedzone otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. przeszukaj otwórz nawias okrągły i przecinek odwiedzone przecinek macierzSasiedztwa zamknij nawias okrągły średnik. Linia 22. licznikSkladowych plus plus średnik. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy. Linia 26. return licznikSkladowych średnik. Linia 27. zamknij nawias klamrowy. Linia 29. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 30. int macierzSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 31. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 32. otwórz nawias klamrowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias klamrowy przecinek. Linia 33. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 34. otwórz nawias klamrowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias klamrowy przecinek. Linia 35. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 36. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy. Linia 37. zamknij nawias klamrowy średnik. Linia 39. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Liczba spojnych skladowych grafu dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny liczbaSkladowych otwórz nawias okrągły macierzSasiedztwa zamknij nawias okrągły otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 41. return 0 średnik. Linia 42. zamknij nawias klamrowy.

#include <iostream>
using namespace std;

const int n = 6;

void przeszukaj(int v, bool odwiedzone[], int macierzSasiedztwa[n][n]) {
    odwiedzone[v] = true;
    for (int i = 0; i < n; ++i) {
        if (macierzSasiedztwa[v][i] == 1 && !odwiedzone[i]) {
            przeszukaj(i, odwiedzone, macierzSasiedztwa);
        }
    }
}

int liczbaSkladowych(int macierzSasiedztwa[n][n]) {
    bool odwiedzone[n] = {false};
    int licznikSkladowych = 0;

    for (int i = 0; i < n; ++i) {
        if (!odwiedzone[i]) {
            przeszukaj(i, odwiedzone, macierzSasiedztwa);
            licznikSkladowych++;
        }
    }

    return licznikSkladowych;
}

int main() {
    int macierzSasiedztwa[n][n] = {
        { 0, 0, 0, 0, 0, 0 },
        { 0, 0, 1, 0, 1, 0 },
        { 0, 1, 0, 1, 0, 0 },
        { 0, 0, 1, 0, 1, 0 },
        { 0, 1, 0, 1, 0, 0 },
        { 0, 0, 0, 0, 0, 0 }
    };

    cout << "Liczba spojnych skladowych grafu: " << liczbaSkladowych(macierzSasiedztwa) << endl;
    
    return 0;
}

Ćwiczenie 6

Napisz program, który sprawdzi, czy dana para wierzchołków o indeksach v oraz w tworzących krawędź vw grafu spójnego nieskierowanego reprezentowanego przez macierz sąsiedztwa jest mostem.

Specyfikacja problemu:

Dane:

n – stała przechowująca liczbę wierzchołków grafu; liczba naturalna
macierzSasiedztwa – macierz sąsiedztwa grafu; tablica dwuwymiarowa liczb naturalnych
v – indeks wierzchołka tworzącego krawędź; liczba naturalna
w – indeks wierzchołka tworzącego krawędź; liczba naturalna

Wynik:

komunikat mówiący o tym, czy krawędź tworzona przez dwa podane wierzchołki vw jest mostem

Działanie programu przetestuj dla następujących danych:

Graf:

RiOppoLhKXNb6

Macierz sąsiedztwa grafu:

int macierzSasiedztwa[n][n] = {
    { 0, 1, 0, 1, 0, 0, 0, 1 },
    { 1, 0, 1, 1, 0, 0, 0, 0 },
    { 0, 1, 0, 0, 1, 0, 0, 0 },
    { 1, 1, 0, 0, 1, 0, 0, 0 },
    { 0, 0, 1, 1, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 1, 0 },
    { 0, 0, 0, 0, 0, 1, 0, 1 },
    { 1, 0, 0, 0, 0, 0, 1, 0 }
};

int v = 0, w = 7;

Przykładowy wynik dla podanych danych:

Krawedz 0-7 jest mostem

RqHzJ19TfRQsH

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. using namespace std średnik. Linia 4. const int n znak równości 8 średnik. Linia 8. void przeszukaj otwórz nawias okrągły int v przecinek bool odwiedzone otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int macierzSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości true średnik. Linia 10. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. if otwórz nawias okrągły macierzSasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości 1 ampersant ampersant wykrzyknik odwiedzone otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. przeszukaj otwórz nawias okrągły i przecinek odwiedzone przecinek macierzSasiedztwa zamknij nawias okrągły średnik. Linia 13. zamknij nawias klamrowy. Linia 14. zamknij nawias klamrowy. Linia 15. zamknij nawias klamrowy. Linia 17. int liczbaSkladowych otwórz nawias okrągły int macierzSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. bool odwiedzone otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy false zamknij nawias klamrowy średnik. Linia 19. int licznikSkladowych znak równości 0 średnik. Linia 21. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik plus plus i zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. if otwórz nawias okrągły wykrzyknik odwiedzone otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. przeszukaj otwórz nawias okrągły i przecinek odwiedzone przecinek macierzSasiedztwa zamknij nawias okrągły średnik. Linia 24. licznikSkladowych plus plus średnik. Linia 25. zamknij nawias klamrowy. Linia 26. zamknij nawias klamrowy. Linia 28. return licznikSkladowych średnik. Linia 29. zamknij nawias klamrowy. Linia 31. bool czyMost otwórz nawias okrągły int v przecinek int w przecinek int macierzSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 32. macierzSasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy w zamknij nawias kwadratowy znak równości 0 średnik. Linia 33. macierzSasiedztwa otwórz nawias kwadratowy w zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości 0 średnik. Linia 34. int nowaLiczba znak równości liczbaSkladowych otwórz nawias okrągły macierzSasiedztwa zamknij nawias okrągły średnik. Linia 35. macierzSasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy w zamknij nawias kwadratowy znak równości 1 średnik. Linia 36. macierzSasiedztwa otwórz nawias kwadratowy w zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości 1 średnik. Linia 37. int liczba znak równości liczbaSkladowych otwórz nawias okrągły macierzSasiedztwa zamknij nawias okrągły średnik. Linia 39. return liczba wykrzyknik znak równości nowaLiczba średnik. Linia 40. zamknij nawias klamrowy. Linia 42. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 44. int macierzSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 45. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 1 zamknij nawias klamrowy przecinek. Linia 46. otwórz nawias klamrowy 1 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 47. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 48. otwórz nawias klamrowy 1 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 49. otwórz nawias klamrowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 50. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 zamknij nawias klamrowy przecinek. Linia 51. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias klamrowy przecinek. Linia 52. otwórz nawias klamrowy 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 zamknij nawias klamrowy. Linia 53. zamknij nawias klamrowy średnik. Linia 55. int v znak równości 0 średnik. Linia 56. int w znak równości 7 średnik. Linia 57. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Krawedz cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny v otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów minus cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny w otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 58. if otwórz nawias okrągły czyMost otwórz nawias okrągły v przecinek w przecinek macierzSasiedztwa zamknij nawias okrągły zamknij nawias okrągły. Linia 59. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów jest mostem cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 60. else. Linia 61. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów nie jest mostem cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 63. return 0 średnik. Linia 64. zamknij nawias klamrowy.

#include <iostream>
using namespace std;

const int n = 8;



void przeszukaj(int v, bool odwiedzone[], int macierzSasiedztwa[n][n]) {
    odwiedzone[v] = true;
    for (int i = 0; i < n; ++i) {
        if (macierzSasiedztwa[v][i] == 1 && !odwiedzone[i]) {
            przeszukaj(i, odwiedzone, macierzSasiedztwa);
        }
    }
}

int liczbaSkladowych(int macierzSasiedztwa[n][n]) {
    bool odwiedzone[n] = {false};
    int licznikSkladowych = 0;

    for (int i = 0; i < n; ++i) {
        if (!odwiedzone[i]) {
            przeszukaj(i, odwiedzone, macierzSasiedztwa);
            licznikSkladowych++;
        }
    }

    return licznikSkladowych;
}

bool czyMost(int v, int w, int macierzSasiedztwa[n][n]) {
    macierzSasiedztwa[v][w] = 0;
    macierzSasiedztwa[w][v] = 0;
    int nowaLiczba = liczbaSkladowych(macierzSasiedztwa);
    macierzSasiedztwa[v][w] = 1;
    macierzSasiedztwa[w][v] = 1;
    int liczba = liczbaSkladowych(macierzSasiedztwa);

    return liczba != nowaLiczba;
}

int main() {
    
    int macierzSasiedztwa[n][n] = {
        { 0, 1, 0, 1, 0, 0, 0, 1 },
        { 1, 0, 1, 1, 0, 0, 0, 0 },
        { 0, 1, 0, 0, 1, 0, 0, 0 },
        { 1, 1, 0, 0, 1, 0, 0, 0 },
        { 0, 0, 1, 1, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 1, 0 },
        { 0, 0, 0, 0, 0, 1, 0, 1 },
        { 1, 0, 0, 0, 0, 0, 1, 0 }
    };

    int v = 0;
    int w = 7;
    cout << "Krawedz " << v << "-" << w << " ";
    if (czyMost(v, w, macierzSasiedztwa))
        cout << "jest mostem" << endl;
    else
        cout << "nie jest mostem" << endl;

    return 0;
}

Dla zainteresowanych

Ćwiczenie 7

Napisz program, który sprawdzi, czy dla danego digrafu reprezentowanego przez macierz sąsiedztwa możliwe jest dojście z wierzchołka startowego (o indeksie startowy) do wierzchołka końcowego (o indeksie koncowy).

Specyfikacja problemu:

Dane:

n – stała przechowująca liczbę wierzchołków grafu; liczba naturalna
macierzSasiedztwa – macierz sąsiedztwa grafu; tablica dwuwymiarowa liczb naturalnych
startowy – indeks wierzchołka; liczba naturalna
koncowy – indeks wierzchołka; liczba naturalna

Wynik:

komunikat mówiący o tym, czy możliwe jest dojście z wierzchołka startowy do wierzchołka koncowy

Działanie programu przetestuj dla następujących danych:

Graf:

R1ACJIqAG7ZTa

Macierz sąsiedztwa grafu:

int macierzSasiedztwa[n][n] = {
	{ 0, 0, 1, 1, 0 },
    { 1, 0, 1, 1, 1 },
    { 0, 1, 0, 1, 1 },
    { 1, 0, 0, 0, 1 },
    { 1, 0, 0, 0, 0 }
};

int startowy = 0;
int koncowy = 4;

Przykładowy wynik dla podanych danych:

Wierzcholek 4 jest osiagalny z wierzcholka 0

R1eVyGnEDvV55

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. using namespace std średnik. Linia 4. const int n znak równości 5 średnik. Linia 6. bool przeszukaj otwórz nawias okrągły int v przecinek bool odwiedzone otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int macierzSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy przecinek int docelowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości true średnik. Linia 8. if otwórz nawias okrągły v znak równości znak równości docelowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. return true średnik. Linia 10. zamknij nawias klamrowy. Linia 12. for otwórz nawias okrągły int w znak równości 0 średnik w otwórz nawias ostrokątny n średnik w plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. if otwórz nawias okrągły macierzSasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy w zamknij nawias kwadratowy znak równości znak równości 1 ampersant ampersant wykrzyknik odwiedzone otwórz nawias kwadratowy w zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. if otwórz nawias okrągły przeszukaj otwórz nawias okrągły w przecinek odwiedzone przecinek macierzSasiedztwa przecinek docelowy zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. return true średnik. Linia 16. zamknij nawias klamrowy. Linia 17. zamknij nawias klamrowy. Linia 18. zamknij nawias klamrowy. Linia 20. return false średnik. Linia 21. zamknij nawias klamrowy. Linia 23. bool czyOsiagalny otwórz nawias okrągły int macierzSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy przecinek int startowy przecinek int koncowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. bool odwiedzone otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy false zamknij nawias klamrowy średnik. Linia 25. return przeszukaj otwórz nawias okrągły startowy przecinek odwiedzone przecinek macierzSasiedztwa przecinek koncowy zamknij nawias okrągły średnik. Linia 26. zamknij nawias klamrowy. Linia 28. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. int macierzSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 30. otwórz nawias klamrowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 zamknij nawias klamrowy przecinek. Linia 31. otwórz nawias klamrowy 1 przecinek 0 przecinek 1 przecinek 1 przecinek 1 zamknij nawias klamrowy przecinek. Linia 32. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 zamknij nawias klamrowy przecinek. Linia 33. otwórz nawias klamrowy 1 przecinek 0 przecinek 0 przecinek 0 przecinek 1 zamknij nawias klamrowy przecinek. Linia 34. otwórz nawias klamrowy 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy. Linia 35. zamknij nawias klamrowy średnik. Linia 37. int startowy znak równości 0 średnik. Linia 38. int koncowy znak równości 4 średnik. Linia 40. if otwórz nawias okrągły czyOsiagalny otwórz nawias okrągły macierzSasiedztwa przecinek startowy przecinek koncowy zamknij nawias okrągły zamknij nawias okrągły. Linia 41. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Wierzcholek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny koncowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów jest osiagalny z wierzcholka cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny startowy otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 42. else. Linia 43. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Wierzcholek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny koncowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów nie jest osiagalny z wierzcholka cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny startowy otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 45. return 0 średnik. Linia 46. zamknij nawias klamrowy.

#include <iostream>
using namespace std;

const int n = 5;

bool przeszukaj(int v, bool odwiedzone[], int macierzSasiedztwa[n][n], int docelowy) {
    odwiedzone[v] = true;
    if (v == docelowy) {
        return true;
    }

    for (int w = 0; w < n; w++) {
        if (macierzSasiedztwa[v][w] == 1 && !odwiedzone[w]) {
            if (przeszukaj(w, odwiedzone, macierzSasiedztwa, docelowy)) {
                return true;
            }
        }
    }

    return false;
}

bool czyOsiagalny(int macierzSasiedztwa[n][n], int startowy, int koncowy) {
    bool odwiedzone[n] = {false};
    return przeszukaj(startowy, odwiedzone, macierzSasiedztwa, koncowy);
}

int main() {
    int macierzSasiedztwa[n][n] = {
        { 0, 0, 1, 1, 0 },
        { 1, 0, 1, 1, 1 },
        { 0, 1, 0, 1, 1 },
        { 1, 0, 0, 0, 1 },
        { 1, 0, 0, 0, 0 }
    };

    int startowy = 0;
    int koncowy = 4;

    if (czyOsiagalny(macierzSasiedztwa, startowy, koncowy))
        cout << "Wierzcholek " << koncowy << " jest osiagalny z wierzcholka " << startowy << endl;
    else
        cout << "Wierzcholek " << koncowy << " nie jest osiagalny z wierzcholka " << startowy << endl;

    return 0;
}

Prezentacja multimedialna

Dla nauczyciela