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 43 --- [ Teorie + 1 Probleme rezolvate ]

Parcurgerea grafurilor in latime (Breadth First)

Derularaea algoritmului presupune alegerea la un moment dat, dintre vecinii unui varf, pe acela ce nu a fost vizitat inca. Acest lucru este posibil prin folosirea unui vector VIZITAT de dimensiune n ale carui componente se definesc astfel:

Vizitat[i] = 1 daca nodul I a fost vizitat

                  = 0 in rest

Se va folosi o structura de tip coada.

Algoritmul parcurgerii in latime

Pas. 1.   Se prelucreaza varful initial k

              Pas. 1.1.  Se adauga varful k in coada

              Pas. 1.2. Varful k se considera vizitat

Pas. 2.  Cat timp coada este nevida se executa:

               Pas. 2.1. Pentru toti vecinii j nevizitati inca ai varfului k

                     Pas. 2.1.1. Se adauga varful j in coada

                Pas. 2.1.2. Varful j se considera vizitat

                Pas. 2.2. Se reia de la Pas. 2.1. (varful j devine varful k)

void Parc_Lat()

{

prim = 1;

ultim = 1;

Cd[1] = 1;

cout<<endl<<Cd[1];

Viz[1] = 1;

while (prim<=ultim)

{

            nod = Scoate(Cd, prim);

            for (j=1 ; j<= n; j++)

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

                {

                  Add(Cd, ultim, j);

                  cout<<"   "<<j;

                  Viz[j]=1;

                }

}

}

Cd – coada

Viz – vectorul VIZITAT

Scoate – functie care returneaza primul element din coada

Add – adauga un element in coada

Prim – indicele primului element din coada (la scoatere creste cu o unitate)

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

In coada vor fi elemente atata timp cat  prim <=ultim

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

S
o
l
u
ț
i
a:
Introdu următorul text: 881044894
#include<iostream>
using namespace std;
int a[50][50],i,j,n,cd[50],viz[50];
void citire(int a[50][50],int n)
{for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
{cout<<" muchie intre "<<i<<" si "<<j<<" ";
cin>>a[i][j];
a[i][i]=0;
a[j][i]=a[i][j];
}}
int scoate(int cd[50],int &prim){
int p=prim;
prim++;
return cd[p];}
int add(int cd[50],int &ultim,int v)
{ultim++;
cd[ultim]=v;}
void muchie(int a[50][50],int n){
int prim=1;
int ultim=1;
cd[1]=1;
for(int i=1;i<=n;i++)
viz[i]=0;
cout<<cd[1]<<" ";
viz[1]=1;
while(prim<=ultim)
{int x=scoate(cd,prim);
for(i=1;i<=n;i++)
if(a[x][i]==1 && viz[i]==0){
cout<<i<<" ";
viz[i]=1;
add(cd,ultim,i);}}}
int main(){
cout<<"n=";cin>>n;
citire(a,n);
muchie(a,n);
return 0;}
Fii primul care comentează lecţia
     Submit
  |   Lectia 44   |   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.