Sprawdź się

Pokaż ćwiczenia:

R6JerVA73gEcT1

Ćwiczenie 1

Ćwiczenie 2

Napisz program, który sprawdzi, czy podane dla przedstawionego grafu ścieżki są ścieżkami Hamiltona.

Specyfikacja problemu:

Dane:

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

Wynik:

komunikat informujący o tym, czy podane dla przedstawionego grafu ścieżki są ścieżkami Hamiltona

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

Graf:

RiOppoLhKXNb6

Macierz sąsiedztwa przedstawionego grafu oraz sprawdzane ścieżki:

Linia 1. const int n znak równości 8 średnik. Linia 3. 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 4. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 1 zamknij nawias klamrowy przecinek. Linia 5. otwórz nawias klamrowy 1 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 6. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 7. otwórz nawias klamrowy 1 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 8. otwórz nawias klamrowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 9. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 zamknij nawias klamrowy przecinek. Linia 10. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias klamrowy przecinek. Linia 11. otwórz nawias klamrowy 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 zamknij nawias klamrowy. Linia 12. zamknij nawias klamrowy średnik. Linia 15. int sciezki otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 16. otwórz nawias klamrowy 0 przecinek 1 przecinek 2 przecinek 3 przecinek 4 przecinek 5 przecinek 6 przecinek 7 zamknij nawias klamrowy przecinek. Linia 17. otwórz nawias klamrowy 1 przecinek 2 przecinek 4 przecinek 3 przecinek 0 przecinek 7 przecinek 6 przecinek 5 zamknij nawias klamrowy przecinek. Linia 18. otwórz nawias klamrowy 5 przecinek 3 przecinek 2 przecinek 3 przecinek 4 przecinek 5 przecinek 0 przecinek 0 zamknij nawias klamrowy. Linia 19. zamknij nawias klamrowy średnik.

const int n = 8;

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 sciezki[][n] = {
  {0, 1, 2, 3, 4, 5, 6, 7},
  {1, 2, 4, 3, 0, 7, 6, 5},
  {5, 3, 2, 3, 4, 5, 0, 0}
};

Przykładowy wynik dla podanych danych:

Ciag wierzcholkow ( 0 1 2 3 4 5 6 7 ) nie jest sciezka Hamiltona
Ciag wierzcholkow ( 1 2 4 3 0 7 6 5 ) jest sciezka Hamiltona
Ciag wierzcholkow ( 5 3 2 3 4 5 0 0 ) nie jest sciezka Hamiltona

Rd6mluWkTb71i

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. const int n znak równości 8 średnik. Linia 7. 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 8. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 1 zamknij nawias klamrowy przecinek. Linia 9. otwórz nawias klamrowy 1 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 10. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 11. otwórz nawias klamrowy 1 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 12. otwórz nawias klamrowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 13. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 zamknij nawias klamrowy przecinek. Linia 14. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias klamrowy przecinek. Linia 15. otwórz nawias klamrowy 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 zamknij nawias klamrowy. Linia 16. zamknij nawias klamrowy średnik. Linia 19. bool odwiedzone otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 21. bool czySciezkaHamiltona otwórz nawias okrągły int sciezka otwórz nawias kwadratowy n zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły odwiedzone otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości false średnik. Linia 23. odwiedzone otwórz nawias kwadratowy sciezka otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias kwadratowy znak równości true średnik. Linia 25. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. int v znak równości sciezka otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek w znak równości sciezka otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy średnik. Linia 28. 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 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. return false średnik. Linia 30. zamknij nawias klamrowy. Linia 32. if otwórz nawias okrągły odwiedzone otwórz nawias kwadratowy w zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 33. return false średnik. Linia 34. zamknij nawias klamrowy. Linia 36. odwiedzone otwórz nawias kwadratowy w zamknij nawias kwadratowy znak równości true średnik. Linia 37. zamknij nawias klamrowy. Linia 39. return true ś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 43. int sciezki otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 44. otwórz nawias klamrowy 0 przecinek 1 przecinek 2 przecinek 3 przecinek 4 przecinek 5 przecinek 6 przecinek 7 zamknij nawias klamrowy przecinek. Linia 45. otwórz nawias klamrowy 1 przecinek 2 przecinek 4 przecinek 3 przecinek 0 przecinek 7 przecinek 6 przecinek 5 zamknij nawias klamrowy przecinek. Linia 46. otwórz nawias klamrowy 5 przecinek 3 przecinek 2 przecinek 3 przecinek 4 przecinek 5 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 47. zamknij nawias klamrowy średnik. Linia 49. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny sizeof otwórz nawias okrągły sciezki zamknij nawias okrągły prawy ukośnik sizeof otwórz nawias okrągły sciezki otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 50. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Ciag wierzcholkow otwórz nawias okrągły cudzysłów średnik. Linia 51. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny n średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 52. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny sciezki otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 53. zamknij nawias klamrowy. Linia 55. if otwórz nawias okrągły czySciezkaHamiltona otwórz nawias okrągły sciezki otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 56. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów zamknij nawias okrągły jest sciezka Hamiltona cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 57. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 58. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów zamknij nawias okrągły nie jest sciezka Hamiltona cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 59. zamknij nawias klamrowy. Linia 60. zamknij nawias klamrowy. Linia 62. return 0 średnik. Linia 63. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

