Bài tập về đồ thị

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

- Ma trận kề.

- Danh sách các đỉnh kề.

Hình V.8

2. Duyệt đồ thị hình V.8 (xét các đỉnh theo thứ tự a,b,c...)

- Theo chiều rộng bắt đầu từ a.

- Theo chiều sâu bắt đầu từ f

3. Áp dụng giải thuật Dijkstra cho đồ thị hình V.8, với đỉnh nguồn là a.

Hình V.9

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

Ma trận kề.

Danh sách các đỉnh kề.

5. Duyệt đồ thị hình V.9 (xét các đỉnh theo thứ tự A,B,C...)

Theo chiều rộng bắt đầu từ A.

Theo chiều sâu bắt đầu từ B.

6. Áp dụng giải thuật Dijkstra cho đồ thị hình V.9, với đỉnh nguồn là A.

7. Tìm cây bao trùm tối thiểu của đồ thị hình V.9 bằng

Giải thuật Prim.

Giải thuật Kruskal.

8. Cài đặt đồ thị có 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).

9. Cài đặt đồ thị có 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.

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.