Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 12: Biểu diễn đồ thị

VUI MỪNG CHÀO ĐÓN CÁC EM ĐẾN BÀI HỌC MỚI!

KHỞI ĐỘNG

Quan sát đồ thị Hình 12.1 và cho biết mỗi tệp dữ liệu sau có ý nghĩa gì

Tệp 1

Tệp 2

Tệp 3

Đồ thị

• Tệp 1: Danh sách các cạnh của đồ thị.
• Tệp 2: Ma trận kề của đồ thị.
• Tệp 3: Danh sách kề của đồ thị.

BÀI 12: BIỂU DIỄN ĐỒ THỊ

Tin học 12

NỘI DUNG BÀI HỌC

Mô hình dữ liệu đồ thị

Thiết lập đồ thị từ danh sách các cạnh

Thiết lập đồ thị từ tệp ma trận kề và tệp danh sách kề

MÔ HÌNH DỮ LIỆU ĐỒ THỊ

DOWNLOAD

Đọc Hoạt động 1 SGK tr.56 và trả lời câu hỏi:

Tìm hiểu, thảo luận về các cách biểu diễn dữ liệu của một đồ thị G.

Sử dụng danh sách các cạnh của đồ thị.

Sử dụng ma trận kề kích thước n × n.

Sử dụng danh sách kề.

a) Dữ liệu danh sách các cạnh của đồ thị

Hình 12.2. Tệp danh sách các cạnh

Dòng đầu tiên là số n.

Các dòng tiếp theo, mỗi dòng là hai chỉ số mô tả một cạnh của đồ thị.

b) Dữ liệu ma trận kề của đồ thị

Hình 12.3. Tệp ma trận kề

Dòng đầu tiên là số n.

n dòng tiếp theo là dữ liệu ma trận kề A.

c) Dữ liệu danh sách kề của đồ thị

Hình 12.4. Tệp danh sách kề

• Dòng đầu tiên là số n.
• n dòng tiếp theo là dữ liệu danh sách kề Adj.
• Dòng thứ i sẽ bắt đầu bằng số i → danh sách các đỉnh là kề của i, mỗi đỉnh ghi số thứ tự của đỉnh, cách nhau bởi dấu cách.

Yêu cầu thành phần đầu tiên của dòng thứ i là số i chỉ có ý nghĩa hình thức (cần thiết khi đỉnh i của đồ thị là biệt lập, không có các đỉnh kề → dòng thứ i chỉ có đúng một giá trị.

Củng cố kiến thức

Câu 1:

Vẽ đồ thị có tệp dữ liệu ma trận kề Hình 12.5.

Hình 12.5. Tệp ma trận kề

Củng cố kiến thức

Câu 2:

Có thể có hai tệp dữ liệu dạng danh sách kề khác nhau nhưng biểu diễn hai đồ thị hoàn toàn giống nhau không?

Có. Vì tệp dữ liệu danh sách các cạnh không quy định thứ tự các cạnh, nên hai tệp khác nhau vẫn biểu diễn cùng một đồ thị.

THIẾT LẬP ĐỒ THỊ TỪ TỆP MA TRẬN KỀ VÀ TỆP DANH SÁCH KỀ

DOWNLOAD

Tìm hiểu, thảo luận cách thiết lập đồ thị (dữ liệu của đồ thị) trong trường hợp tệp dữ liệu biểu diễn là ma trận kề hoặc danh sách kề.

a) Thiết lập đồ thị từ tệp ma trận kề

• Dòng đầu tiên là n (số đỉnh của đồ thị).
• n dòng tiếp theo tả ma trận kề của đồ thị.
• Áp dụng cho cả đồ thị vô hướng và đồ thị có hướng.
• Hàm BuildGraph(fname) đọc dữ liệu từ tệp fname và trả về bộ dữ liệu V.
• A với V là danh sách các đỉnh.
• A là ma trận kề.

b) Thiết lập đồ thị từ tệp danh sách kề

• Dòng đầu tiên là n (số đỉnh của đồ thị).
• n dòng tiếp theo tả danh sách kề của đồ thị.
• Áp dụng cho cả đồ thị vô hướng và đồ thị có hướng.
• Hàm BuildGraph(fname) đọc dữ liệu từ tệp có tên fname và trả về bộ dữ liệu V.
• Adj với V là danh sách các đỉnh, Adj là danh sách kề.

Củng cố kiến thức

Câu 1:

Khẳng định dãy Adj[i] có số lượng phần tử bằng số các phần tử có giá trị 1 của hàng thứ i của ma trận kề A là đúng hay sai?

Đúng.

Câu 2:

Khi nào ma trận kề A chỉ gồm toàn số 0?

Ma trận kề A gồm toàn số 0 nếu đồ thị không có bất kì cạnh nào, tức là số cạnh bằng 0.

THIẾT LẬP ĐỒ THỊ TỪ DANH SÁCH CÁC CẠNH

--------------- Còn tiếp ---------------