Algoritmo della settimana: Graph ricerca depth-first

Introduzione

Insieme con ricerca breadth-first , ricerca depth-first è uno dei due metodi principali per camminare attraverso un grafico. Questo approccio è però diverso. In ampiezza (BFS) assomiglia molto partendo da un vertice e l'espansione del livello di processo di ricerca per livello. Questo significa che prima si ottiene qualche informazione di tutti i successori del nodo dato e poi proseguire con il livello successivo. In altre parole, BFS è come un'onda. Ricerca in profondità è basato su un approccio diverso, che può essere molto utile in alcuni algoritmi specifici.

Ricerca in profondità e in ampiezza sono i due modi principali per esplorare un grafico!

Entrambi i metodi possono essere utili nel risolvere diversi compiti.

Panoramica

Ricerca in profondità è un algoritmo che, dato il nodo di partenza e di destinazione, trova un percorso tra di loro. Possiamo anche utilizzare DFS camminare attraverso tutti i vertici di un grafo, nel caso il grafico è collegato.

L'algoritmo va prima in profondità e poi marcia indietro a tutti i successori non visitati!

L'idea di questo algoritmo è di andare il più possibile dal nodo dato inizio alla ricerca del bersaglio. Nel caso in cui si arriva a un nodo che non ha successori, torniamo (in genere questo viene fatto in modo ricorsivo) e proseguiamo con l'ultimo vertice che non è ancora visitato.

Quindi, in pratica ci sono 3 passi:

1. Prendete un vertice che non è visitato ancora e segnare visitato;
2. Vai al suo primo successore non visitati e segnare visitato;
3. Se tutti i successori del vertice sono già visitato o non ha successori - tornare al suo genitore;

Codice

Il seguente PHP codice implementa la ricerca in profondità. Il punto chiave è la ricorsione nel depthFirst metodo.

01.classe Graph

02.{

03.protetto $ _len = 0;

04.protetto $ _g = matrice ();

05.protetto $ _visited = matrice ();

06. 

07.pubblica funzione __construct ()

08.{

09.$ this -> _g = matrice (

10.matrice (0, 1, 1, 0, 0, 0),

11.matrice (1, 0, 0, 1, 0, 0),

12.matrice (1, 0, 0, 1, 1, 1),

13.matrice (0, 1, 1, 0, 1, 0),

14.matrice (0, 0, 1, 1, 0, 1),

15.matrice (0, 0, 1, 0, 1, 0),

16.);

17. 

18.$ this -> _len = count ( $ this -> _g);

19. 

20.$ this -> _initVisited ();

21.}

22. 

23.protetto funzione _initVisited ()

24.{

25.per ( $ i = 0; $ i < $ this -> _len; $ i + +) {

26.$ this -> _visited [ $ i ] = 0;

27.}

28.}

29. 

30.pubblica funzione depthFirst ( $ vertice )

31.{

32.$ this -> _visited [ $ vertice ] = 1;

33. 

34.echo $ vertice . "\ n" ;

35. 

36.per ( $ i = 0; $ i < $ this -> _len; $ i + +) {

37.se ( $ this -> _g [ $ vertice ] [ $ i ] == 1 &&! $ this -> _visited [ $ i ]) {

38.$ this -> depthFirst ( $ i );

39.}

40.}

41.}

42.}

43. 

44.$ g = nuovo grafico ();

45./ / 2 0 1 3 4 5

46.​​$ g -> depthFirst (2);

Complessità

Utilizzando una matrice di adiacenza abbiamo bisogno di spazio n2 per un grafo con n vertici. Inoltre, utilizziamo un array aggiuntivo per segnare vertici visitati, il che richiede ulteriore spazio di n ! Così la complessità spazio è O (n2).

Quando si tratta di complessità temporale dal momento che abbiamo una ricorsione e ci prova a visitare tutti i vertici ad ogni passo, nel caso peggiore, il tempo è ancora una volta O (n2)!

Applicazione

Questo grafico a piedi algoritmo può essere molto utile per la risoluzione di alcuni compiti specifici come trovare i percorsi più brevi / più lungo in un grafico. Sebbene BFS e DFS non sono gli unici metodi di camminare attraverso un grafico, sono considerati i due principali algoritmi di questo tipo. Questo è importante per risolvere il grafico basati problemi.

Corso Java - Corsi Java - Corsi programmazione Java

 Corso programmazione Android - Certificazione Android