const int n = 8;

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 }
};


bool odwiedzone[n];

bool czySciezkaHamiltona(int sciezka[n]) {
    for (int i = 0; i < n; i++) odwiedzone[i] = false;
    odwiedzone[sciezka[0]] = true;

    for (int i = 0; i < n - 1; i++) {
        int v = sciezka[i], w = sciezka[i + 1];

        if (macierzSasiedztwa[v][w] == 0) {
            return false; 
        }

        if (odwiedzone[w]) {
            return false;
        }

        odwiedzone[w] = true;
    }

    return true;
}

int main() {
    int sciezki[][n] = {
        {0, 1, 2, 3, 4, 5, 6, 7},
        {1, 2, 4, 3, 0, 7, 6, 5},
        {5, 3, 2, 3, 4, 5, 0, 0},
    };

    for (int i = 0; i < sizeof(sciezki) / sizeof(sciezki[0]); i++) {
        cout << "Ciag wierzcholkow (";
        for (int j = 0; j < n; j++) {
            cout << " " << sciezki[i][j];
        }

        if (czySciezkaHamiltona(sciezki[i])) {
            cout << " ) jest sciezka Hamiltona" << endl;
        } else {
            cout << " ) nie jest sciezka Hamiltona" << endl;
        }
    }

    return 0;
}

Ćwiczenie 3

Napisz program, który dla danego grafu reprezentowanego przez macierz sąsiedztwa sprawdzi, czy jest on grafem eulerowskim, a jeśli tak, wypisze odnaleziony cykl Eulera (indeksy kolejnych odwiedzonych wierzchołków). Przeszukiwanie zacznij od wierzchołka o indeksie 0.

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:

komunikat informujący o tym, czy graf jest grafem eulerowskim
kolejne wierzchołki cyklu Eulera, jeśli graf jest grafem eulerowskim

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

Graf:

R1Zl9QHAiYvPt

Macierz sąsiedztwa grafu:

const int n = 6;

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

Przykładowy wynik dla podanych danych:

Graf zawiera cykl Eulera.
Cykl Eulera: 0 5 3 4 2 5 1 4 0 3 2 1 0

RGGbcwNXSewLz

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 usunKrawedz 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 u przecinek int v zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. macierzSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości 0 średnik. Linia 8. macierzSasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy u zamknij nawias kwadratowy znak równości 0 średnik. Linia 9. zamknij nawias klamrowy. Linia 11. void znajdzCyklEulera 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 u zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. for otwórz nawias okrągły int v znak równości 0 średnik v otwórz nawias ostrokątny n średnik v 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 u zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. usunKrawedz otwórz nawias okrągły macierzSasiedztwa przecinek u przecinek v zamknij nawias okrągły średnik. Linia 15. znajdzCyklEulera otwórz nawias okrągły macierzSasiedztwa przecinek v zamknij nawias okrągły średnik. Linia 16. zamknij nawias klamrowy. Linia 17. zamknij nawias klamrowy. Linia 18. cout otwórz nawias ostrokątny otwórz nawias ostrokątny u otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 19. zamknij nawias klamrowy. Linia 21. bool istnienieCykluEulera 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 22. int stopnieWierzcholkow otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 0 zamknij nawias klamrowy średnik. Linia 23. int liczbaNieparzystych znak równości 0 średnik. Linia 25. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny n średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 27. stopnieWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy plus znak równości macierzSasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 28. zamknij nawias klamrowy. Linia 30. if otwórz nawias okrągły stopnieWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy procent 2 wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. liczbaNieparzystych plus plus średnik. Linia 32. zamknij nawias klamrowy. Linia 33. zamknij nawias klamrowy. Linia 35. return liczbaNieparzystych znak równości znak równości 0 ampersant ampersant n zamknij nawias ostrokątny 0 średnik. Linia 36. zamknij nawias klamrowy. Linia 38. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 39. 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 40. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 przecinek 1 zamknij nawias klamrowy przecinek. Linia 41. otwórz nawias klamrowy 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 zamknij nawias klamrowy przecinek. Linia 42. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 przecinek 1 zamknij nawias klamrowy przecinek. Linia 43. otwórz nawias klamrowy 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 zamknij nawias klamrowy przecinek. Linia 44. otwórz nawias klamrowy 1 przecinek 1 przecinek 1 przecinek 1 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 45. otwórz nawias klamrowy 1 przecinek 1 przecinek 1 przecinek 1 przecinek 0 przecinek 0 zamknij nawias klamrowy. Linia 46. zamknij nawias klamrowy średnik. Linia 48. if otwórz nawias okrągły istnienieCykluEulera otwórz nawias okrągły macierzSasiedztwa zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 49. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Graf zawiera cykl Eulera kropka cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 50. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Cykl Eulera dwukropek cudzysłów średnik. Linia 51. znajdzCyklEulera otwórz nawias okrągły macierzSasiedztwa przecinek 0 zamknij nawias okrągły średnik. Linia 52. cout otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 53. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 54. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Graf nie zawiera cyklu Eulera kropka cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 55. zamknij nawias klamrowy. Linia 57. return 0 średnik. Linia 58. zamknij nawias klamrowy.

