Bài tập Bài 1 Phương pháp cài đặt như trên có thể nói là rất hay và hiệu quả, đòi hỏi ta phải hiểu rõ bản chất thuật toán, nếu không thì rất dễ nhầm. Trên thực tế, còn có một phương pháp khác dễ hiểu hơn, tuy tính hiệu quả có kém hơn một chút. Hãy viết chương trình mô tả phương pháp sau: Vẫn dùng thuật toán tìm kiếm theo chiều sâu với thủ tục Visit nói ở đầu mục, đánh số lại các đỉnh từ 1 tới n theo thứ tự duyệt xong, sau đó đảo chiều. | Các thuật toán trên đồ thị 203 Init Solve Close fo end. Bài tập Bài 1 Phương pháp cài đặt như trên có thể nói là rất hay và hiệu quả đòi hỏi ta phải hiểu rõ bản chất thuật toán nếu không thì rất dễ nhầm. Trên thực tế còn có một phương pháp khác dễ hiểu hơn tuy tính hiệu quả có kém hơn một chút. Hãy viết chương trình mô tả phương pháp sau vẫn dùng thuật toán tìm kiếm theo chiều sâu với thủ tục Visit nói ở đầu mục đánh số lại các đỉnh từ 1 tới n theo thứ tự duyệt xong sau đó đảo chiều tất cả các cung của đồ thị. Xét lần lượt các đỉnh theo thứ tự từ đỉnh duyệt xong sau cùng tới đỉnh duyệt xong đầu tiên với mỗi đỉnh đó ta lại dùng thuật toán tìm kiếm trên đồ thị BFS hay DFS liệt kê những đỉnh nào đến được từ đỉnh đang xét đó chính là một thành phần liên thông mạnh. Lưu ý là khi liệt kê xong thành phần nào ta loại ngay các đỉnh của thành phần đó khỏi đồ thị. Tính đúng đắn của phương pháp có thể hình dung không mấy khó khăn Trước hết ta thêm vào đồ thị đỉnh x và các cung x v với mọi v sau đó gọi Visit x để xây dựng cây DFS gốc x. Hiển nhiên x là chốt của thành phần liên thông chỉ gồm mỗi x. Sau đó bỏ đỉnh x khỏi cây DFS cây sẽ phân rã thành các cây con. Đỉnh r duyệt xong sau cùng chắc chắn là gốc của một cây con bởi khi duyệt xong nó chắc chắn sẽ lùi về x suy ra r là chốt. Hơn thế nữa nếu một đỉnh u nào đó tới được r thì u cũng phải thuộc cây con gốc r. Bởi nếu giả sử phản chứng rằng u thuộc cây con khác thì u phải được thăm trước r do cây con gốc r được thăm tới sau cùng có nghĩa là khi Visit u thì r chưa thăm. Vậy nên r sẽ thuộc nhánh DFS gốc u mâu thuẫn với lập luận r là gốc. Từ đó suy ra nếu u tới được r thì r tới được u tức là khi đảo chiều các cung nếu r tới được đỉnh nào thì đỉnh đó thuộc thành phần liên thông chốt r. Loại bỏ thành phần liên thông với chốt r khỏi đồ thị. Cây con gốc r lại phân rã thành nhiều cây con. Lập luận tương tự như trên với v là đỉnh duyệt xong sau cùng Hình 66 . Ví dụ Lê Minh Hoàng 204 Chuyên đề Hình 66 Đánh số lại đảo chiều các cung và .
