Đường dẫn ngắn nhất đến thăm tất cả các nút trong C ++

Giả sử chúng ta có một đồ thị vô hướng, liên thông với N nút, các nút này được đánh dấu là 0, 1, 2, ..., N-1. độ dài đồ thị sẽ là N, và j không giống như i trong đồ thị danh sách [i] đúng một lần, nếu và chỉ khi các nút i và j được nối với nhau. Chúng ta phải tìm độ dài của đường đi ngắn nhất đến thăm mọi nút. Chúng tôi có thể bắt đầu và dừng lại ở bất kỳ nút nào, chúng tôi có thể truy cập lại các nút nhiều lần và chúng tôi có thể sử dụng lại các cạnh.

Vì vậy, nếu đầu vào giống như [[1], [0,2,4], [1,3,4], [2], [1,2]], thì đầu ra sẽ là 4. Bây giờ ở đây có thể đường dẫn là [0,1,4,2,3].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàng đợi
n:=kích thước của đồ thị
yêu cầu:=2 ^ (n - 1)
Xác định một bản đồ
để khởi tạo i:=0, khi i
- chèn {0 OR (2 ^ i), i} vào q
nếu n giống 1 thì -
- trả về 0
để khởi tạo lvl:=1, khi không phải q trống, hãy cập nhật (tăng lvl lên 1), thực hiện -
- sz:=kích thước của q
- trong khi sz khác 0, giảm sz đi 1 trong mỗi lần lặp, thực hiện -
  - Xác định mảng curr =phần tử phía trước của q
  - xóa phần tử khỏi q
  - để khởi tạo i:=0, khi i
    - u:=graph [curr [1], i]
    - newMask:=(curr [0] HOẶC 2 ^ u)
    - nếu newMask giống với req, thì -
      - trả về lvl
    - nếu số lượng cuộc gọi (newMask) trong số [u] đã truy cập, thì -
      - Bỏ qua phần sau, chuyển sang phần tiếp theo
    - chèn newMask vào [u]
      đã truy cập
    - chèn {newMask, u} vào q
trả về -1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   int shortestPathLength(vector<vector<int> >& graph){
      queue<vector<int> > q;
      int n = graph.size();
      int req = (1 << n) - 1;
      map<int, set<int> > visited;
      for (int i = 0; i < n; i++) {
         q.push({ 0 | (1 << i), i });
      }
      if (n == 1)
      return 0;
      for (int lvl = 1; !q.empty(); lvl++) {
         int sz = q.size();
         while (sz--) {
            vector<int> curr = q.front();
            q.pop();
            for (int i = 0; i < graph[curr[1]].size(); i++) {
               int u = graph[curr[1]][i];
               int newMask = (curr[0] | (1 << u));
               if (newMask == req)
                  return lvl;
               if (visited[u].count(newMask))
               continue;
               visited[u].insert(newMask);
               q.push({ newMask, u });
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1},{0,2,4},{1,3,4},{2},{1,2}};
   cout << (ob.shortestPathLength(v));
}

Đầu vào

{{1},{0,2,4},{1,3,4},{2},{1,2}}

Đường dẫn ngắn nhất đến thăm tất cả các nút trong C ++

Ví dụ

Đầu vào

Đầu ra