a IX-a A0 lecții INFORMATICĂ | 2 lecții T.I.C.
T.I.C.
█
Lectia 01   |   Lectia 02
a IX-a B0 lecții INFORMATICĂ | 0 lecții T.I.C.
a IX-a C0 lecții INFORMATICĂ | 0 lecții T.I.C.
a IX-a D0 lecții INFORMATICĂ | 0 lecții T.I.C.
a IX-a E0 lecții INFORMATICĂ | 0 lecții T.I.C.
a X-a A0 lecții INFORMATICĂ | 0 lecții T.I.C.
a X-a B0 lecții INFORMATICĂ | 0 lecții T.I.C.
a X-a C0 lecții INFORMATICĂ | 0 lecții T.I.C.
a X-a D0 lecții INFORMATICĂ | 0 lecții T.I.C.
a XI-a A30 lecții INFORMATICĂ | 0 lecții T.I.C.
Informatică
█
Lectia 07   |   Lectia 08   |   Lectia 09   |   Lectia 10   |   Lectia 11   |   Lectia 12   |   Lectia 13   |   Lectia 14
█
Lectia 16   |   Lectia 18   |   Lectia 19   |   Lectia 20   |   Lectia 21
█
Lectia 23   |   Lectia 24
█
Lectia 36
█
Lectia 40   |   Lectia 41   |   Lectia 42   |   Lectia 43   |   Lectia 44
Lectia 44 --- [ Teorie + 1 Probleme rezolvate ]

Parcurgerea grafurilor in adancime (Depth First)

Derularaea algoritmului presupune vizitarea unui varf apoi a varfului adiacent cu acesta si asa mai departe , pana se revine la un alt varf si se alege un alt  varf nevizitat inca. Acest lucru este posibil prin folosirea unui vector VIZITAT de dimensiune n ale carui componente se definesc astfel:

Se va folosi o structura de tip stiva.

Algoritmul parcurgerii in adancime

Pas. 1.   Se adauga varful  k in stiva si se considera vizitat

Pas. 2.   Se analizeaza varful k

         Pas. 2.1. Se cauta primul din vecinii nevizitati

                Pas. 2.1.1.  Daca exista (fie j acesta) se dauga in stiva si    se considera vizitat

                Pas. 2.1.2. Daca nu exista se scoate urmatorul nod din stiva (fie j  acesta)

           Pas. 2.2. Varful j devine varful ce trebuie analizat (varful k)

Pas. 3. Cat timp stiva este nevida se executa Pas. 2.

void Parc_Ad()  {

ultim = 1;

St[1] = 1;

cout<<endl<<St[1];

Viz[1] = 1;

while (ultim>0)  {

            nod = Scoate(St, ultim);

            j=0;

            ok=0;

            for (j=1; ((j<=n) && (ok==0)); j++)

               if((a[nod][j] == 1) && (Viz[j] == 0)) {

                  Add(St, ultim, j);

                  cout<<"   "<<j;

                  Viz[j]=1;

                  ok=1;

                }

            while ((ok==0) && (j<=n));

            if (ok==0) ultim--;

}

}

 

St – stiva

Viz – vectorul VIZITAT

Scoate – functie care returneaza primul element din stiva

Add – adauga un element in stiva

Ultim – indicele ultimului element din stiva (la adaugare creste cu o unitate)

Ok – indica daca a fost gasit un alt varf adiacent cu cel prelucrat. ( daca e 1 inseamna ca s-a gasit)

In stiva vor fi elemente atata timp cat    ultim > 0


1. Sa se scrie un program C++ care memoreaza un graf neorientat cu ajutorul matricei de adiacenta si parcurge graful in adancime.
Propune o soluție

S
o
l
u
ț
i
a:
Introdu următorul text: 477891973
#include<iostream>
using namespace std;
int a[20][20],n,ultim,viz[20],nod,i,j,st[20],gasit,u;
void citire (int a[20][20],int n,int i,int j)
{if (i<=n)
{
    if (j<=n)
{
    cout<<"este muchie intre"<<i<<" si "<<j<<" ";
cin>>a[i][j];
a[j][i]=a[i][j];
a[i][i]=0;
citire(a,n,i,j+1);
}
else
citire(a,n,i+1,i+2);
}
}
int scoate (int st[20],int u )
{int x=u;
u--;
return st[x];}
void add( int st[20],int &u, int x)
{u++;
st[u]=x;}
void parc_ad()
{ultim=1;
st[1]=1;
viz[1]=1;
cout<<st[1]<<" ";
while(ultim>0)
{nod=scoate(st,ultim);
gasit=0;
for(i=1;i<=n && gasit==0;i++)
if(a[nod][i] && viz[i]==0)
gasit=i;
if(gasit!=0)
{add(st,ultim,gasit);
cout<<gasit<<" ";
viz[gasit]=1;}
else
ultim--;
}
}
int main ()
{cout<<"n=";
cin>> n;
citire (a,n,1,2);
parc_ad();
return 0;
}
Fii primul care comentează lecţia
     Submit
  |   Lectia 45   |   Lectia 46   |   Lectia 46_1
█
Lectia 47   |   Lectia 48   |   Lectia 49   |   Lectia 50   |   Lectia 50_1
█
Lectia 50_2
a XI-a B0 lecții INFORMATICĂ | 0 lecții T.I.C.
a XI-a C0 lecții INFORMATICĂ | 0 lecții T.I.C.
a XI-a D0 lecții INFORMATICĂ | 0 lecții T.I.C.
a XI-a E0 lecții INFORMATICĂ | 1 lecții T.I.C.
T.I.C.
█
Fişa 01
a XII-a A2 lecții INFORMATICĂ | 6 lecții T.I.C.
Informatică
█
Lectia 01   |   Lectia 02
T.I.C.

█
Fişa 01   |   Fişa 02   |   Fişa 03   |   Fişa 04   |   Fişa 05   |   Fişa 06
a XII-a B0 lecții INFORMATICĂ | 0 lecții T.I.C.
a XII-a C0 lecții INFORMATICĂ | 0 lecții T.I.C.
a XII-a D0 lecții INFORMATICĂ | 0 lecții T.I.C.
a XII-a E0 lecții INFORMATICĂ | 0 lecții T.I.C.
Excelenta A0 lecții INFORMATICĂ | 0 lecții T.I.C.