TAILIEUCHUNG - Cấu trúc dữ liệu và giải thuật part 6

Tham khảo tài liệu 'cấu trúc dữ liệu và giải thuật part 6', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Bài toán bao đóng truyền ứng trasitive closure Bài toán nêu trên có thể giải quyết được dỗ dàng bằng cách sử dụng ma trận lân cân của dồ thị. Trước hốt ta thấy có thể coi ma trận làn cận như một ma trận Bool. Như vậy có thổ tác động lên ma trận đó các phép toán lôgic đối với ma trận Bool được. Ta nhác lại hai phép toán logic - Phép cộng hay phép tuyển phép hoạc V - Phép nhân hay phép hội phép và A mà định nghĩa được cho bơi bảng sau a b a V b a A b 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 Đối với ma trận Bool A và B kích thước n X n phép cộng A với B để cho ma trận tổng c c A vB được thực hiện bằng cách tính C-J ajj V bjj với 1 i n 1 j n Phép nhân A với B để cho ma trân tích D được thực hiện bằng phép tính du kv aik Abk với l i n 1 j n Ta đã biết với ma trân lân cận A nếu a- 1 thì nghĩa là có một cung hay một đường đi độ dài 1 từ đỉnh i tới đỉnh j. Bây giờ thử xét A 2 A A A rõ ràng nếu phần tử ở hàng i cột j của A bằng 1 thì ít nhất cũng có một đường đi có độ dài 2 tù đỉnh i tới đỉnh j vì Aakj l thì ít nhất cũng có một giá trị k mà ajk Aakj 1 mà aik Aakj chỉ bằng 1 khi 158 và chỉ khi cả alk 1 và akj 1 nghĩa là khì có đường đi độ dài 1 từ đỉnh i tới đỉnh k và có đường đi có độ dài 1 từ đĩnh k tới đỉnh j. Từ đó suy ra điều tương tự cho A l A A Aư với r 3 4. nghĩa là nếu tijj - 1 thì ít nhất có một đường đi độ dài r từ đỉnh i tới đỉnh J. Như vậy nếu ta lập ma trận p A V Aí2 vv A n V A k k-1 thì p sẽ cho biết có hay không đường di có độ dài lớn nhất là n từ đỉnh i tới đỉnh j. p được gọi là ma trân đường đi path matricc của đồ thị G. Ví dụ Với đổ thị Hỉnh i ta se có 0 0 10 0 0 10 0 0 11 0 10 0 0 0 11 0 0 11 0 111 0 0 10 0 111 0 111 0 111 0 0 11 A 2 A 0 111 0 111 0 111 0 111 0 111 0 111 0 111 0 111 Aơ p Việc tính p có thổ dễ dàng thực hiện bởi giải thuật Warshall sau đây 159 Procedure WARSHALL A p n 1 p A Đây là phép gán quy ước thay vào cho việc gán lần lượt các phần tử của A cho các phần tử tương ứng của PJ 2 for k 1 to n do for i 1 to n do for j 1 to n do p i j pfi j

• Cơ sở dữ liệu
• Cấu trúc dữ liệu và giải thuật
• tài liệu Cấu trúc dữ liệu và giải thuật
• giáo trình Cấu trúc dữ liệu và giải thuật
• bài giảng Cấu trúc dữ liệu và giải thuật
• bài tập Cấu trúc dữ liệu và giải thuật
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật đệ quy
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• phân tích thiết kế
• thiết kế hướng đối tượng
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp