11/09 11:56:51

Chúng ta đã biết bài toán và thuật toán duyệt (tìm kiếm) dữ liệu trên các cấu trúc dữ liệu khác nhau: – Kiểu dữ liệu mảng (một hoặc hai chiều). – Kiểu dữ liệu cây (cây nhị phân và cây tìm kiếm nhị phân). Vậy với dữ liệu của đồ thị, việc duyệt các đỉnh của đồ thị sẽ được thực hiện như thế nào? Quan sát hai đồ thị ở Hình 14.1 và thảo luận với bạn cách thực hiện duyệt trên các đỉnh của đồ thị đó.

Chúng ta đã biết bài toán và thuật toán duyệt (tìm kiếm) dữ liệu trên các cấu trúc dữ liệu khác nhau:

– Kiểu dữ liệu mảng (một hoặc hai chiều).

– Kiểu dữ liệu cây (cây nhị phân và cây tìm kiếm nhị phân).

Vậy với dữ liệu của đồ thị, việc duyệt các đỉnh của đồ thị sẽ được thực hiện như thế nào? Quan sát hai đồ thị ở Hình 14.1 và thảo luận với bạn cách thực hiện duyệt trên các đỉnh của đồ thị đó.

1 trả lời

+ Trả lời +4đ

Hỏi gia sư

+500k

8

1 trả lời

Thưởng th.10.2024

Xếp hạng

Đấu trường tri thức +500K

0

Cách thực hiện duyệt các đỉnh của đồ thị:

- Duyệt theo chiều sâu (DFS): Bắt đầu từ một đỉnh, tiếp tục đi sâu vào đồ thị theo một nhánh cho đến khi không thể đi xa hơn, sau đó quay lại (backtrack) và tiếp tục với nhánh khác.

- Duyệt theo chiều rộng (BFS): Bắt đầu từ một đỉnh, duyệt tất cả các đỉnh kề với nó trước, sau đó mới chuyển sang duyệt các đỉnh ở mức độ sâu tiếp theo.

- Đánh dấu các đỉnh: Khi duyệt, đánh dấu các đỉnh đã thăm để tránh duyệt lại nhiều lần.

- Thứ tự duyệt: Thứ tự duyệt có thể khác nhau tùy thuộc vào cách đồ thị được biểu diễn và thuật toán sử dụng.

Trả lời nhanh trong 10 phút và nhận thưởng

Đấu trường tri thức +500K

Chúng ta đã biết bài toán và thuật toán duyệt (tìm kiếm) dữ liệu trên các cấu trúc dữ liệu khác nhau:– Kiểu dữ liệu mảng (một hoặc hai chiều).– Kiểu dữ liệu cây (cây nhị phân và cây tìm kiếm nhị phân).Giải chuyên đề Tin 12 KNTT Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu có đáp án Tin học - Lớp 12 Tin học Lớp 12

Bạn muốn biết điều gì?

GỬI CÂU HỎI

Học tập không giới hạn cùng học sinh cả nước và AI, sôi động, tích cực, trải nghiệm

Tham gia Cộng đồng Lazi trên các mạng xã hội
Fanpage:	https://www.fb.com/lazi.vn
Group:	https://www.fb.com/groups/lazi.vn
Kênh FB:	https://m.me/j/AbY8WMG2VhCvgIcB
LaziGo:	https://go.lazi.vn/join/lazigo
Discord:	https://discord.gg/4vkBe6wJuU
Youtube:	https://www.youtube.com/@lazi-vn
Tiktok:	https://www.tiktok.com/@lazi.vn

Bài tập liên quan

Viết lại các hàm thiết lập đồ thị BuildGraph(fname) với tệp dữ liệu đầu vào là danh sách các cạnh của đồ thị. Đầu ra của hàm là dãy các giá trị V, E, A, Adj. Viết hàm cho cả hai trường hợp đồ thị vô hướng và đồ thị có hướng. (Tin học - Lớp 12)

1 trả lời

Cây nhị phân có thể được coi là đồ thị vô hướng, các nút của cây sẽ tương ứng là đỉnh, còn quan hệ cha-con là cạnh nối của đồ thị. Với cây nhị phân hoàn chỉnh, các đỉnh được đánh số theo chỉ số của mảng biểu diễn tương ứng của cây. Hãy tính ma trận kề của đồ thị tương ứng cây nhị phân ở hình bên. (Tin học - Lớp 12)

1 trả lời

