GT-reivew

Dựa vào 2 tính chất: hướng và trọng số, chúng ta có mấy loại đồ thị?

• 1

• 2

• 3

• 4

Cạnh (e) mà có đỉnh đầu (u) và đỉnh cuối (v) trùng nhau được gọi là?

• Khuyên (self-loop)

• Đỉnh treo (pendant)

• Đỉnh cô lập (isolated)

• Bậc (degree)

Cho đồ thị G có n đỉnh và m cạnh. Kích thước của ma trận kề của đồ thị G là

• n x n

• m x m

• n x m

• m x n

Thuật toán tìm kiếm theo chiều rộng tên là gì?

• BFS

• DFS

• HFS

• HDFS

Thuật toán BFS sử dụng cấu trúc dữ liệu nào?

• Stack

• Queue

• List

• Array

Có mấy phương pháp cơ bản hiện thực thuật toán DFS

• 1

• 2

• 3

• 4

Thuật toán BFS và DFS có thể giải quyết bài toán nào (chọn nhiều)

• Tìm đường đi ngắn nhất

• Kiểm tra tính liên thông

• Đếm miền liên thông

• Duyệt đồ thị

Thuật toán nào sau đây có thể tìm đường đi ngắn nhất giữa đỉnh s và các đỉnh còn lại trong đồ thị

• Floyd – Warshall​

• Kruskal

• Dijkstra

• DFS

Phát biểu nào sau đây SAI về thuật toán Dijkstra

• Thuật toán Dijkstra tìm đường đi ngắn nhất giữa các cặp đỉnh trong đồ thị

• Thuật toán Dijkstra không làm việc với đồ thị có trọng số âm

• Thuật toán Dijkstra chỉ làm việc trên đồ thị có trọng số

• Thuật toán Dijkstra sử dụng hàng đợi ưu tiên (Priority Queue) làm CTDL chính

Chúng ta sử dụng thuật toán nào để khắc phục vấn đề trọng số âm của thuật toán Dijkstra

• Prim

• Euler

• Bellman-Ford

• Floyd – Warshall​