Penggunaan fungsi rekursif C++ dalam algoritma carian?

Fungsi rekursif digunakan dalam algoritma carian untuk meneroka struktur data seperti pokok. Carian pertama mendalam menggunakan timbunan untuk meneroka nod, manakala carian pertama keluasan menggunakan baris gilir untuk melintasi lapisan demi lapisan. Dalam aplikasi praktikal, seperti mencari fail, fungsi rekursif boleh digunakan untuk mencari fail tertentu dalam direktori tertentu.

Aplikasi fungsi rekursif C++ dalam algoritma carian

Fungsi rekursif ialah fungsi khas yang memanggil dirinya di dalam fungsi. Pendekatan ini amat berguna apabila menyelesaikan masalah dengan struktur data seperti pepohon seperti mencari dan melintasi.

Depth First Search (DFS)

Depth First Search algorithm (DFS) menggunakan tindanan untuk menerokai nod, mencari secara mendalam melalui semua kemungkinan cawangan nod, dan kemudian menjejak kembali ke nod sebelumnya bagi nod untuk meneruskan penerokaan .Ranting sehingga seluruh pokok dilalui.

// 执行深度优先搜索
void DFS(Node* node) {
  // 访问当前节点
  Visit(node);

  // 递归遍历所有子节点
  for (Node* child : node->children) {
    DFS(child);
  }
}

Breadth First Search (BFS)

Breadth first search algorithm (BFS) menggunakan baris gilir untuk meneroka nod dan melintasi pepohon dalam susunan hierarki. Ia menambah semua nod dalam lapisan semasa ke baris gilir dan kemudian mengakses nod ini dalam urutan. Selepas melawat semua nod anak nod, teruskan ke peringkat seterusnya.

// 执行广度优先搜索
void BFS(Node* root) {
  // 创建队列并添加根节点
  Queue<Node*> queue;
  queue.push(root);

  // 当队列不为空时，继续遍历
  while (!queue.empty()) {
    // 取出队首节点
    Node* node = queue.front();
    queue.pop();

    // 访问当前节点
    Visit(node);

    // 将子节点添加至队列
    for (Node* child : node->children) {
      queue.push(child);
    }
  }
}

Kes Praktikal: Cari Fail

Andaikan terdapat sistem fail di mana setiap fail atau direktori boleh mengandungi sub-fail dan sub-direktori. Kita boleh menggunakan fungsi rekursif untuk mencari fail tertentu.

rreeee

Atas ialah kandungan terperinci Penggunaan fungsi rekursif C++ dalam algoritma carian?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!