Giải thuật và lập trình - C: BÀI TẬP

1. Viết biểu diễn đồ thị V.8 bằng:

• Ma trận kề.
• Danh sách các đỉnh kề.

10. Cài đặt đồ thị vô hướng bằng ma trận kề rồi viết các giải thuật:

• Duyệt theo chiều rộng.
• Duyệt theo chiều sâu.
• Tìm đường đi ngắn nhất từ một đỉnh cho trước (Dijkstra).
• Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh (Floyd).
• Tìm cây bao trùm tối thiểu (Prim, Kruskal).
• Cài đặt thuật toán Greedy cho bài toán tô màu đồ thị (Gợi ý: xem giải thuật trong chương 1).

11. Cài đặt đồ thị vô hướng bằng danh sách các đỉnh kề rồi viết các giải thuật:

• Duyệt theo chiều rộng.
• Duyệt theo chiều sâu.

12. Hãy viết một chương trình, trong đó, cài đặt đồ thị vô hướng bằng cấu trúc ma trận kề rồi viết các thủ tục/hàm sau:

• Nhập toạ độ n đỉnh của đồ thị.
• Giả sử đồ thị là đầy đủ, tức là hai đỉnh bất kỳ đều có cạnh nối, và giả sử giá của mỗi cạnh là độ dài của đoạn thẳng nối hai cạnh. Hãy tìm:
  • Đường đi ngắn nhất từ một đỉnh cho trước (Dijkstra).
  • Đường đi ngắn nhất giữa tất cả các cặp đỉnh (Floyd).
  • Cây bao trùm tối thiểu (Prim, Kruskal).
• Thể hiện đồ thị lên màn hình đồ hoạ, các cạnh thuộc cây bao trùm tối thiểu được vẽ bằng một màu khác với các cạnh khác.