เส้นทางที่สั้นที่สุดในการเยี่ยมชมโหนดทั้งหมดใน C++

สมมติว่าเรามีกราฟที่เชื่อมต่อแบบไม่มีทิศทางและมีโหนด N โหนด โหนดเหล่านี้มีป้ายกำกับว่า 0, 1, 2, ..., N-1 ความยาวของกราฟจะเป็น N และ j ไม่เหมือนกับ i ที่อยู่ในรายการ graph[i] เพียงครั้งเดียว ถ้าหากว่าโหนด i และ j เชื่อมต่อกัน เราต้องหาความยาวของเส้นทางที่สั้นที่สุดที่เข้าชมทุกโหนด เราสามารถเริ่มต้นและหยุดที่โหนดใดก็ได้ เราสามารถกลับมายังโหนดได้หลายครั้ง และเราสามารถนำขอบกลับมาใช้ใหม่ได้

ดังนั้นหากอินพุตเป็น [[1],[0,2,4],[1,3,4],[2],[1,2]] ผลลัพธ์จะเป็น 4 ตอนนี้เป็นไปได้ เส้นทางคือ [0,1,4,2,3]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่งคิว

• n :=ขนาดของกราฟ

• req :=2^(n - 1)

• กำหนดหนึ่งแผนที่

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • แทรก {0 OR (2^i), i} ลงใน q

• ถ้า n เท่ากับ 1 แล้ว −

  • คืนค่า 0

• สำหรับการเริ่มต้น lvl :=1 เมื่อไม่มี q ว่าง ให้อัปเดต (เพิ่ม lvl ขึ้น 1) ทำ -

  • sz :=ขนาดของ q

  • ในขณะที่ sz ไม่ใช่ศูนย์ ให้ลด sz ลง 1 ในการวนซ้ำแต่ละครั้ง ให้ทำ -

    • กำหนดอาร์เรย์ curr =องค์ประกอบด้านหน้าของ q

    • ลบองค์ประกอบออกจาก q

    • สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของกราฟ[curr[1]] อัปเดต (เพิ่ม i ขึ้น 1) ทำ

      • u :=กราฟ[curr[1], i]

      • newMask :=(curr[0] หรือ 2^u)

      • ถ้า newMask เหมือนกับ req แล้ว −

        • กลับเลเวล

      • ถ้านับการโทร (newMask) ของการเยี่ยมชม[u] แล้ว −

        • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

      • ใส่ newMask เข้าไปที่ visit[u]

      • แทรก {newMask, u} ลงใน q

• กลับ -1

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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));
}

อินพุต

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

ผลลัพธ์

4