giải theo thuật toán Kahn
- B1: nhập các đỉnh theo đồ thị có hướng như bình thường
- B2: tạo 1 mảng lưu số bậc của các đỉnh(số bậc của một đỉnh là số lượng đỉnh đi đến đỉnh đấy)
- B3: khởi tạo thuật toán Kahn
+ tạo 1 hàng đợi
+ for các đỉnh i từ 1 -> n nếu số bậc của i bằng 0 thì thêm đỉnh i vào hàng đợi
+ tạo 1 biến đếm
+ tạo vòng lặp while với điều kiện số lượng phần tử trong hàng đợi khác 0
+ (trong vòng while) với mỗi lần chạy của vòng while biến đếm tăng thêm 1
+ (trong vòng while) lấy phần tử đầu tiên của hàng đợi ra và xoá phần tử đó khỏi hàng đợi
+ (trong vòng while) for các đỉnh mà đỉnh đấy có thể đi đến
+ (trong vòng for ở trong vòng while) xoá bậc của các đỉnh có thể đi đến đi 1 bậc
+ (trong vòng for ở trong vòng while) kiểm tra xem số bậc của các đỉnh có thể đi tới có bằng 0 không
+ (trong vòng for ở trong vòng while) nếu có thì thêm đỉnh có thể đi tới đó vào hàng đợi
+ nếu biến đếm có giá trị bằng số lượng đỉnh thì trả về "YES"
+ còn không trả về "NO"
- B4: gọi hàm Kahn và in ra giá trị trả về của hàm Kahn
GIẢI THÍCH : các bạn sẽ có câu hỏi tại sao giá trị biến đếm bằng số lượng đỉnh thì lại là "YES" đúng không
là vì nếu đồ thị có chu trình thì khi đến 1 đỉnh nào đó của chu trình trong đồ thì thì số bậc của đỉnh đó
không chuyển về không trong khi hàng đợi không còn giá trị nào mà để hàng đợi có giá trị thì số bậc của đỉnh
đấy phải về 0 mới được thêm vào khi này hàng đợi không có phần tử nào vòng lặp while sẽ bị thoát và khi này
cái đỉnh có số bậc kia chưa về 0 là đỉnh bị xót lại vì chưa được thêm vào hàng đợi để xét khi đó khi ta so
sánh biến đếm và số đỉnh sẽ khác nhau khi đó đồ thị ta đang xét là đồ thị có chu trình nên sẽ trả về "NO" còn
nếu giá trị biến đếm bằng số bậc khi đó các đỉnh đều được xét hết nên trả về "YES"
Chinhle
Created at
0 likes