Podcast Beta
Questions and Answers
Để kiểm tra đồ thị là strongly connected, chúng ta cần thực hiện bao nhiêu lần DFS?
Thuật toán nào dưới đây chỉ cần 1 lần DFS để chia đồ thị thành các tập con là một thành phần liên thông mạnh?
Ý nghĩa của cây khung (Spanning Tree) trong đồ thị là gì?
Thuật toán nào dưới đây được sử dụng để tìm cây khung có trọng số nhỏ nhất trên đồ thị?
Signup and view all the answers
Thời gian thực hiện của thuật toán Kosaraju là gì?
Signup and view all the answers
Bài toán chia đồ thị thành các tập con là một thành phần liên thông mạnh có tên là gì?
Signup and view all the answers
Tại sao thuật toán Tarjan lại được ưa chuộng trong chia đồ thị thành các tập con là một thành phần liên thông mạnh?
Signup and view all the answers
Ý nghĩa của thuật toán duyệt đồ thị là gì?
Signup and view all the answers
Thuật toán nào được sử dụng để tìm đường đi ngắn nhất giữa hai đỉnh trên đồ thị không có trọng số âm?
Signup and view all the answers
Để tìm kiếm thành phần liên thông của đồ thị, người ta sử dụng thuật toán nào?
Signup and view all the answers
Bài toán nào liên quan đến việc tô màu các đỉnh trên đồ thị bằng 2 màu?
Signup and view all the answers
Thuật toán nào được sử dụng để tìm đường đi ngắn nhất trên đồ thị có trọng số âm nhưng không có chu trình âm?
Signup and view all the answers
Khẳng định nào sau đây là đúng về thành phần liên thông của đồ thị?
Signup and view all the answers
Thuật toán nào được sử dụng để tìm đường đi ngắn nhất trên đồ thị có chu trình âm?
Signup and view all the answers
Bài toán nào liên quan đến việc tìm kiếm đường đi ngắn nhất giữa hai đỉnh trên đồ thị?
Signup and view all the answers
Thuật toán nào được sử dụng để kiểm tra đồ thị có liên thông hay không?
Signup and view all the answers
Nhược điểm của biểu diễn đồ thị bằng ma trận kề là gì?
Signup and view all the answers
Khi nào nên dùng danh sách kề để biểu diễn đồ thị?
Signup and view all the answers
Thuật toán nào tìm kiếm tất cả các đỉnh mà có thể tới được từ đỉnh nguồn s?
Signup and view all the answers
Ưu điểm của dùng danh sách kề là gì?
Signup and view all the answers
Thư viện nào cung cấp các hàm về đồ thị?
Signup and view all the answers
Tìm kiếm theo chiều rộng được dùng để làm gì?
Signup and view all the answers
Biểu diễn đồ thị bằng cấu trúc nào?
Signup and view all the answers
Ưu điểm của dùng ma trận kề là gì?
Signup and view all the answers
Study Notes
Kiểm tra đồ thị là strongly connected
- Thực hiện DFS từ 1 đỉnh v tuỳ ý
- Đổi hướng các đỉnh trên đồ thị cũ và thực hiện DFS lại với đỉnh v
Thuật toán tìm thành phần liên thông mạnh
- Kosaraju: cần 2 lần DFS trên đồ thị
- Tarjan: 1 Lần DFS
- Gabow
- Thời gian ( + | |)
Ứng dụng của các thuật toán duyệt đồ thị
- Bài toán 8: Cây khung có trọng số nhỏ nhất trên đồ thị (minimum spanning tree - MST)
- Cây khung: là cây chứa mà kết nối tất cả các đỉnh của đồ thị
- Cost = 17 and Cost = 10
Bài toán 1: Tìm đường đi ngắn nhất giữa hai đỉnh trên đồ thị
- Trường hợp đồ thị không có trọng số âm: Thuật toán Dijkstra
- Trường hợp đồ thị có trọng số âm: Thuật toán Ford Bellman
- Trường hợp đồ thị có chu trình âm: Thuật toán Floyd Warshall
Bài toán 2: Thành phần liên thông – connected components
- Thành phần liên thông của 1 đồ thị vô hướng là tập đỉnh lớn nhất
- Thực hiện DFS hoặc BFS để kiểm tra đồ thị liên thông
- Tất cả các đỉnh đều được thăm liên thông
Bài toán 3: Bi-coloring graphs – tô màu các đỉnh trên đồ thị
- Kiểm tra xem có thể tô màu các đỉnh trên đồ thị chỉ bằng 2 màu
- 2 đỉnh của mỗi cạnh đều có màu khác nhau
Biểu diễn đồ thị
- Ma trận kề và danh sách kề
- Kiểm tra cạnh và tìm bậc của node
- Kích thước bộ nhớ và thêm xóa cạnh
- Duyệt trên đồ thị
Thư viện các hàm về đồ thị thông dụng
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Kiểm tra kiến thức về đồ thị có hướng, bao gồm các cách biểu diễn đồ thị và các vấn đề liên quan.
