PROGRAMOWANIE I ALGORYTMY

Przeszukiwanie w głąb


Jednym ze sposobów przeszukiwania grafu jest algorytm przeszukujący w głąb (DFS Depth-first search). Strategia takiego rozwiązania jest bardzo prosta. Z wierzchołka początkowego przechodzimy do pierwszego połączonego z nim - nazwijmy go wierzchołkiem A. Następnie z wierzchołka A przechodzimy do pierwszego nieodwiedzonego do tej pory z nim połączonego, nazwijmy go B. Z tego zaś do pierwszego nieodwiedzonego itd. Gdy w ten sposób skończą nam się wierzchołki, cofamy się do wierzchołka, z którego ostatnio przyszliśmy i wchodzimy z tego miejsca do następnego nieodwiedzonego (jeśli taki jest). Czynności te powtarzamy do momentu odwiedzenia wszystkich wierzchołków. 

Każdorazowe przejście do wierzchołka odznaczamy ustawiając flagę jako odwiedzony (np. można te informacje przechowywać w dodatkowej tablicy lub jako dodatkowe pole w strukturze).

Dla przykładu posłużymy się następującą strukturą grafu:

Definicje połączeń wierzchołków

1 <--> 2
2 <--> 3
3 <--> 4
3 <--> 5
1 <--> 5
4 <--> 8
8 <--> 5
8 <--> 9
6 <--> 5
5 <--> 7

Powyższy przykład prezentuje poniższy szkic:

graf DFS

Załóżmy, że rozpoczynamy z wierzchołka z numerem 1. Odznaczamy go jako odwiedzony i przechodzimy do wierzchołka z numerem (jest to pierwsze połączenie), z 2 przechodzimy do 3, następnie do 4, 8, 5, 6, 7. Siódmy wierzchołek nie ma więcej już połączeń, więc cofamy się do następnego wierzchołka, który je ma. Jest to wierzchołek numer 8, z którego przechodzimy do 9 i tu kończymy przeszukiwanie. Omawiany proces prezentuje poniższa animacja:

przeszukiwanie w głąb

Zakładając, że mamy n wierzchołków i p połączeń, złożoność czasowa omawianego algorytmu wynosi $$O(n+p)$$.

Poniższy kod prezentuje przeszukanie wszystkich wierzchołków grafu metodą w głąb. Rozwiązanie wykorzystuje technikę rekurencji.

//www.algorytm.edu.pl
#include<iostream>
#include<vector>
using namespace std;

struct wierzcholki{
	//połączenia wychodzące z danego wierzchołka
	vector <unsigned int> polaczenia; 
	//okresla, czy wierzchołek został odwiedzony
	bool odwiedzony; 
	//dodatkowe dane dla danego wierzchołka
	//........................
	//........................
}*w;

void DFS(int k)
{
	cout<<"Odwiedzono "<<k<<" wierzcholek\n";
	w[k].odwiedzony = 1;
	for(int i=0; i<w[k].polaczenia.size(); i++)
	//jesli wierzchołek, do którego chcemy przejsć nie został
	//jeszcze odwiedzony
		if(!w[w[k].polaczenia[i]].odwiedzony) 
		//to przechodzimy do niego
			DFS(w[k].polaczenia[i]); 
}

int main()
{
	unsigned int n, pol, pocz, a, b;
	cout<<"Podaj liczbę wierzcholków w grafie: ";
	cin>>n;
	cout<<"Podaj liczbę połączeń w grafie: ";
	cin>>pol;
	cout<<"Podaj wierzchołek, z którego zaczynamy przeszukiwanie: ";
	cin>>pocz;
	
	w = new wierzcholki[n+1];
	
	cout<<"Podaj kolejne połączenia wierzchołków: \n";
	//wczytanie połączeń grafu
	for(int i=0; i<pol; i++)
	{
		cin>>a>>b;
		cout<<a<<" <--> "<<b<<endl;
		//tworzymy połączenie a --> b
		w[a].polaczenia.push_back(b);
		//tworzymy połączenie b --> a
		w[b].polaczenia.push_back(a);
	}
	cout<<"\nOdwiedzano wierzchołki w następującej kolejnosci:\n";
	DFS(pocz);
	
	delete [] w;
	
	return 0;
}

