Valaki elmeagyarázná az alábbi gráfjáró algoritmust?
#include<iostream>
using namespace std;
const int N=9;
int graph[N][N]={
// 0 1 2 3 4 5 6 7 8
{0,0,1,0,1,0,0,0,0}, //0
{0,0,1,1,0,1,0,0,0}, //1
{1,1,0,0,0,0,1,1,0}, //2
{0,1,0,0,0,0,0,0,0}, //3
{1,0,0,0,0,0,0,0,1}, //4
{0,1,0,0,0,0,0,1,0}, //5
{0,0,1,0,0,0,0,0,0}, //6
{0,0,1,0,0,1,0,0,0}, //7
{0,0,0,0,1,0,0,0,0} //8
};
int path[N];
int pX=0;
bool check[N];
void depthS(int); //mélységi bejárás
void breadthS(int); //szélességi bejárás
void init();
//Sor változói
const int qN=N+1;
int queue[qN];
int qBegin=0,qEnd=qN-1;
//Sor eljárásai
void qPut(int);
int qGet();
int qSize();
main(){
init();
int v0=0;
depthS(v0);
cout<<"Melysegi bejaras a(z) "<<v0<<". csucsbol:"<<endl;
for(int i=0;i<pX;i++)cout<<path[i]<<" ";
cout<<endl;
init();
v0=5;
depthS(v0);
cout<<"Melysegi bejaras a(z) "<<v0<<". csucsbol:"<<endl;
for(int i=0;i<pX;i++)cout<<path[i]<<" ";
cout<<endl;
init();
v0=0;
breadthS(v0);
cout<<"Szelessegi bejaras a(z) "<<v0<<". csucsbol:"<<endl;
for(int i=0;i<pX;i++)cout<<path[i]<<" ";
cout<<endl;
init();
v0=1;
breadthS(v0);
cout<<"Szelessegi bejaras a(z) "<<v0<<". csucsbol:"<<endl;
for(int i=0;i<pX;i++)cout<<path[i]<<" ";
cout<<endl;
}
//mélységi bejárás
void depthS(int v){
int i;
check[v]=1;
path[pX]=v;
//pX++;
for(i=0;i<N;i++)
{
if(graph[v][i]==1 && check[i]==0)
depthS(i);
}
}
//szélességi bejárás
void breadthS(int v){
path[pX++]=v;
check[v]=1;
qPut(v);
while((v=qGet())!=-1)
{
for(int i=0;i<N;i++)
{
if(check[i]==0 && graph[v][i]==1)
{
path[pX++]=i;
check[i]=1;
qPut(i);
}
}
}
}
void init(){
pX=0;
for(int i=0;i<N;i++)check[i]=false;
}
//Sor eljárásai
void qPut(int number){
if(qSize()<qN-1){
qEnd=(qEnd+1)%qN;
queue[qEnd]=number;
}
}
int qGet(){
if(qSize()>0){
int tmp=queue[qBegin];
qBegin=(qBegin+1)%qN;
return tmp;
}else
return -1;
}
int qSize(){
return (qN+qEnd-qBegin+1)%qN;
}
Kapcsolódó kérdések:
Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!