Question

va rog sa ma ajutati cu o problema. Realozati un program C++ care sa afiseze gradul varfurilor unui graf orientat.

Answer 1

Iti aduci aminte povestea cu matricea de adiacenta de la graful neorientat.
La graful orientat, povestea e putin diferita. elementele matricii A[i][j]=1 daca si numai daca exista o muchi de la i->j SI directia sagetii este de la i la j
Pentru graful atasat uite aici matricea de adiacenta
0 1 1 0 0 0 0 0 0 0 1 00 0 0 0 0 00 0 0 0 1 01 0 0 1 0 0 0 0 0 0 0 0

dupa cum observi, pe fiecare linie ai valoarea 1 daca de la numarul liniei la acea valoare exista o muchie cu directie: ex: nodul 1 are sageti catre 2,3 numai pe A12,A13 ai valoarea 1. Pe fiecare coloana, ai 1 numai daca este o sageata indreptata catre nod: pentru nodul 5 ai 2 si 4, A25,A45 pentru ca acolo ai sagetile INSPRE nodul 5.
Ei bine, gradul unui nod cu sageti iesite din el se numeste grad exterior
gradul unui nod cu sageti intrand in el se numeste grad interior
si gradul total este diferenta dintre gradul exterior(cate pleaca din nod) si gradul interior(cate intra in nod)
Pentru nodul 5 de exemplu avem grad exterior=2(de la 5 la 1 si de la 5 la 4) dar grad interior=2(de la 2 la 5 si de la 4 la 5) atunci graful total este grad exterior-grad interior=2-2=0

Mai jos ai programul cu toate trei determinate:

#include <iostream>
using namespace std;

int grade[20];
int main()
{
int a[20][20];
int n,i,j,grad_ext,grad_int;
cout<<"Introduceti nr de noduri din graf: ";
cin>>n;
cout<<"Introduceti matricea adiacenta grafului orientat: \n";
for(i=0;i<n;i++){
for(j=0;j<n;j++){
cin>>a[i][j];
}
}
cout<<"Nodurile cu grade exterioare sunt: \n";
for(i=0;i<n;i++){
grad_ext=0;
for(j=0;j<n;j++){
if(a[i][j]>0){
grad_ext++;
grade[i]--;
}
}
if(grad_ext>0){
cout<<i+1<<" grad "<<grad_ext<<endl;
}
}
cout<<"Nodurile cu grade interioare sunt: \n";
for(j=0;j<n;j++){
grad_int=0;
for(i=0;i<n;i++){
if(a[i][j]>0){
grad_int++;
grade[j]++;
}
}
if(grad_int>0){
cout<<j+1<<" grad "<<grad_int<<endl;
}
}
cout<<"Grade totale pentru fiecare varf: \n";
for(i=0;i<n;i++){
cout<<"Varful "<<i+1<<" cu gradul total "<<grade[i]<<endl;
}
return 0;
}