#include <iostream>
using namespace std;

const int n = 6;

void usunKrawedz(int macierzSasiedztwa[n][n], int u, int v) {
    macierzSasiedztwa[u][v] = 0;
    macierzSasiedztwa[v][u] = 0;
}

void znajdzCyklEulera(int macierzSasiedztwa[n][n], int u) {
    for (int v = 0; v < n; v++) {
        if (macierzSasiedztwa[u][v] > 0) {
            usunKrawedz(macierzSasiedztwa, u, v);
            znajdzCyklEulera(macierzSasiedztwa, v);
        }
    }
    cout << u << " ";
}

bool istnienieCykluEulera(int macierzSasiedztwa[n][n]) {
    int stopnieWierzcholkow[n] = {0};
    int liczbaNieparzystych = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            stopnieWierzcholkow[i] += macierzSasiedztwa[i][j];
        }

        if (stopnieWierzcholkow[i] % 2 != 0) {
            liczbaNieparzystych++;
        }
    }

    return liczbaNieparzystych == 0 && n > 0;
}

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

    if (istnienieCykluEulera(macierzSasiedztwa)) {
        cout << "Graf zawiera cykl Eulera." << endl;
        cout << "Cykl Eulera: ";
        znajdzCyklEulera(macierzSasiedztwa, 0);
        cout << endl;
    } else {
        cout << "Graf nie zawiera cyklu Eulera." << endl;
    }
    
    return 0;
}

Ćwiczenie 4

Napisz program, który sprawdzi, czy dla danego grafu reprezentowanego przez macierz sąsiedztwa istnieją ścieżki oraz cykle Hamiltona wychodzące z podanego wierzchołka początkowego. Jeśli tak, program powinien je wypisać.

Specyfikacja problemu:

Dane:

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

Wynik:

komunikat informujący o tym, czy graf zawiera ścieżki i cykle Hamiltona wychodzące z podanego wierzchołka

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

Graf:

R1Lp6pSNKvOel

Macierz sąsiedztwa przedstawionego grafu oraz wierzchołek początkowy:

const int n = 5;

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

int start = 0;

Przykładowy wynik dla podanych danych:

Sciezki i cykle Hamiltona:
Sciezka Hamiltona: 0 1 2 3 4 
Cykl Hamiltona: 0 1 2 3 4 0
Sciezka Hamiltona: 0 1 2 4 3 
Sciezka Hamiltona: 0 1 3 2 4 
Cykl Hamiltona: 0 1 3 2 4 0
Sciezka Hamiltona: 0 1 3 4 2 
Sciezka Hamiltona: 0 4 2 1 3 
Sciezka Hamiltona: 0 4 2 3 1 
Cykl Hamiltona: 0 4 2 3 1 0
Sciezka Hamiltona: 0 4 3 1 2 
Sciezka Hamiltona: 0 4 3 2 1 
Cykl Hamiltona: 0 4 3 2 1 0

