Giả sử chúng ta có ma trận kề của một đồ thị có hướng G. Cho đến khi đồ thị trở nên trống, chúng ta lặp lại thao tác sau:Chọn một đỉnh từ G, sau đó xóa đỉnh đó và tất cả các đỉnh có thể tới được từ đỉnh đó bằng cách đi theo một số cạnh. Xóa một đỉnh cũng sẽ xóa các cạnh của nó. Chúng tôi phải tìm số lần dự kiến hoạt động được thực hiện
Vì vậy, nếu đầu vào giống như
thì kết quả ra sẽ là 1.6667, vì ban đầu chọn đỉnh A thì loại bỏ tất cả các đỉnh, nếu chọn đỉnh B thì loại bỏ B và C, ở thao tác thứ 2 chọn A để loại bỏ, tương tự với chọn C cũng phải thực hiện 2 thao tác. Vậy giá trị trung bình là (1 + 2 + 2) / 3 =1,6667.
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
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
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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;
} Đầu vào
{ { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } } Đầu ra
1.66667