Trong Nhiệm vụ 2, chúng ta có thể thấy các đỉnh kề không được in ra theo thứ tự tăng dần của chỉ số trong biểu diễn danh sách kề. Em hãy giải thích tại sao. Có thể chỉnh sửa chương trình để in ra các đỉnh kề theo thứ tự chỉ số tăng dần được không? (Tin học - Lớp 12)

1 trả lời

Trong Nhiệm vụ 1, hàm In_danh_sach_dinh_ke() lấy thông tin từ ma trận kề A. Có thể sử dụng hàm này với dữ liệu là danh sách kề Adj được không? Nếu có thì viết lại hàm này với dữ liệu đầu vào là danh sách kề Adj. (Tin học - Lớp 12)

1 trả lời

Em hãy trao đổi, thảo luận và trả lời một số câu hỏi sau: – Nếu đồ thị là vô hướng thì ma trận kề có đặc điểm gì? – Phân biệt sự giống nhau và khác nhau giữa ma trận kề và danh sách kề? – Khái niệm bậc của các đỉnh có gì khác nhau trong trường hợp đồ thị là vô hướng, có hướng? (Tin học - Lớp 12)

1 trả lời

Cho danh sách kề Adj của đồ thị G. Viết hàm GraphEdge(Adj) trả lại danh sách E các cạnh của đồ thị G. Viết chương trình cho hai trường hợp riêng biệt, G là đồ thị vô hướng và G là đồ thị có hướng. (Tin học - Lớp 12)

1 trả lời

Cho ma trận kề A của đồ thị vô hướng G. Viết hàm GraphEdge(A) trả lại danh sách E các cạnh của đồ thị G. (Tin học - Lớp 12)

1 trả lời

Từ ma trận kề A của đồ thị G có thể tính được số các cạnh của đồ thị không? Nếu được thì tính bằng cách nào? (Tin học - Lớp 12)

1 trả lời

Bổ sung thêm đoạn chương trình kiểm tra khi đọc dữ liệu danh sách các cạnh đồ thị của Hoạt động 3 như sau: Với mỗi dòng dữ liệu, nếu hai chỉ số i = j thì bỏ qua dòng này. (Tin học - Lớp 12)

1 trả lời

Hiện nay vỏ sọ phát triển mạnh mẽ của AI. Các sản phẩm robot công nghiệp là một công cụ không thể thiếu trong các công ty, nhà máy, xí nghiệp. Chúng đóng vai trò quan trọng trong sản xuất, nâng cao chất lượng sản phẩm, góp phần giảm chi phí sản xuất (Tin học - Lớp 12)

1 trả lời

Trang web đã xuất bản (công bố), có thể giới hạn người xem được không? Nếu có thể, hãy chỉ rõ các thao tác thực hiện. (Tin học - Lớp 12)

1 trả lời

Trang web đang soạn thảo, chưa xuất bản, có thể chia sẻ nó cho một nhóm người cùng tham gia soạn thảo hoặc công khai cho tất cả cùng xem được không? Nếu có thể, hãy chỉ rõ các thao tác thực hiện. (Tin học - Lớp 12)

1 trả lời

Kiểu phông chữ mặc định trong mỗi khối nội dung là kiểu như thế nào? (Tin học - Lớp 12)

1 trả lời

Xem thêm

Trắc nghiệm Tin học Lớp 12 mới nhất

Một gia đình có nhiều thành viên, mỗi người có một Laptop và một điện thoại thông minh. Thiết bị mạng nào được cung cấp bởi ISP để các thiết bị này có thể kết nối mạng Internet?

Một phòng Tin học có 20 máy tính. Những thiết bị nào cần thiết để kết nối các máy tính này trong một mạng LAN?

Thiết bị được kết nối mạng dây có đặc điểm nào sau đây?

Một gia đình có 3 thành viên, mỗi người có một Laptop và một điện thoại thông minh. Thiết bị mạng nào cần thiết để kết nối các thiết bị này trong một mạng LAN?

Giao tiếp qua không gian mạng là gì?

Xem thêm

Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi

Vui	Buồn	Bình thường

Học ngoại ngữ với Flashcard

