Comment utiliser les algorithmes de recherche de graphiques en C++

Comment utiliser l'algorithme de recherche de graphiques en C++

L'algorithme de recherche de graphiques est un algorithme couramment utilisé pour trouver des chemins dans des structures de graphiques, traverser des nœuds ou résoudre d'autres problèmes liés aux graphiques. En C++, il existe de nombreuses implémentations d'algorithmes de recherche de graphes, tels que la recherche en profondeur d'abord (DFS), la recherche en largeur d'abord (BFS), l'algorithme de Dijkstra, l'algorithme A*, etc. Dans cet article, nous présenterons comment utiliser les algorithmes de recherche de graphiques en C++ et donnerons des exemples de code spécifiques.

1. Depth First Search (DFS)

Depth First Search est un algorithme de recherche de graphe classique. Son idée de base est de parcourir profondément les nœuds du graphe jusqu'à ce que le nœud cible soit trouvé ou que le graphe entier soit parcouru. Voici un exemple de code pour implémenter DFS en utilisant C++ :

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 定义图的节点数据结构
struct Node {
    int val;
    vector<Node*> neighbors;
    bool visited;
    
    Node(int x) : val(x), visited(false) {} // 初始化节点
};

// 深度优先搜索函数
void dfs(Node* node) {
    stack<Node*> stk;
    stk.push(node);
    
    while (!stk.empty()) {
        Node* cur = stk.top();
        stk.pop();
        
        if (cur->visited) {
            continue;
        }
        
        cur->visited = true;
        
        // 对当前节点进行操作
        cout << cur->val << " ";
        
        // 遍历当前节点的邻居节点
        for (Node* neighbor : cur->neighbors) {
            if (!neighbor->visited) {
                stk.push(neighbor);
            }
        }
    }
}

int main() {
    // 构造图
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    node1->neighbors.push_back(node2);
    node1->neighbors.push_back(node4);
    node2->neighbors.push_back(node1);
    node2->neighbors.push_back(node3);
    node3->neighbors.push_back(node2);
    node3->neighbors.push_back(node4);
    node4->neighbors.push_back(node1);
    node4->neighbors.push_back(node3);
    
    // 调用深度优先搜索函数
    dfs(node1);

    return 0;
}

Dans le code ci-dessus, nous définissons d'abord la structure de données de nœud du graphe, chaque nœud contient une valeur (val) et une liste de nœuds voisins (neighbours). Ensuite, nous définissons une pile (stk) pour sauvegarder les nœuds à visiter. Dans la fonction DFS, nous plaçons d'abord le nœud de départ dans la pile, puis commençons à accéder aux nœuds de manière itérative. Pour chaque nœud, nous le marquons comme visité et agissons dessus (dans ce cas, nous affichons simplement la valeur du nœud). Ensuite, nous parcourons les nœuds voisins du nœud actuel et ajoutons les nœuds voisins non visités à la pile. De cette façon, nous pouvons accéder à l’intégralité du graphique en profondeur.

2. Breadth First Search (BFS)

Breadth First Search est un autre algorithme de recherche de graphes couramment utilisé. Son idée de base est de parcourir les nœuds du graphique couche par couche jusqu'à ce que le nœud cible soit trouvé ou que l'intégralité du graphique soit parcourue. Voici un exemple de code pour implémenter BFS en utilisant C++ :

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 定义图的节点数据结构
struct Node {
    int val;
    vector<Node*> neighbors;
    bool visited;
    
    Node(int x) : val(x), visited(false) {} // 初始化节点
};

// 广度优先搜索函数
void bfs(Node* node) {
    queue<Node*> q;
    q.push(node);
    
    while (!q.empty()) {
        Node* cur = q.front();
        q.pop();
        
        if (cur->visited) {
            continue;
        }
        
        cur->visited = true;
        
        // 对当前节点进行操作
        cout << cur->val << " ";
        
        // 遍历当前节点的邻居节点
        for (Node* neighbor : cur->neighbors) {
            if (!neighbor->visited) {
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // 构造图
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    node1->neighbors.push_back(node2);
    node1->neighbors.push_back(node4);
    node2->neighbors.push_back(node1);
    node2->neighbors.push_back(node3);
    node3->neighbors.push_back(node2);
    node3->neighbors.push_back(node4);
    node4->neighbors.push_back(node1);
    node4->neighbors.push_back(node3);
    
    // 调用广度优先搜索函数
    bfs(node1);

    return 0;
}

Dans le code ci-dessus, nous utilisons la file d'attente (q) pour enregistrer les nœuds à visiter. Dans la fonction BFS, nous mettons d'abord le nœud de départ dans la file d'attente, puis commençons à accéder aux nœuds de manière itérative. Pour chaque nœud, nous le marquons comme visité et agissons dessus (dans ce cas, nous affichons simplement la valeur du nœud). Ensuite, nous parcourons les nœuds voisins du nœud actuel et ajoutons les nœuds voisins non visités à la file d'attente. De cette façon, nous pouvons accéder à l’intégralité du graphique en largeur.

3. Implémentation d'autres algorithmes de recherche de graphiques

En plus de la recherche en profondeur et en largeur, C++ fournit également des implémentations de nombreux autres algorithmes de recherche de graphiques, tels que l'algorithme de Dijkstra et l'algorithme A*. La mise en œuvre de ces algorithmes est légèrement plus complexe et ne peut être présentée dans cet article. Cependant, vous pouvez trouver des implémentations de ces algorithmes dans la bibliothèque standard C++ ou utiliser des bibliothèques tierces pour les implémenter. En utilisant ces algorithmes, vous pouvez résoudre des problèmes graphiques plus complexes, tels que le chemin le plus court, la distance la plus courte, etc.

En résumé, cet article présente comment utiliser l'algorithme de recherche graphique en C++ et donne des exemples de code spécifiques de recherche en profondeur d'abord et de recherche en largeur d'abord. J'espère que cet article pourra vous aider à comprendre et à appliquer des algorithmes de recherche de graphiques.

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!