Grafuri neorientate – implementarea unui graf utilizand matricea de adiacenta


//definirea tipului nod
typedef TIP_NODG
{
  int cheie;
  ... informaţii
} tip_nodg;
ntip_nodg nod[Nmax];
//tabloul de noduri
//Nmax este numărul maxim de noduri
int arc[N max] [N max];
//matricea de adiacenţă

Adăugarea unui nod cu cheia key:
int i;
nod[N].cheie=key;
//adăugăm nodul N+1
for(i=0;i <= N;i++)   arc[i][N]=arc[N][i]=0; //iniţalizarea cu o a conexiunilor cu celelalte noduri N++; //incrementarea numărului de noduri

În cazul în care este importantă poziţia nodului ce se inserează în tablou, inserţia nu se va face pe ultima poziţie, ci în poziţia dorită poz:
void Insereaza_nod(int poz, int key)
{
  int i,j;
  //incrementarea numărului de noduri
  N++;
  for(i=N-1;i >= poz; i--)
  {
  //mutarea liniilor
  arc[i+1][j]=arc[i][j];
  //mutarea coloanelor
  arc[j][i+1]=arc[i][j];
  }
}
//setarea cheii nodului
nod[poz].cheie=key;
for(i=0;i < N;i++)   //inițializarea cu 0 a conexiunilor cu celelalte noduri   arc[i][poz]=arc[poz][i]=0; } Căutarea unui nod într-un graf: //funcţia de căutare a unui nod cu cheia key int cauta_nod(int key) {   int i;   for(i=0;i < N;i++)     //returnează poziţia în cazul în care cheia a fost găsită     if(k == nod[i].cheie)       return(i);   //returnează -1 dacă cheia nu a fost găsită   return(-1); } Ştergerea unui nod din graf presupune eliminarea lui din tabloul de noduri void sterg_nod(int poz) {   int i;   //aducem nodul N în locul celui pe care il suprimăm   nod[poz]=nod[N-1];   for(i=0;i < N;i++)     //suprascrie linia     arc[poz][i]=arc[N-1][i];   for(i=0;i < N;i++)     //suprascrie coloana     arc[i][poz]=arc[i][N-1];   //decrementăm numărul de noduri   N--; }

Leave a Reply

Your email address will not be published. Required fields are marked *

19 − eight =

Time limit is exhausted. Please reload CAPTCHA.