Lee sau un BFS, e chiar usor de facut:
1. alegi un varf de plecare ( in general 1 )
2. pui varful in coada
3. cat timp coada nu este vida
4. extragi primul element.
5. determini toti vecini lui x care
nu au fost vizitati si ii pui in coada, marcandui ca vizitati
6. revi la pasul 3
5. continuie programul cu ce trebuie
Implementarea, o sa folosesc putin stl pentru rapiditate
#include <fstream>
#include <queue> //pentru coada
#include <bitset> // pentru a retine matricea de adiacenta avem nevoie doar de o matrice de biti ( 1 sau 0 )
#define Nmax 301
using namespace std;
ifstream in;
ofstream out;
bitset<Nmax> v[Nmax], uz; //in v - retin matricea de adiacenta si in uz ce varf a fost vizitat
queue<int> Q; //coada
int main()
{int N,M,x,y,i;
in.open("lee.in");;
in>>N>>M; // N - numarul de varfuri , M- numarul de muchii
while( M -- )
{
in>>x>>y;
v[x].flip(y); v[y].flip(x); //marchez v[x][y]=v[y][x]=1
}
Q.push(1); // inserez 1 in coada
uz.flip(1);
out.open("lee.out");
while( !Q.empty() ) //3
{
x=Q.front(); Q.pop(); //4
for( i=1; i<=N; ++i ) //5
if( v[x][i] && !uz[i] )
{
Q.push(i); uz.flip(i);
}
}
//restul programului
return 0;
}
Sper ca fost de ajutor