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

void main()
{
  int x,y,i,j,m;
  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_latime();   getchQ; }

Leave a Reply

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

2 + sixteen =

Time limit is exhausted. Please reload CAPTCHA.