Trang chủ	Giải đáp bài tập	Đố vui	Ca dao tục ngữ	Liên hệ	Tải ứng dụng Lazi
Giới thiệu	Hỏi đáp tổng hợp	Đuổi hình bắt chữ	Thi trắc nghiệm	Ý tưởng phát triển Lazi
Chính sách bảo mật	Trắc nghiệm tri thức	Điều ước và lời chúc	Kết bạn 4 phương	Xem lịch
Điều khoản sử dụng	Khảo sát ý kiến	Xem ảnh	Hội nhóm	Bảng xếp hạng
Tuyển dụng	Flashcard	DOL IELTS Đình Lực	Mua ô tô	Bảng Huy hiệu
Đấu trường tri thức	Thơ văn danh ngôn	Từ điển Việt - Anh	Đề thi, kiểm tra	Xem thêm

Trong Nhiệm vụ 1, hàm In_danh_sach_dinh_ke() lấy thông tin từ ma trận kề A. Có thể sử dụng hàm này với dữ liệu là danh sách kề Adj được không? Nếu có thì viết lại hàm này với dữ liệu đầu vào là danh sách kề Adj. (Tin học - Lớp 12)

Cho danh sách kề Adj của đồ thị G. Viết hàm GraphEdge(Adj) trả lại danh sách E các cạnh của đồ thị G. Viết chương trình cho hai trường hợp riêng biệt, G là đồ thị vô hướng và G là đồ thị có hướng. (Tin học - Lớp 12)

Cho ma trận kề A của đồ thị vô hướng G. Viết hàm GraphEdge(A) trả lại danh sách E các cạnh của đồ thị G. (Tin học - Lớp 12)

Từ ma trận kề A của đồ thị G có thể tính được số các cạnh của đồ thị không? Nếu được thì tính bằng cách nào? (Tin học - Lớp 12)

Bổ sung thêm đoạn chương trình kiểm tra khi đọc dữ liệu danh sách các cạnh đồ thị của Hoạt động 3 như sau: Với mỗi dòng dữ liệu, nếu hai chỉ số i = j thì bỏ qua dòng này. (Tin học - Lớp 12)

Khi nào thì tất cả các phần tử của Adj đều rỗng? (Tin học - Lớp 12)

Phát biểu nào sau đây là sai? (Tin học - Lớp 12)

Trong các cách giải thích ý nghĩa của thuật ngữ "Wireless Access Point", cách giải thích nào đúng? (Tin học - Lớp 12)

Câu nào sau đây là sai khi nói về giao thức TCP? (Tin học - Lớp 12)

Hub và Switch kết nối các máy tính trong mạng cục bộ hay mạng intenet mạng diện rộng mạng toàn cầu (Tin học - Lớp 12)

Điều nào sau đây không dùng khi nói về thẻ đánh dấu HTML (Tin học - Lớp 12)

Câu nào sau đây là sai khi nói về giao thức TCP? (Tin học - Lớp 12)

Trang web đã xuất bản (công bố), có thể giới hạn người xem được không? Nếu có thể, hãy chỉ rõ các thao tác thực hiện. (Tin học - Lớp 12)

Trang web đang soạn thảo, chưa xuất bản, có thể chia sẻ nó cho một nhóm người cùng tham gia soạn thảo hoặc công khai cho tất cả cùng xem được không? Nếu có thể, hãy chỉ rõ các thao tác thực hiện. (Tin học - Lớp 12)

Kiểu phông chữ mặc định trong mỗi khối nội dung là kiểu như thế nào? (Tin học - Lớp 12)

Cho biết đoạn soạn thảo văn bản HTML 5 sau bị lỗi cú pháp gì? Ngôn ngữ đánh dấu siêu văn bản
Chủ đề F

Phần tử nào sau đây được sử dụng để in nghiêng nội dung văn bản trong HTML?

Trong không gian mạng, hành động nào sau đây được coi là không phù hợp?

Khi đặt một siêu liên kết vào một đoạn văn bản nào đó, đoạn văn bản sẽ có định dạng mặc định là gì?

Cách Làm việc với ổ cắm thông minh:

Một gia đình có nhiều thành viên, mỗi người có một Laptop và một điện thoại thông minh. Thiết bị mạng nào được cung cấp bởi ISP để các thiết bị này có thể kết nối mạng Internet?

Một phòng Tin học có 20 máy tính. Những thiết bị nào cần thiết để kết nối các máy tính này trong một mạng LAN?

Thiết bị được kết nối mạng dây có đặc điểm nào sau đây?

Một gia đình có 3 thành viên, mỗi người có một Laptop và một điện thoại thông minh. Thiết bị mạng nào cần thiết để kết nối các thiết bị này trong một mạng LAN?

Giao tiếp qua không gian mạng là gì?

Đăng nhập

Mở khóa để xem toàn bộ nội dung trả lời