algorytm.org

Implementacja w C/C++

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Przeszukiwanie grafu wszerz (BFS) i w głąb (DFS) - Implementacja w C/C++
Ocena użytkownikóww: *****  / 35
SłabyŚwietny
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;
}


Komentarze
photo
-6 # Marta23 2014-07-05 08:10
Czy w funkcji dfs w while'u nie powinno być nastepny=nastepnik_dfs(n astepny)? Jeśli się mylę poprawcie mnie :)
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz