Jumlah semua pasangan laluan terpendek dalam pokok itu

Dalam pokok, istilah "jumlah laluan terpendek ke atas semua pasangan nod" merujuk kepada pengiraan jumlah laluan terpendek individu untuk semua pasangan nod. Kaedah yang berkesan ialah menggunakan algoritma dwi DFS (depth first search). Jarak antara nod yang dipilih dan setiap nod lain ditentukan semasa pas DFS pertama. Pokok itu dilalui semula semasa pas DFS kedua, dengan mengambil kira setiap nod sebagai potensi LCA (nenek moyang paling rendah) dan mengira jumlah jarak antara pasangan nod keturunan LCA yang dipilih. Menggunakan kaedah ini, anda boleh mengira jumlah laluan terpendek untuk semua pasangan nod dalam pokok dan memastikan penyelesaian yang ideal

Kaedah penggunaan

• Kaedah DFS Berganda (depth first search).

• Kaedah pengaturcaraan dinamik

Kaedah Double DFS (Depth First Search)

Untuk jumlah semua pasangan laluan terpendek dalam pepohon, kami menggunakan kaedah DFS (carian pertama mendalam) dwi, ​​yang melibatkan dua pas DFS. Pertama, kita mengira jarak dari mana-mana nod ke semua nod lain. Kemudian, semasa traversal DFS kedua, kami menavigasi pepohon sambil mempertimbangkan setiap nod sebagai LCA yang berpotensi. Kami mengira dan menjumlahkan jarak antara pasangan nod yang merupakan keturunan LCA yang dipilih semasa melintasi. Dengan mengulangi proses ini untuk semua nod, kami memperoleh jumlah semua pasangan laluan terpendek. Strategi ini sangat menarik untuk masalah ini kerana ia secara berkesan mengira jumlah jarak antara semua set nod dalam pepohon.

Algoritma

• Sebarang nod dalam pokok boleh digunakan sebagai nod permulaan

• Untuk menentukan jarak dari nod permulaan yang dipilih ke semua nod lain, lakukan carian pertama mendalam (DFS) bermula dari nod itu. Jarak ini harus disimpan dalam tatasusunan atau struktur data.

• Seterusnya, jalankan carian mendalam-pertama (DFS) kedua pada pepohon, mempertimbangkan setiap nod sebagai kemungkinan nenek moyang sepunya terdekat (LCA)

• Semasa melintasi pokok semasa DFS kedua, hitung jarak antara pasangan nod yang merupakan keturunan LCA yang dipilih. Untuk setiap LCA, jarak ini ditambah bersama.

• Ulang proses ini untuk setiap nod dalam pokok

• Jumlah semua padanan dengan cara yang paling terhingga dalam pokok diwakili oleh jumlah semua jarak yang dikira dalam langkah 4.

Contoh

Contoh

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 10005;
vector<int> graph[MAXN];
int ancestor[MAXN];

int dfs(int node, int lca, int distance) {
   int sum = 0;
   for (int neighbor : graph[node]) {
      if (neighbor != lca) {
         sum += dfs(neighbor, lca, distance + 1);
      }
   }
   return sum + distance;
}

int main() {

   int lca_node = 0;
   int total_sum = 0;

   for (int node = 0; node < MAXN; ++node) {
      if (node != lca_node) {
         total_sum += dfs(node, lca_node, 0);
      }
   }

   cout << "Total sum of distances between descendants of the LCA: " << total_sum << endl;

   return 0;
}

Output

Total sum of distances between descendants of the LCA: 0

Kaedah pengaturcaraan dinamik:

Kami mula-mula memilih mana-mana nod sebagai nod akar dan menukar pepohon kepada pepohon berakar dalam kaedah pengaturcaraan dinamik, yang digunakan untuk mengira jumlah laluan terpendek antara semua nod dalam pepohon. Kami menggunakan pengaturcaraan dinamik untuk mengira pemisahan antara setiap nod dan nod akar dan menyimpan hasilnya dalam tatasusunan. Kemudian, untuk setiap nod, kami menambah pemisahan (dikira) anak-anaknya daripada nod akar untuk menentukan pemisahan keseluruhan semua nod lain. Dengan cara ini, kita boleh mengira dengan cepat jumlah laluan terpendek antara semua nod. Sebagai cara yang cekap untuk menyelesaikan masalah ini, kerumitan masa algoritma ini ialah O(N), di mana N ialah bilangan nod dalam pokok.

Algoritma

• Ambil mana-mana nod dalam pokok sebagai akar dan akar pokok (cth. menggunakan carian mendalam nod akar) untuk mencipta pokok berakar.

• Pengaturcaraan dinamik boleh digunakan untuk menentukan jarak setiap nod dari akar. Jarak ini harus disimpan dalam tatasusunan atau struktur data.

• Kira jumlah jarak dari setiap nod ke semua nod lain dalam pepohon:

a. Lintas nod anak nod semasa.

b. Untuk mempertimbangkan laluan melalui nod semasa, tambahkan bilangan nod dalam subpokok dan jarak ke punca yang dikira sebelum ini untuk setiap subpokok.

c Untuk setiap nod anak nod aktif, tambahkan jumlah ini

d. Tambahkan jumlah nod semasa kepada hasil akhir.

• Jumlah semua pasangan laluan terpendek dalam pokok ialah hasil akhir.

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
   int val;
   vector<TreeNode*> children;
};

int dfs(TreeNode* node, vector<int>& distances) {
   int subtree_size = 1;
   for (TreeNode* child : node->children) {
      subtree_size += dfs(child, distances);
      distances[node->val] += distances[child->val] + subtree_size;
   }
   return subtree_size;
}

int sumOfAllPairShortestPaths(TreeNode* root) {
   vector<int> distances(root->val + 1, 0);
   dfs(root, distances);
   int total_sum = 0;
   for (int distance : distances) {
      total_sum += distance;
   }
   return total_sum;
}

int main() {
   TreeNode* root = new TreeNode{0};
   int result = sumOfAllPairShortestPaths(root);
   cout << "Sum of all pair shortest paths in the tree: " << result << endl;
   return 0;
}

Output

Sum of all pair shortest paths in the tree: 0

Kesimpulan

Jumlah semua pasangan laluan terpendek dalam pepohon boleh dikira menggunakan kaedah Double DFS (Depth First Search) atau pengaturcaraan dinamik. Kaedah DFS Berganda terdiri daripada dua hantaran, mula-mula mengira jarak dari nod yang dipilih ke semua nod lain, dan kemudian melintasi pepohon itu semula sambil menganggap setiap nod sebagai potensi nenek moyang sepunya terendah (LCA) untuk menjumlahkan jarak antara pasangan nod Keturunan. Kaedah pengaturcaraan dinamik memerlukan secara rekursif menggunakan DFS untuk membina akar pokok dan mengira jarak dari akar ke setiap nod lain. Hasil kedua-dua kaedah adalah sama dan terdiri daripada jumlah semua laluan terpendek berpasangan dalam pokok. Keputusan antara dua algoritma mungkin berdasarkan keutamaan pelaksanaan tertentu atau struktur pokok, tetapi kedua-dua algoritma menyediakan penyelesaian yang cekap.

Atas ialah kandungan terperinci Jumlah semua pasangan laluan terpendek dalam pokok itu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!