Przykładowe wejście i wyjście:

Podaj liczbę wierzchołków w grafie: 9
Podaj liczbę połączeń w grafie: 10
Podaj wierzchołek, z którego zaczynamy przeszukiwanie: 1
Podaj kolejne połączenia wierzchołków:
1 2
1 <--> 2
2 3
2 <--> 3
3 4
3 <--> 4
3 5
3 <--> 5
1 5
1 <--> 5
4 8
4 <--> 8
8 5
8 <--> 5
8 9
8 <--> 9
6 5
6 <--> 5
5 7
5 <--> 7

Odwiedzano wierzchołki w następującej kolejności:

Odwiedzono 1 wierzcholek
Odwiedzono 2 wierzcholek
Odwiedzono 3 wierzcholek
Odwiedzono 4 wierzcholek
Odwiedzono 8 wierzcholek
Odwiedzono 5 wierzcholek
Odwiedzono 6 wierzcholek
Odwiedzono 7 wierzcholek
Odwiedzono 9 wierzcholek

Przeszukiwanie DFS można zrealizować także wykorzystując stos:

//www.algorytm.edu.pl
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
 
struct graf{
  bool stos; //czy dodany na stos
 
  vector <int> polaczenia; //do przechowywania połączeń
  // dodatkowe opcje
}*w; 
 
void odwiedz(int n)
{
  //wykonaj jakies czynnosci
  //w przypadku odwiedzenia wierzcholka o numerze n
  cout<<"Odwiedzono wierzchołek o numerze: "<<n<<endl;
}
 
void DFS(int n)
{
  stack<int> stos;    //utworzenie stosu 
  stos.push(n);  //dodanie pierwszego wierzcholka na stos
 
  while(!stos.empty()) //dopóki jest cos na stosie
  {
    n = stos.top(); //pobranie elementu ze stosu
 
      stos.pop(); //usuń pobrany element ze stosu
      odwiedz(n); //odwiedź go i zrób coś
      //oraz dodaj wszystkie jego nieodwiedzone i nie będące 
      //na stosie połączenia na stos
      for(int i=0;i<w[n].polaczenia.size();i++)
        if(!w[w[n].polaczenia[i]].stos)
        {
          stos.push(w[n].polaczenia[i]);
          w[w[n].polaczenia[i]].stos = 1; //oznaczenie, że dodano na stos
          cout<<"Dodano na stos wierzcholek nr "<<w[n].polaczenia[i]<<endl;
        }
  }   
}
 
int main()
{
  cout<<"Podaj liczbę wierzchołków w grafie: ";
  int n, p, a, b;
  cin>>n;
  w = new graf [n+1];//przydzielenie pamięci na wierzchołki grafu
  //wczytanie wierzchołków grafu
  cout<<"Podaj liczbę połączeń: ";
  cin>>p;
 
  for(int i=0;i<p;i++)
  {
    cout<<"Podaj numery wierzchołków, które chcesz ze sobą połączyć: ";
    cin>>a>>b;
    w[a].polaczenia.push_back(b); //połączenie jest dwukierunkowe a-->b
    w[b].polaczenia.push_back(a); //b-->a
  }
  //przeszukaj graf
  DFS(1); //rozpoczynamy od wierzchołka o numerze 1
 
  delete [] w;
  return 0;
}

Przykładowe zadania, wykorzystujące powyższy algorytm:

Zadanie 1. Znajdź wyjście z labiryntu.

Dane wejściowe:

Ciąg znaków X lub O umieszczony w kwadratowej macierzy 10x10, gdzie O oznacza przejście, natomiast X mur labiryntu.

Dane wyjściowe

Należy napisać tak, jeśli jest możliwe przejście z komórki (0, 0) do komórki (9, 9).

Przykład

Wejście

OOOXXOOXXX
XOXXXXXOOO
XOOOOOOOXO
XXXXXXXXXO
XXXOOOOOOO
XXXOXXXXOX
XOOOOOOOOX
XXXOXOXXOX
OOOOXOOOOX
XXXXXXXXOO

Wyjście

Tak