TAILIEUCHUNG - Tài liệu tham khảo môn học Cấu trúc dữ liệu
Tài liệu tham khảo môn học Cấu trúc dữ liệu gồm 8 chương với mục tiêu giới thiệu cho học sinh về khái niệm về kiểu dữ liệu trừu tượng, kiểu dữ liệu trừu tượng, cấu trúc dữ liệu thông dụng, nâng cao và những thao tác trên các cấu trúc đó, một số thuật toán cơ bản và rèn luyện một số kĩ năng phân tích thuật toán. | Để cài đặt thuật giải, với giả thiết N không lớn hơn 100, ta sẽ dùng cách thể hiện đồ thị bằng ma trận kề, đó là một mảng hai chiều A[1100,1100] mà A[I,J] = 1 nếu có cung (I,J) và bằng 0 nếu không có cung (I,J). Để ghi nhận thông tin với mỗi đỉnh J, đỉnh đó đã qua/chưa qua và nếu đã qua, đỉnh ngay trước nó trên đường từ U đến là đỉnh nào, ta chỉ cần dùng một mảng một chiều T[1100] mà T[J] = 0 có nghĩa là chưa đi qua đỉnh J, nếu T[J] khác 0, giá trị của T[J] chính là đỉnh ngay trước nó trên đường từ U đến. Để ghi nhận việc có/không có đường đi từ U đến, ta dùng biến Found kiểu Boolean, ban đầu ta khởi tạo Found=False. Nếu có đường đi từ U đến V, ta cho giá trị Found=True, khi đó, để tìm đường đi từ U đến V ta ghi nhận các đỉnh lần lượt trên đường đi vào mảng H và số đỉnh thuộc đường đi vào biến SD, ta bắt đầu từ V, tìm đỉnh ngay trước V trên đường đi từ U đến và ghi vào mảng H, cho đỉnh đó đóng vai trò V, ta lại tìm đỉnh ngay trước nó, cứ như vậy khi nào ta dò được về U thì ghi nhận được các đỉnh trên đường đi từ U theo thứ tự ngược lại: từ V về U; để viết đường đi, ta phải viết các đỉnh của mảng H theo thứ tự từ SD đến 1.
đang nạp các trang xem trước