RMzr3gouOG6Y7

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. void wypisz otwórz nawias okrągły int sciezka otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int n przecinek bool czyCykl zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Sciezka Hamiltona dwukropek cudzysłów ś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 i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. cout otwórz nawias ostrokątny otwórz nawias ostrokątny sciezka otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 10. zamknij nawias klamrowy. Linia 11. cout otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 13. if otwórz nawias okrągły czyCykl zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Cykl Hamiltona dwukropek cudzysłów średnik. Linia 15. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. cout otwórz nawias ostrokątny otwórz nawias ostrokątny sciezka otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 17. zamknij nawias klamrowy. Linia 18. cout otwórz nawias ostrokątny otwórz nawias ostrokątny sciezka otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 19. cout otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 20. zamknij nawias klamrowy. Linia 21. zamknij nawias klamrowy. Linia 23. void znajdzSciezkeHamiltona 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 bool odwiedzone otwórz nawias kwadratowy n zamknij nawias kwadratowy przecinek int sciezka otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int akt przecinek int poz zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. if otwórz nawias okrągły poz znak równości znak równości n zamknij nawias okrągły otwórz nawias klamrowy. Linia 25. wypisz otwórz nawias okrągły sciezka przecinek n przecinek macierzSasiedztwa otwórz nawias kwadratowy akt zamknij nawias kwadratowy otwórz nawias kwadratowy sciezka otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias kwadratowy znak równości znak równości 1 zamknij nawias okrągły średnik. Linia 26. return średnik. Linia 27. zamknij nawias klamrowy. Linia 29. for otwórz nawias okrągły int v znak równości 0 średnik v otwórz nawias ostrokątny n średnik v plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 30. if otwórz nawias okrągły wykrzyknik odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy ampersant ampersant macierzSasiedztwa otwórz nawias kwadratowy akt zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości znak równości 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości true średnik. Linia 32. sciezka otwórz nawias kwadratowy poz zamknij nawias kwadratowy znak równości v średnik. Linia 34. znajdzSciezkeHamiltona otwórz nawias okrągły macierzSasiedztwa przecinek odwiedzone przecinek sciezka przecinek v przecinek poz plus 1 zamknij nawias okrągły średnik. Linia 36. odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości false średnik. Linia 37. zamknij nawias klamrowy. Linia 38. zamknij nawias klamrowy. Linia 39. zamknij nawias klamrowy. Linia 41. void sciezkiCykle 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 start zamknij nawias okrągły otwórz nawias klamrowy. Linia 42. bool odwiedzone otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy false zamknij nawias klamrowy średnik. Linia 43. int sciezka otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 45. odwiedzone otwórz nawias kwadratowy start zamknij nawias kwadratowy znak równości true średnik. Linia 46. sciezka otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości start średnik. Linia 47. znajdzSciezkeHamiltona otwórz nawias okrągły macierzSasiedztwa przecinek odwiedzone przecinek sciezka przecinek start przecinek 1 zamknij nawias okrągły średnik. Linia 48. zamknij nawias klamrowy. Linia 50. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 51. 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 52. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 zamknij nawias klamrowy przecinek. Linia 53. otwórz nawias klamrowy 1 przecinek 0 przecinek 1 przecinek 1 przecinek 0 zamknij nawias klamrowy przecinek. Linia 54. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 zamknij nawias klamrowy przecinek. Linia 55. otwórz nawias klamrowy 0 przecinek 1 przecinek 1 przecinek 0 przecinek 1 zamknij nawias klamrowy przecinek. Linia 56. otwórz nawias klamrowy 1 przecinek 0 przecinek 1 przecinek 1 przecinek 0 zamknij nawias klamrowy. Linia 57. zamknij nawias klamrowy średnik. Linia 59. int start znak równości 0 średnik. Linia 61. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Sciezki i cykle Hamiltona dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 62. sciezkiCykle otwórz nawias okrągły macierzSasiedztwa przecinek start zamknij nawias okrągły średnik. Linia 64. return 0 średnik. Linia 65. zamknij nawias klamrowy.

#include <iostream>
using namespace std;

const int n = 5;

void wypisz(int sciezka[], int n, bool czyCykl) {
    cout << "Sciezka Hamiltona: ";
    for (int i = 0; i < n; i++) {
        cout << sciezka[i] << " ";
    }
    cout << endl;

    if (czyCykl) {
        cout << "Cykl Hamiltona: ";
        for (int i = 0; i < n; i++) {
            cout << sciezka[i] << " ";
        }
        cout << sciezka[0]; 
        cout << endl;
    }
}

void znajdzSciezkeHamiltona(int macierzSasiedztwa[n][n], bool odwiedzone[n], int sciezka[], int akt, int poz) {
    if (poz == n) {
        wypisz(sciezka, n, macierzSasiedztwa[akt][sciezka[0]] == 1);
        return;
    }

    for (int v = 0; v < n; v++) {
        if (!odwiedzone[v] && macierzSasiedztwa[akt][v] == 1) {
            odwiedzone[v] = true;
            sciezka[poz] = v;

            znajdzSciezkeHamiltona(macierzSasiedztwa, odwiedzone, sciezka, v, poz + 1);

            odwiedzone[v] = false;
        }
    }
}

void sciezkiCykle(int macierzSasiedztwa[n][n], int start) {
    bool odwiedzone[n] = {false};
    int sciezka[n];

    odwiedzone[start] = true;
    sciezka[0] = start;
    znajdzSciezkeHamiltona(macierzSasiedztwa, odwiedzone, sciezka, start, 1);
}

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

    cout << "Sciezki i cykle Hamiltona:" << endl;
    sciezkiCykle(macierzSasiedztwa, start);

    return 0;
}

Prezentacja multimedialna

Dla nauczyciela