Kezdőoldal » Számítástechnika » Programozás » Valaki elmeagyarázná az...

VálaszVálaszoló kérdése:

Valaki elmeagyarázná az alábbi gráfjáró algoritmust?

Figyelt kérdés

#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;

}


2017. ápr. 25. 20:54
 1/2 anonim ***** válasza:

[link]


Bocs a képigénytelenségéért, egy kővel csináltam.

2017. ápr. 25. 21:05
Hasznos számodra ez a válasz?
 2/2 anonim ***** válasza:
100%
Ez valami ocsmánykód versenyre készült?
2017. ápr. 25. 21:18
Hasznos számodra ez a válasz?

Kapcsolódó kérdések:





Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!