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(); }

Leave a Reply

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

sixteen + 1 =

Time limit is exhausted. Please reload CAPTCHA.