Informatică, întrebare adresată de 2sg7gr, 8 ani în urmă

Ajutoooooooooooooor in c++ cu explicatie programului
Se dă un graf orientat cu n noduri și un nod p. Să se afișeze toate nodurile q ale grafului, diferite de p, cu proprietatea că există cel puțin un drum de la p la q și lungimea drumului minim este pară.

Răspunsuri la întrebare

Răspuns de andrei750238
7

Explicatie :

  • Folosim parcurgerea in latime (BFS) a nodurilor unui graf.
  • Pornind de la nodul p calculam distanta drumului pana la toate nodurile adiacente. Apoi repetam procedeul pentru fiecare nod adiacent.
  • Ordinea in care parcurgem graful este importanta. Trebuie sa ne asiguram ca parcurgem in fiecare moment nodurile cele mai apropiate de nodul p. Pentru acest motiv folosim o coada.
  • Am ales sa citesc matricea de adiacenta din fisier pentru a nu fi nevoie sa o introduc mereu de la tastatura.

Program C++ :

#include <iostream>

#include <fstream>

#define NMAX 10

using namespace std;

//Citesc matricea declarata static din fisierul date.txt

void citesc(bool matrice[10][10], int& nr_noduri) {

ifstream file("date.txt");

if (!file.is_open()) return;

file >> nr_noduri;

for (int linie = 1; linie <= nr_noduri; linie++) {

 for (int coloana = 1; coloana <= nr_noduri; coloana++) {

  file >> matrice[linie][coloana];

 }

}

file.close();

}

void drum_minim_bfs(bool mat[NMAX][NMAX], int nr_noduri, int nod_sursa, int lungime_drum[]) {

//Implementeaza coada

int index_cap = 0;

int index_coada = 0;

int coada[NMAX] = { 0 };

//Adauga nodul p in coada

coada[index_coada++] = nod_sursa;

//Cat timp coada nu este goala

while (index_cap != index_coada) {

 //Parcurge fiecare nod adiacent cu nodul din capul cozii.

 for (int nod = 1; nod <= nr_noduri; nod++) {

  if (mat[nod][coada[index_cap]]) {

   //Daca nodul nu a fost vizitat

   if (!lungime_drum[nod]) {

    //Calculeaza lungimea drumului din p in nod

    lungime_drum[nod] = lungime_drum[coada[index_cap]] + 1;

    //Adauga nodul la finalul cozii pentru ca nodurile adiacente cu acesta sa fie procesate

    coada[index_coada++] = nod;

   }

  }

 }

 //Sterge nodul procesat din coada

 index_cap++;

}

}

int main() {

bool mat[NMAX][NMAX]; //Matrice adiacenta graf

int n; //Numar noduri

//Citesc matrice adiacenta

citesc(mat, n);

//Primeste id nod sursa

int p;

cout << "Nodul de la care se incepe cautarea : ";

cin >> p;

//Vector care retine lungimea drumului de la nodul sursa la celelalte noduri

int lungime_drum[NMAX] = {0};

drum_minim_bfs(mat, n, p, lungime_drum);

lungime_drum[p] = 0;

//Afiseaza totate nodurile pentru care exista un drum de la p minim par

cout << "\nNoduri cu drum minim par : ";

for (int q = 0; q <= n; q++) {

 if (lungime_drum[q] && lungime_drum[q] % 2 == 0)

  cout << q << " ";

}

}

Anexe:
Alte întrebări interesante