Grafuri neorientate – ponderate

Într-un graf neorientat, fiecărei muchii i se poate asocia o pondere (un cost). Putem considera un graf neorientat fără ponderi ca fiind o particularizare a unui graf cu costuri, fiecare muchie având costul 1. Această pondere (sau cost) va exprima intensitatea relaţiei dintre 2 noduri ale grafului.

Reprezentarea unui astfel de graf G=(X,U) se face utilizând o matrice a ponderilor P(n,n) a cărei elemente se definesc astfel:
p(i,j) = 0 dacă i=j
p(i,j) = c(i,j) în cazul în care (i,j) este o muchie din U unde c(i,j) este costul muchiei (i,j)
P(i,j) = $latex \infty$ în restul cazurilor

Utilizarea grafurilor ponderate este des întâlnită în practică. Cel mai sugestiv exemplu este cel al unei reţele de oraşe, nodurile grafului reprezentând oraşele, muchiile reprezentând legăturile (şoselele) dintre oraşe iar costul lor este dat de distanţa dintre oraşe.

Să se scrie un program C care verifică dacă un graf este conex şi să se afişeze toate componentele sale conexe.


#include "stdio.h"
#include "conio.h"
int n,m,a[20][20],viz[20],nrc=0;
void viziteaza(int nod)
{
  int i;
  viz[nod]=nrc;
  for(i=1;i <= n;i++)     if(a[nod][i] == i && viz[i] == 0)       viziteaza(i); } void main() {   int nod,i,j,x,y;   printf("Introdu numărul de noduri:");   scanf("%d",&n);   printf("Introdu numărul de muchii:");   scanf("%d",&m);   for(i=1;i <= n;i++)     for(j=1;j <= n;j++)       a[i][j]=0;   printf("Introdu muchiile :\n");   for(i=1;i <= m;i++)   {     printf("De la nodul: ");     scanf("%d",&x);     printf("la nodul: ");     scanf("%d",&y);     a[x][y]=a[y][x]=1;   }   for(nod=1;nod <= n;nod++)     if(viz[nod] == 0)     {       nrc++;       viziteaza(nod);     }   if(nrc == 1)     printf("Graful este conex!\n");   else     printf("Graful nu este conex!\n");   printf("Componentele conexe sunt:\n");   for(i=1;i <= nrc;i++)   {     printf("Componenta %d:",i);       for(j=1;j <= n;j++)         if(viz[j] == i)           printf("%d ",j);     putchar("\n");   }   getch(); }

Grafuri neorientate – Drumuri intr-un graf

Matricea de adiacenţă A(n,n) a unui graf G=(X,U) evidenţiază drumurile de lungime 1 între oricare 2 noduri ale grafului.

Pentru a găsi drumurile de lungime 2 între 2 noduri ale unui graf se procedează astfel. Se consideră două noduri $latex x_{i}$ şi $latex x_{j} \in X$. Existenţa unui drum de lungime 2 între ele presupune existenţa unui nod $latex x_{k} \in X$, cu proprietatea că există atât arcul $latex \left ( x_{i},x_{k} \right )$ cât şi arcul $latex \left ( x_{i},x_{k} \right )$. Pentru a vedea dacă acest arc există, se poate lua pe rând fiecare nod al grafului şi verificăm dacă există sau nu ambele arce $latex \left (\left ( x_{i},x_{k} \right ) si \left ( x_{i},x_{k} \right ) \right )$. Aceasta este echivalent cu a verifica dacă în matricea de adiacenţă există vreun indice k astfel încât elementul k al liniei i şi elementul k al coloanei j să fie ambele egale cu 1. Acest lucru este echivalent cu a verifica dacă elementul de pe poziţia (i,j) din $latex A^{2}$ este diferit de 0. Numărul de drumuri de lungime 2 dintre $latex x_{i}$ şi $latex x_{j}$ este dat de valoarea elementului $latex A^{2} \left (i,j \right )$.

Generalizând, numărul de drumuri de lungime k dintre $latex x_{i}$ şi $latex x_{j}$ este dat de valoarea elementului $latex A^{2} \left (i,j \right )$.

