โปรแกรม C++ เพื่อนับจำนวนการดำเนินการที่จำเป็นสำหรับการลบโหนดทั้งหมด

สมมติว่าเรามีเมทริกซ์ที่อยู่ติดกันของกราฟกำกับ G จนกว่ากราฟจะว่างเปล่า เรากำลังดำเนินการต่อไปนี้ซ้ำ:เลือกจุดยอดหนึ่งจุดจาก G จากนั้นลบจุดยอดนั้นและจุดยอดทั้งหมดที่สามารถเข้าถึงได้จากจุดยอดนั้นโดยทำตามขอบบางส่วน การลบจุดยอดจะลบขอบที่ตกกระทบลงไปด้วย เราต้องหาจำนวนครั้งที่คาดว่าจะดำเนินการเสร็จ

ดังนั้นหากอินพุตเป็นแบบ

ผลลัพธ์จะเป็น 1.6667 เนื่องจากเริ่มแรกเลือกจุดยอด A ลบจุดยอดทั้งหมด หากเราเลือกจุดยอด B ลบ B และ C และในการดำเนินการที่สอง เลือก A เพื่อลบ ในทำนองเดียวกันโดยการเลือก C ก็ต้องใช้ 2 การดำเนินการเช่นกัน ค่าเฉลี่ยคือ (1+2+2)/3 =1.6667

ขั้นตอน

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

n := size of G
for initialize i := 0, when i < n, update (increase i by 1), do:
   G[i, i] := 1
for initialize k := 0, when k < n, update (increase k by 1), do:
   for initialize i := 0, when i < n, update (increase i by 1), do:
      for initialize j := 0, when j < n, update (increase j by 1), do:
         if G[i, k] is non-zero and G[k, j] is non-zero, then:
            G[i, j] := 1
         ans := 0
      for initialize i := 0, when i < n, update (increase i by 1), do:
         k := 0
      for initialize j := 0, when j < n, update (increase j by 1), do:
         if G[j, i] is non-zero, then:
            (increase k by 1)
         ans := ans + 1.0 / k
return ans

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;

double solve(vector<vector<int>> G){
   int n = G.size();
   for (int i = 0; i < n; ++i)
      G[i][i] = 1;
   for (int k = 0; k < n; ++k)
      for (int i = 0; i < n; ++i)
         for (int j = 0; j < n; ++j)
            if (G[i][k] && G[k][j])
               G[i][j] = 1;
   double ans = 0;
   for (int i = 0; i < n; ++i){
      int k = 0;
      for (int j = 0; j < n; ++j)
         if (G[j][i])
            ++k;
         ans += 1.0 / k;
   }
   return ans;
}
int main(){
   vector<vector<int>> G = { { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 }};
   cout << solve(G) << endl;
}

อินพุต

{ { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } }

ผลลัพธ์

1.66667