Recherche en profondeur d'abord (DFS)

La recherche en profondeur d'un graphique commence à partir d'un sommet du graphique et visite tous les sommets du graphique autant que possible avant de revenir en arrière.
La recherche en profondeur d'un graphique est comme la recherche en profondeur d'un arbre discutée dans Tree Traversal, Tree Traversal. Dans le cas d'un arbre, la recherche part de la racine. Dans un graphique, la recherche peut commencer à partir de n'importe quel sommet.

Une recherche en profondeur d'un arbre visite d'abord la racine, puis visite récursivement les sous-arbres de la racine. De même, la recherche en profondeur d’un graphe visite d’abord un sommet, puis de manière récursive tous les sommets adjacents à ce sommet. La différence est que le graphique peut contenir des cycles, ce qui pourrait conduire à une récursion infinie. Pour éviter ce problème, vous devez suivre les sommets déjà visités.

La recherche est appelée profondeur d'abord car elle recherche « plus profondément » dans le graphique autant que possible. La recherche commence à partir d'un sommet v. Après avoir visité v, il visite un voisin non visité de v. Si v n'a pas de voisin non visité, la recherche revient au sommet à partir duquel il a atteint v. Nous supposons que le graphe est connecté et que la recherche commence de n'importe quel sommet peut atteindre tous les sommets.

Algorithme de recherche en profondeur

L'algorithme de recherche en profondeur d'abord est décrit dans le code ci-dessous.

Entrée : G = (V, E) et un sommet de départ v
Sortie : un arbre DFS enraciné à v
1 Arbre dfs (sommet v) {
2 visite v;
3 pour chaque voisin w de v
4 si (w n'a pas été visité) {
5 définir v comme parent de w dans l'arbre ;
6 dfs(w);
7>
8>

Vous pouvez utiliser un tableau nommé isVisited pour indiquer si un sommet a été visité. Initialement, isVisited[i] est false pour chaque sommet i. Une fois qu'un sommet, disons v, est visité, isVisited[v] est défini sur true.

Considérez le graphique de la figure ci-dessous (a). Supposons que nous commencions la recherche en profondeur à partir du sommet 0. Visitez d’abord 0, puis l’un de ses voisins, disons 1. Maintenant, 1 est visité, comme le montre la figure ci-dessous (b). Le sommet 1 a trois voisins : 0, 2 et 4. Puisque 0 a déjà été visité, vous visiterez soit 2, soit 4. Choisissons 2. Maintenant, 2 est visité, comme le montre la figure ci-dessous (c). Le sommet 2 a trois voisins : 0, 1 et 3. Puisque 0 et 1 ont déjà été visités, le choix 3. 3 est maintenant visité, comme le montre la figure ci-dessous (d). À ce stade, les sommets ont été visités dans cet ordre :

0, 1, 2, 3

Puisque tous les voisins de 3 ont été visités, revenez à 2. Puisque tous les sommets de 2 ont été visités, revenez à 1. 4 est adjacent à 1, mais 4 n'a pas été visité. Par conséquent, visitez 4, comme le montre la figure ci-dessous (e). Puisque tous les voisins de 4 ont été visités, revenez à 1.
Puisque tous les voisins de 1 ont été visités, revenez à 0. Puisque tous les voisins de 0 ont été visités, la recherche se termine.

Comme chaque arête et chaque sommet n'est visité qu'une seule fois, la complexité temporelle de la méthode dfs est O(|E| + |V|), où | E| désigne le nombre d'arêtes et |V| le nombre de sommets.

Mise en œuvre de la recherche en profondeur

L'algorithme pour DFS dans le code ci-dessus utilise la récursivité. Il est naturel d'utiliser la récursivité pour l'implémenter. Alternativement, vous pouvez utiliser une pile.

La méthode dfs(int v) est implémentée aux lignes 164 à 193 dans AbstractGraph.java. Il renvoie une instance de la classe Tree avec le sommet v comme racine. La méthode stocke les sommets recherchés dans la liste searchOrder (ligne 165), le parent de chaque sommet dans le tableau parent (ligne 166), et utilise le isVisited tableau pour indiquer si un sommet a été visité (ligne 171). Il invoque la méthode d'assistance dfs(v, parent, searchOrder, isVisited) pour effectuer une recherche en profondeur d'abord (ligne 174).

Dans la méthode d'assistance récursive, la recherche commence à partir du sommet u. u est ajouté à searchOrder à la ligne 184 et est marqué comme visité (ligne 185). Pour chaque voisin non visité de u, la méthode est invoquée de manière récursive pour effectuer une recherche en profondeur d'abord. Lorsqu'un sommet e.v est visité, le parent de e.v est stocké dans parent[e.v] (ligne 189). La méthode est renvoyée lorsque tous les sommets sont visités pour un graphe connecté ou dans un composant connecté.

Le code ci-dessous donne un programme de test qui affiche un DFS pour le graphique de la figure ci-dessus à partir de Chicago. L'illustration graphique du DFS à partir de Chicago est présentée dans la figure ci-dessous.

public class TestDFS {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5},
                {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7},
                {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11},
                {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        Graph<String> graph = new UnweightedGraph<>(vertices, edges);
        AbstractGraph<String>.Tree dfs = graph.dfs(graph.getIndex("Chicago"));

        java.util.List<Integer> searchOrders = dfs.getSearchOrder();
        System.out.println(dfs.getNumberOfVerticesFound() + " vertices are searched in this DFS order:");
        for(int i = 0; i < searchOrders.size(); i++)
            System.out.print(graph.getVertex(searchOrders.get(i)) + " ");
        System.out.println();

        for(int i = 0; i < searchOrders.size(); i++)
            if(dfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(dfs.getParent(i)));
    }

}

12 sommets sont recherchés dans cet ordre DFS :
Chicago Seattle San Francisco Los Angeles Denver
Kansas City New York Boston Atlanta Miami Houston Dallas
Le parent de Seattle est Chicago
Le parent de San Francisco est Seattle
Le parent de Los Angeles est San Francisco
Le parent de Denver est Los Angeles
Le parent de Kansas City est Denver
le parent de Boston est New York
Le parent de New York est Kansas City
Le parent d'Atlanta est New York
Le parent de Miami est Atlanta
le parent de Dallas est Houston
Le parent de Houston est Miami

Applications du DFS

La recherche en profondeur peut être utilisée pour résoudre de nombreux problèmes, tels que les suivants :

• Détecter si un graphique est connecté. Recherchez le graphique à partir de n’importe quel sommet. Si le nombre de sommets recherchés est le même que le nombre de sommets dans le graphe, le graphe est connecté. Sinon, le graphique n'est pas connecté.
• Détecter s'il existe un chemin entre deux sommets.
• Trouver un chemin entre deux sommets.
• Trouver tous les composants connectés. Un composant connexe est un sous-graphe connexe maximal dans lequel chaque paire de sommets est reliée par un chemin.
• Détecter s'il y a un cycle dans le graphique.
• Trouver un cycle dans le graphique.
• Trouver un chemin/cycle hamiltonien. Un Chemin hamiltonien dans un graphe est un chemin qui visite chaque sommet du graphe exactement une fois. Un cycle hamiltonien visite chaque sommet du graphique exactement une fois et revient au sommet de départ.

Les six premiers problèmes peuvent être facilement résolus en utilisant la méthode dfs dans AbstractGraph.java. Pour trouver un chemin/cycle hamiltonien, vous devez explorer tous les DFS possibles pour trouver celui qui mène au chemin le plus long. Le chemin/cycle hamiltonien a de nombreuses applications, notamment pour résoudre le problème bien connu du Knight’s Tour.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!