Penggunaan fungsi rekursif C++ dalam struktur data graf?

Fungsi rekursif C++ digunakan secara meluas dalam struktur data graf, terutamanya dalam algoritma seperti carian depth-first (DFS). Algoritma DFS merentasi graf dengan meneroka jiran nod secara rekursif dan boleh digunakan untuk mencari laluan, komponen bersambung dan kitaran. Fungsi C++ berikut melaksanakan algoritma DFS: DFS(graf, nod) {}, dengan graf ialah graf dan nod ialah nod semasa. Fungsi ini menandakan nod semasa sebagai dilawati dan secara rekursif melintasi semua nod bersebelahan yang tidak dilawati.

C++ Aplikasi fungsi rekursif dalam struktur data graf

Fungsi rekursif digunakan secara meluas dalam struktur data graf, terutamanya dalam traversal graf dan algoritma carian. Artikel ini menerangkan cara menggunakan fungsi rekursif C++ untuk melakukan carian pertama mendalam (DFS) pada graf.

Depth First Search (DFS)

Algoritma DFS merentasi graf dengan meneroka secara rekursif semua nod bersebelahan yang belum diterokai bagi setiap nod. Algoritma ini boleh digunakan untuk mencari laluan, komponen yang disambungkan dan kitaran dalam graf.

Fungsi DFS Rekursif C++

Fungsi C++ berikut melaksanakan algoritma 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);
    }
  }
}

Contoh Praktikal

Pertimbangkan graf tidak terarah berikut:

1 -- 2
| /  |
3 -- 4

Untuk melaksanakan DFS pada graf ini, kita tidak perlu memulakan graf ini dan kemudiannya ia secara rekursif Semua nod bersebelahan yang tidak dilawati:

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 akan mencetak urutan akses berikut: 1, 2, 4, 3

Kesimpulan

Fungsi rekursif menyediakan cara ringkas dan berkuasa untuk melaksanakan pelbagai traversal dan algoritma Carian. Artikel ini menerangkan cara menggunakan fungsi rekursif C++ untuk melaksanakan DFS dan menyediakan kes praktikal untuk menggambarkan penggunaannya.

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