Ocena użytkownikóww: ***** / 35
Nadesłany przez Michał Knasiecki, 09 sierpnia 2005 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
przeszukiwanie_c/bfs_dfs.cpp:
/********************************************************
* *
* Przeszukiwanie grafu w lab i wszerz *
* Program zostal pobrany ze strony www.algorytm.org *
* Znajdziesz na niej opis tego algorytmu i wielu innych *
* *
* Autor: Michal Knasiecki *
* *
*********************************************************/
/*
UWAGA
W ponizszej implementacji uzywamy biblioteki STL.
Jezeli Twoj kompilator nie jest w nia wyposazony, musisz zastapic
ja wlasna implementacja stosu i kolejki.
*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <vector.h> //STL
#include <list.h> //STL
#include <stack.h> //STL
#include <queue.h> //STL
#define Max_Nodes 10 //Maksymalna liczba wierzcholkow w macierzy
using namespace std;
int Macierz[Max_Nodes][Max_Nodes];
int Odwiedzony[Max_Nodes];
int LiczbaWierzcholkow;
//Stos do przechowywania wierzcholkow w DFS
stack<int,vector<int> > stos;
//Kolejka do przechowywania wierzcholkow w BFS
queue<int, list<int> > kolejka;
//Funkcja zwraca OSTATNI nieodwiedzony nastepnik wierzcholka v
int nastepnik_dfs(int v)
{
int i;
for (i=LiczbaWierzcholkow-1;i>=0;i--)
if ((Macierz[i][v]==1)&&(Odwiedzony[i]==0))
{
Odwiedzony[i]=1;
return(i);
}
//Wierzcholek v nie ma juz nastepnikow do odwiedzenia
return(-1);
}
//Funkcja zwraca PIERWSZY nieodwiedzony nastepnik wierzcholka v
int nastepnik_bfs(int v)
{
int i;
for (i=0;i<LiczbaWierzcholkow;i++)
if ((Macierz[i][v]==1)&&(Odwiedzony[i]==0))
{
Odwiedzony[i]=1;
return(i);
}
//Wierzcholek v nie ma juz nastepnikow do odwiedzenia
return -1;
}
void dfs(int v)
{
int u;
int nastepny;
printf("%d ",v+1);
Odwiedzony[v]=1;
nastepny=nastepnik_dfs(v);
while (nastepny!=-1)
{
stos.push(nastepny);
nastepny=nastepnik_dfs(v);
}
if (!stos.empty())
{
u=stos.top();
stos.pop();
dfs(u);
}
}
void bfs(int v)
{
int u;
int nastepny;
printf("%d ",v+1);
Odwiedzony[v]=1;
nastepny=nastepnik_bfs(v);
while (nastepny!=-1)
{
kolejka.push(nastepny);
nastepny=nastepnik_bfs(v);
}
if (!kolejka.empty())
{
u=kolejka.front();
kolejka.pop();
bfs(u);
}
}
void main(void)
{
FILE *Plik_We;
int i,j;
for (i=0;i<Max_Nodes;i++)
Odwiedzony[i]=0;
Plik_We=fopen("graf.txt","rt");
fscanf(Plik_We,"%d",&LiczbaWierzcholkow);
for (j=0;j<LiczbaWierzcholkow;j++)
for (i=0;i<LiczbaWierzcholkow;i++)
fscanf(Plik_We,"%d",&Macierz[i][j]);
//DFS
printf("Przeszukiwanie DFS: ");
dfs(0);
for (i=0;i<Max_Nodes;i++)
Odwiedzony[i]=0;
//BFS
printf("\nPrzeszukiwanie BFS: ");
bfs(0);
printf("\n\n\nDowolny klawisz...");
getch();
fclose(Plik_We);
return;
}