Application des fonctions récursives C++ dans les structures de données graphiques ?

Les fonctions récursives C++ sont largement utilisées dans les structures de données graphiques, en particulier dans les algorithmes tels que la recherche en profondeur d'abord (DFS). L'algorithme DFS parcourt un graphe en explorant de manière récursive les voisins d'un nœud et peut être utilisé pour trouver des chemins, des composants connectés et des cycles. La fonction C++ suivante implémente l'algorithme DFS : DFS(graph, node) {}, où graph est le graphique et node est le nœud actuel. Cette fonction marque le nœud actuel comme visité et parcourt de manière récursive tous les nœuds adjacents non visités.

Application C++ de fonctions récursives dans les structures de données graphiques

Les fonctions récursives sont largement utilisées dans les structures de données graphiques, en particulier dans les algorithmes de parcours et de recherche de graphiques. Cet article décrit comment utiliser les fonctions récursives C++ pour effectuer une recherche en profondeur (DFS) sur un graphique.

Depth First Search (DFS)

L'algorithme DFS parcourt le graphique en explorant de manière récursive tous les nœuds adjacents inexplorés de chaque nœud. Cet algorithme peut être utilisé pour trouver des chemins, des composants connectés et des cycles dans des graphiques.

Fonction DFS récursive C++

La fonction C++ suivante implémente l'algorithme DFS :

void DFS(Graph& graph, int node) {
  // 标记给定节点已访问
  graph.visit(node);

  // 递归遍历所有未访问的邻接节点
  for (auto adjacent_node : graph.get_adjacent_nodes(node)) {
    if (!graph.is_visited(adjacent_node)) {
      DFS(graph, adjacent_node);
    }
  }
}

Exemple pratique

Considérez le graphe non orienté suivant :

1 -- 2
| /  |
3 -- 4

Pour effectuer DFS sur ce graphe, nous devons partir d'un nœud puis visiter il récursivement Tous ses nœuds adjacents non visités :

Graph graph;
// 添加节点和边
graph.add_edge(1, 2);
graph.add_edge(1, 3);
graph.add_edge(2, 4);
graph.add_edge(3, 4);

// 从节点 1 开始 DFS
DFS(graph, 1);

DFS imprimera la séquence d'accès suivante : 1, 2, 4, 3

Conclusion

Les fonctions récursives fournissent un moyen concis et puissant d'implémenter diverses traversées et algorithmes de recherche. Cet article décrit comment utiliser les fonctions récursives C++ pour exécuter DFS et fournit un cas pratique pour illustrer son application.

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!