Dacă între nodurile $latex x_{i}$ şi $latex x_{j}$ există un drum de lungime >= n atunci el va conţine un număr de noduri mai mare sau egal nu n+1 şi, cum în graf sunt doar n vârfuri, este clar că cel puţin unul, să zicem $latex x_{k}$, va apărea de două ori. Vom avea în acest caz un drum de la $latex x_{i}$ până la prima apariţie a lui $latex x_{k}$, şi un drum de la ultima apariţie a lui $latex x_{k}$ la $latex x_{j}$.Eliminând toate nodurile dintre prima apariţie a lui $latex x_{k}$, şi ultima apariţie a sa vom obţine un drum de la $latex x_{i}$ la $latex x_{j}$, în care $latex x_{k}$ apare o singură dată. Aplicând acest procedeu pentru toate nodurile care apar de mai multe ori pe drum, vom obţine un drum de la $latex x_{i}$ la $latex x_{j}$, în care fiecare nod apare o singură dată (deci un drum elementar), care are evident cel mult n-1 arce. În concluzie, dacă există vreun drum de la $latex x_{i}$ la $latex x_{j}$ atunci există şi un drum elementar şi, deci, va exista o putere a lui A, între $latex A^{1}$ şi $latex A^{n-1}$, în care poziţia (i,j) este diferită de 0. Pentru deciderea existenţei unui drum între oricare două noduri este suficientă, deci, calcularea doar a primelor n-1 puteri ale lui A.

Grafuri neorientate – parcurgerea in adancime

Implementarea parcurgerii în adâncime pentru un graf neorientat


#include
#include
int a[20][20],n,i,j;
void parc_adancime()
{
  int s[40],varf,k,nod,urm[20],viz[20],in;
  printf("Introduceti nodul iniţial de pornire= ");
  scanf("%d",&in);
  for (nod=1;nod <= n;nod++)   {     urm[nod]=0;     viz[nod]=0;   }   varf=1;   //şirul s va păstra ordinea de traversare în adâncime;   //introducem nodul de start în acest şir   s[varf]=in;   //marcăm nodul de pornire ca vizitat   viz[in]=1;   //afişăm nodul de start ca prim nod în traversarea în adâncime   printf("%d ",in);   while (varf >= 1)
  {
    //nod va fi nodul căruia îi mai căutăm succesori
    nod=s[varf];
    //k va conţine numărul nodului de unde reîncepem să
    // căutam succesori pentru nodul nod
    k=urm[nod]+1;
    while ((k <= n) && ((a[nod][k] == 0) || ((a[nod][k]==1)&&(viz[k]==1))))     {       k++;     urm[nod]=k;     }     if (k == n+1)       vârf--;     else     {       varf++;       s[varf]=k;       viz[k]=1;       printf("%d", s[varf]);     }   }   putchar("\n"); } void main() {   int m,i,j,x,y;   printf("Introduceti numărul de noduri n=");   scanf("%d",&n);   printf("Introduceti numărul de muchii m=");   scanf("%d",&m);   for(i=1;i <= n;i++)     for(j=1;j <= n;j++)       a[i][j]=0;   for(i=1;i <= m;i++)   {     printf("De la nodul:");     scanf("%d",&x);     printf("La nodul:");     scanf("%d",&y);     a[x][y]=a[y][x]=1;   }   parc_adancime();   getch(); }

Grafuri neorientate – parcurgerea in latime

Implementarea parcurgerii în lăţime pentru un graf neorientat


