Algoritmo DFS (Depth First Search)

Sommario

Profondità primo algoritmo di ricerca
Profondità prima ricerca esempio
Pseudocodice DFS (implementazione ricorsiva)
Implementazione di DFS in Python, Java e C / C ++
Complessità della ricerca in profondità
Applicazione dell'algoritmo DFS

In questo tutorial imparerai a conoscere l'algoritmo di ricerca in profondità con esempi e pseudocodice. Inoltre, imparerai a implementare DFS in C, Java, Python e C ++.

Depth first Search o Depth first traversal è un algoritmo ricorsivo per la ricerca in tutti i vertici di un grafo o di una struttura dati ad albero. Traversal significa visitare tutti i nodi di un grafo.

Profondità primo algoritmo di ricerca

Un'implementazione DFS standard inserisce ogni vertice del grafico in una delle due categorie:

Visitato
Non visitato

Lo scopo dell'algoritmo è contrassegnare ogni vertice come visitato evitando i cicli.

L'algoritmo DFS funziona come segue:

Inizia mettendo uno qualsiasi dei vertici del grafico in cima a una pila.
Prendi l'elemento in cima alla pila e aggiungilo all'elenco dei visitati.
Crea un elenco dei nodi adiacenti di quel vertice. Aggiungi quelli che non sono nell'elenco dei visitati in cima alla pila.
Continua a ripetere i passaggi 2 e 3 finché lo stack non è vuoto.

Profondità prima ricerca esempio

Vediamo come funziona l'algoritmo di Depth First Search con un esempio. Usiamo un grafo non orientato con 5 vertici.

Grafo non orientato con 5 vertici

Partiamo dal vertice 0, l'algoritmo DFS inizia mettendolo nella lista Visitate e mettendo tutti i suoi vertici adiacenti nello stack.

Visita l'elemento e inseriscilo nell'elenco dei visitati

Successivamente, visitiamo l'elemento in cima allo stack, cioè 1 e andiamo ai suoi nodi adiacenti. Poiché 0 è già stato visitato, visitiamo invece 2.

Visita l'elemento in cima alla pila

Il vertice 2 ha un vertice adiacente non visitato in 4, quindi lo aggiungiamo in cima alla pila e lo visitiamo.

Dopo aver visitato l'ultimo elemento 3, non ha nodi adiacenti non visitati, quindi abbiamo completato il Depth First Traversal del grafico.

Pseudocodice DFS (implementazione ricorsiva)

Lo pseudocodice per DFS è mostrato di seguito. Nella funzione init (), notare che eseguiamo la funzione DFS su ogni nodo. Questo perché il grafico potrebbe avere due diverse parti disconnesse, quindi per assicurarci di coprire ogni vertice, possiamo anche eseguire l'algoritmo DFS su ogni nodo.

 DFS (G, u) u.visited = true per ogni v ∈ G.Adj (u) if v.visited == false DFS (G, v) init () (Per ogni u ∈ G u.visited = false For each u ∈ G DFS (G, u))

Implementazione di DFS in Python, Java e C / C ++

Di seguito è mostrato il codice per l'algoritmo di ricerca in profondità prima con un esempio. Il codice è stato semplificato in modo che possiamo concentrarci sull'algoritmo piuttosto che su altri dettagli.

Python Java C C +

 # DFS algorithm in Python # DFS algorithm def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for next in graph(start) - visited: dfs(graph, next, visited) return visited graph = ('0': set(('1', '2')), '1': set(('0', '3', '4')), '2': set(('0')), '3': set(('1')), '4': set(('2', '3'))) dfs(graph, '0')

 // DFS algorithm in Java import java.util.*; class Graph ( private LinkedList adjLists(); private boolean visited(); // Graph creation Graph(int vertices) ( adjLists = new LinkedList(vertices); visited = new boolean(vertices); for (int i = 0; i < vertices; i++) adjLists(i) = new LinkedList(); ) // Add edges void addEdge(int src, int dest) ( adjLists(src).add(dest); ) // DFS algorithm void DFS(int vertex) ( visited(vertex) = true; System.out.print(vertex + " "); Iterator ite = adjLists(vertex).listIterator(); while (ite.hasNext()) ( int adj = ite.next(); if (!visited(adj)) DFS(adj); ) ) public static void main(String args()) ( Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); System.out.println("Following is Depth First Traversal"); g.DFS(2); ) )

 // DFS algorithm in C #include #include struct node ( int vertex; struct node* next; ); struct node* createNode(int v); struct Graph ( int numVertices; int* visited; // We need int** to store a two dimensional array. // Similary, we need struct node** to store an array of Linked lists struct node** adjLists; ); // DFS algo void DFS(struct Graph* graph, int vertex) ( struct node* adjList = graph->adjLists(vertex); struct node* temp = adjList; graph->visited(vertex) = 1; printf("Visited %d ", vertex); while (temp != NULL) ( int connectedVertex = temp->vertex; if (graph->visited(connectedVertex) == 0) ( DFS(graph, connectedVertex); ) temp = temp->next; ) ) // Create a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Create graph struct Graph* createGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i adjLists(i) = NULL; graph->visited(i) = 0; ) return graph; ) // Add edge void addEdge(struct Graph* graph, int src, int dest) ( // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists(src); graph->adjLists(src) = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists(dest); graph->adjLists(dest) = newNode; ) // Print the graph void printGraph(struct Graph* graph) ( int v; for (v = 0; v numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Adjacency list of vertex %d ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) int main() ( struct Graph* graph = createGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 2, 3); printGraph(graph); DFS(graph, 2); return 0; )

 // DFS algorithm in C++ #include #include using namespace std; class Graph ( int numVertices; list *adjLists; bool *visited; public: Graph(int V); void addEdge(int src, int dest); void DFS(int vertex); ); // Initialize graph Graph::Graph(int vertices) ( numVertices = vertices; adjLists = new list(vertices); visited = new bool(vertices); ) // Add edges void Graph::addEdge(int src, int dest) ( adjLists(src).push_front(dest); ) // DFS algorithm void Graph::DFS(int vertex) ( visited(vertex) = true; list adjList = adjLists(vertex); cout << vertex << " "; list::iterator i; for (i = adjList.begin(); i != adjList.end(); ++i) if (!visited(*i)) DFS(*i); ) int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); g.DFS(2); return 0; )