Algorithme de recherche en profondeur (DFS)

Dans ce didacticiel, vous découvrirez l'algorithme de recherche en profondeur avec des exemples et un pseudocode. De plus, vous apprendrez à implémenter DFS en C, Java, Python et C ++.

La première recherche en profondeur ou la première traversée en profondeur est un algorithme récursif pour rechercher tous les sommets d'un graphe ou d'une arborescence de données. Traverser signifie visiter tous les nœuds d'un graphe.

Algorithme de recherche en profondeur d'abord

Une implémentation DFS standard place chaque sommet du graphe dans l'une des deux catégories suivantes:

  1. A visité
  2. Non visité

Le but de l'algorithme est de marquer chaque sommet comme visité tout en évitant les cycles.

L'algorithme DFS fonctionne comme suit:

  1. Commencez par placer l'un des sommets du graphe au-dessus d'une pile.
  2. Prenez l'élément supérieur de la pile et ajoutez-le à la liste visitée.
  3. Créez une liste des nœuds adjacents de ce sommet. Ajoutez ceux qui ne sont pas dans la liste visitée en haut de la pile.
  4. Répétez les étapes 2 et 3 jusqu'à ce que la pile soit vide.

Exemple de recherche en profondeur d'abord

Voyons comment fonctionne l'algorithme Depth First Search avec un exemple. Nous utilisons un graphe non orienté avec 5 sommets.

Graphique non orienté avec 5 sommets

Nous partons du sommet 0, l'algorithme DFS commence par le mettre dans la liste Visited et mettre tous ses sommets adjacents dans la pile.

Visitez l'élément et mettez-le dans la liste visitée

Ensuite, nous visitons l'élément en haut de la pile soit 1 et allons à ses nœuds adjacents. Puisque 0 a déjà été visité, nous en visitons 2 à la place.

Visitez l'élément en haut de la pile

Vertex 2 a un sommet adjacent non visité dans 4, nous l'ajoutons donc au sommet de la pile et le visitons.

Vertex 2 a un sommet adjacent non visité dans 4, nous l'ajoutons donc au sommet de la pile et le visitons. Vertex 2 a un sommet adjacent non visité dans 4, nous l'ajoutons donc au sommet de la pile et le visitons.

Après avoir visité le dernier élément 3, il n'a pas de nœuds adjacents non visités, nous avons donc terminé la première traversée en profondeur du graphique.

Après avoir visité le dernier élément 3, il n'a pas de nœuds adjacents non visités, nous avons donc terminé la première traversée en profondeur du graphique.

Pseudocode DFS (implémentation récursive)

Le pseudocode pour DFS est indiqué ci-dessous. Dans la fonction init (), notez que nous exécutons la fonction DFS sur chaque nœud. En effet, le graphique peut avoir deux parties déconnectées différentes, donc pour nous assurer que nous couvrons chaque sommet, nous pouvons également exécuter l'algorithme DFS sur chaque nœud.

 DFS (G, u) u.visited = true pour chaque v ∈ G.Adj (u) if v.visited == false DFS (G, v) init () (Pour chaque u ∈ G u.visited = false Pour chaque u ∈ G DFS (G, u))

Implémentation DFS en Python, Java et C / C ++

Le code de l'algorithme de recherche en profondeur d'abord avec un exemple est illustré ci-dessous. Le code a été simplifié afin que nous puissions nous concentrer sur l'algorithme plutôt que sur d'autres détails.

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; )

Complexité de la première recherche en profondeur

La complexité temporelle de l'algorithme DFS est représentée sous la forme de O(V + E), où Vest le nombre de nœuds et Ele nombre d'arêtes.

La complexité spatiale de l'algorithme est O(V).

Application de l'algorithme DFS

  1. Pour trouver le chemin
  2. Pour tester si le graphique est biparti
  3. Pour trouver les composants fortement connectés d'un graphe
  4. Pour détecter les cycles dans un graphique

Articles intéressants...