#include "stdio.h"
#include "conio.h"
int a[20][20],n;
void parc_latime()
{
  int c[20],p,u,v,viz[20],im,nod;
  printf("Dati nodul de pornire pentru parcurgere: ");
  scanf("5d",&in);
  for(nod=1;nod <= n; nod++)     viz[nod]=0;   p=1;u=1;   //traversarea începe cu nodul in; şirul c va păstra ordinea de traversare   c[1]=in;   //marcăm nodul in ca vizitat   viz[in]=1;   while(p <= u)   {     //vom căuta vecinii nodului v     v=c[p];     for(nod=1;nod <= n;nod++)       //dacă există muchie între nodul nod şi nodul v şi       //nodul nod nu a fost vizitat       if((a[v][nod]==1)&&(viz[nod]==0))       {         //incrementăm indicele şirului ce conţine traversarea         u++;         //punem nodul în şirul ce conţine traversarea         c[u]=nod;         //marcăm nodul ca vizitat         viz[nod]=1;       }       //vom căuta vecinii următorului nod din şirul ce conţine traversarea       p++;   }   for (ind=1;ind <= n;ind++)     printf("%d ",c[ind]);   putchar("\n"); } Continue reading

Metoda Divide et Impera – Problema cautarii binare

Prezentare generala:
Divide et Impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:

1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.

Se citeşte un şir de n elemente numere întregi ordonate crescător şi o valoare întreagă key. Să se decidă dacă valoarea key se găseşte printre valorile şirului de elemente şi în caz afirmativ să se tipărească indicele componentei care conţine acea valoare.


#include "stdio.h"
int a[10],n,key;

void caut(int i, int j)
{
  if(key == a[(i+j)/2])
    printf("Valoarea a fost gasita la indicele %d\n",(i+j)/2);
  else
    if(i < j)       if(nr < a[(i+j)/2])         caut(i, (i+j)/2-1);       else         caut((i+h)/2+1,j); } Continue reading

Metoda Divide et Impera – Elementul maxim intr-un sir

Prezentare generala:
Divide et Impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:

1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.

Se citeşte un şir de n elemente numere întregi. Să se găsească maximul elementelor acestui şir utilizând metoda divide et impera.

#include "stdio.h"
int a[10],n;
int max(int i, int j)
{
  int a,b;
  if(i == j)
    return a[i];
  else
  {
    a=max(i,(i+j)/2);
    b=max((i+j)/2+1,j);
    if(a > b)
      return (a);
    else
      return (b);
  }
}
Continue reading

Metoda Divide et Impera – Problema Turnurilor din Hanoi

Prezentare generala:
Divide et Impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:

1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.

Legenda acestei probleme spune că Brahma a fixat pe Pământ trei tije de diamante şi pe una din ele a pus în ordine crescătoare 64 de discuri de aur de dimensiuni diferite, cu discul cel mai mare jos. Singura operaţiune permisă călugărilor era mutarea a câte unui singur disc de pe o tijă pe alta, astfel încât niciodată să nu se pună un disc mai mare peste unul mai mic. Legenda spune că atunci când călugării vor muta toate cele 64 de discuri respectând regulile de maa sus, atunci va veni sfârşitul lumii. Presupunând că în fiecare secundă se mută un disc, lucrând fără întrerupere, cele 64 de discuri nu pot fi mutate nici în 500 de miliarde de ani de la începutul acţiunii!

Vom considera trei tije verticale notate Stânga, Mijloc, Dreapta. Pe tija Stânga se găsesc aşezate n discuri de diametre diferite, în ordinea descrescătoare a diametrelor, privind de jos în sus. Iniţial, tijele Mijloc şi Dreapta sunt goale. Să se afişeze toate mutările prin care discurile de pe tija Stânga se mută pe tija Mijloc, în aceeaşi ordine, respectând următoarele reguli:
• la fiecare mişcare se mută un singur disc
• un disc mai mare nu poate fi plasat peste un disc cu diametrul mai mic
• un disc mai mare nu poate fi plasat peste un disc cu diametrul mai mic
Continue reading

Metoda Divide et Impera – Suma elementelor unui sir

Prezentare generala:
Divide et Impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:

1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.


#include "stdio.h"
#incude "conio.h"
int a[20];
int divide(int ls, int ld)
{
  int mijloc,d1,d2;
  if(ls != ld)
  {
    mijloc=(ls+ld)/2;
    d1=divide(ls, mijloc);
    d2=divide(mijloc+1,ld);
    return(d1+d2);
  }
  else
    return(a[ls]);
}
Continue reading

Backtracking – problema mingii

Se dă un teren parcelat cu porţiuni de teren pătrate, fiecare având o anumită cotă. Cotele se citesc de la tastatură şi se reţin într-o matrice de m/n poziţii. O bilă se găseşte într-o poziţie iniţială, având nişte coordonate iniţiale ce se citesc de la tastatură. Se ştie că bila poate sări de la o cotă mai mare spre o cotă mai mică, pe orizontală, verticală şi pe diagonale, rostogolindu-se astfel către marginea terenului. Se cere să se afişeze toate variantele de deplasare a mingii până la atingerea unei margini.


#include "stdio.h"
#include "conio.h"
int a[8]={1,1,0,-1,-1,-1,0,1}, b[8]={0,1,1,1,0,-1,-1,-1};
//tablou va păstra cotele iar drum drumul
//parcurs de minge (folosind valori 0 şi 1)
int tablou[10][10],drum[10][10],m,n;
//funcţia de afişare a soluţiei void afiseaza(void)
{
  int p,r;
  for(p=0;p < m;p++)   {   for(r=0;r < n;r++)     printf("%d",drum[p][r]);   putchar("\n");   }   putchar("\n");   getch(); } Continue reading

Backtracking – problema calului

Se consideră o tablă de şah având m/n câmpuri. Se plasează un cal în colţul din stânga sus. Calul se mişcă conform regulilor din şah. Se cere să se găsească toate variantele (dacă există) de a acoperi întreaga tablă, adică să se determine un număr de m*n-i mutări astfel încât fiecare câmp să fie vizitat o singură dată.


#include "stdio.h"
#include "conio.h"
//şirurile pentru cele 8 salturi
int a[8]={2,1,-1,-2,-2,-1,1,2}, b[8]={1,2,2,i,-1,-2,-2,-1};
//matricea t va conţine drumul
int t[10][10],m,n;
//funcţia de afişare a soluţiei
void afiseaza(void)
{
  int p,r;
  for(p=0;p < m;p++)   {     for(r=0;r < n;r++)     printf("%d",t[p][r]);   putchar("\n");   }   getch(); } Continue reading