Question

Functie ce afişează gradul interior şi
gradul exterior al fiecărui nod dintr-un graf orientat C++

Cine imi da idei primeste "Cel mai bun raspuns"

Answer 1

Vrei doar idei sau si cod?

Idee: Construieste matricea de adiacenta a grafului, numeri fiecare cifra 1 de pe fiecare linie si fiecare coloana si ar trebui ca una din sume sa fie gradul intern si cealalta cel extern (depinde de cum vezi tu matricea, merge either way).

de exemplu, sa zicem ca ai graful orientat reprezentat de aceste perechi

(1->2), (1->3), (2->1).

poti construi matricea astfel: daca ai i->j pui 1 in Matrice[i][j] si 0 altfel

   1    2     3

1   0    1      1

2   1    0     0

3   0   0     0

sau transpusa ei = 1 in Matrice[j][i] daca ai i->j si 0 altfel.

eu folosesc prima varianta in care numarul de elemente nenule pe linia k reprezinta gradul extern al varfului k si numarul de elemente nenule de pe coloana k reprezinta gradul intern al varfului k.

daca ai nevoie de ajutor la implementare, da-mi un mesaj in privat sau comenteaza si revin.

Implementare C++

#include <iostream>

using namespace std;

int main()

{

int M[100][100], i, j, contor=0, n;

cin>>n;

for(i=1; i<=n; i++)

  {

   for(j=1; j<=n; j++)

      {

        cin>>M[i][j];

        contor=contor+M[i][j];

      }

    cout<<"Gradul extern al nodului "<<i<<" este "<<contor<<endl;

   contor=0;

}

for(i=1; i<=n; i++)

{

for(j=1; j<=n; j++)

{  

contor=contor+M[j][i];

}

cout<<"Gradul intern al nodului "<<i<<" este "<<contor<<endl;

contor=0;

}

return 0;

}