Bối cảnh và vấn đề nghiên cứu

Lý thuyết đồ thị là một chuyên ngành toán học rời rạc có nguồn gốc từ thế kỷ 18, khởi đầu từ các công trình nghiên cứu của nhà toán học Leonhard Euler. Trong bối cảnh công nghệ thông tin và khoa học máy tính phát triển, các mô hình đồ thị trở thành công cụ nền tảng để biểu diễn và giải quyết nhiều bài toán kỹ thuật thực tiễn. Cụ thể, đồ thị được ứng dụng trong việc giải tích mạch điện để xác định các mạch vòng, xác định đường đi ngắn nhất giữa các địa điểm trong mạng lưới giao thông, bài toán điều độ công việc và lập thời khóa biểu, cũng như tối ưu hóa định tuyến trong mạng máy tính và lý thuyết mã hóa.

Tuy nhiên, việc tiếp cận các cấu trúc dữ liệu đồ thị và thuật toán liên quan thông qua lý thuyết thuần túy thường gặp khó khăn trong việc hình dung trạng thái biến đổi dữ liệu. Nhằm giải quyết vấn đề này, đồ án môn học "Minh họa trực quan bằng giao diện đồ họa các thuật toán Tìm thành phần liên thông của đồ thị Duyệt đồ thị theo chiều rộng và theo chiều sâu" được thực hiện trong khuôn khổ học phần Lý thuyết đồ thị và ứng dụng (mã học phần: COMP170101) tại Khoa Công nghệ Thông tin, Trường Đại học Sư phạm Thành phố Hồ Chí Minh.

Mục tiêu và nhiệm vụ nghiên cứu của đồ án được xác định rõ ràng:

  1. Mục tiêu tổng quát: Nghiên cứu chuyên sâu cơ chế hoạt động của thuật toán tìm kiếm theo chiều rộng (Breadth-First Search - BFS), thuật toán tìm kiếm theo chiều sâu (Depth-First Search - DFS) và thuật toán phân rã thành phần liên thông; đồng thời xây dựng một phần mềm có giao diện đồ họa trực quan giúp người dùng dễ dàng thao tác, quan sát và hiểu rõ cơ chế thực thi của từng thuật toán trên đồ thị tùy biến.
  2. Nhiệm vụ nghiên cứu:
    • Nghiên cứu cơ sở lý luận về cấu trúc đồ thị vô hướng, đồ thị có hướng, ma trận kề và nguyên lý hoạt động của các giải thuật duyệt đồ thị và xét tính liên thông.
    • Hiện thực hóa các thuật toán xử lý đồ thị trên cấu trúc dữ liệu bằng ngôn ngữ lập trình C#.
    • Thiết kế giao diện đồ họa người dùng (GUI) cho phép tạo đỉnh, thêm/xóa cạnh, chuyển đổi dữ liệu sang ma trận kề và mô phỏng từng bước duyệt đồ thị.
    • Kiểm thử chương trình, sửa lỗi và đóng gói sản phẩm hoàn chỉnh cùng tài liệu báo cáo.

Đối tượng và phạm vi nghiên cứu:

  • Đối tượng nghiên cứu: Các cấu trúc đồ thị cơ bản (đồ thị có hướng, đồ thị vô hướng), ma trận kề; giải thuật duyệt theo chiều rộng (BFS); giải thuật duyệt theo chiều sâu (DFS); giải thuật tìm thành phần liên thông của đồ thị; kỹ thuật xây dựng giao diện ứng dụng trực quan bằng ngôn ngữ lập trình C#.
  • Phạm vi nghiên cứu: Kiến thức học thuật trong phạm vi học phần COMP170101 – Lý thuyết đồ thị và ứng dụng; môi trường lập trình C# kết hợp thư viện đồ họa Windows Forms trên hệ điều hành Windows; dữ liệu đầu vào là các đơn đồ thị có hướng hoặc vô hướng do người dùng trực tiếp khởi tạo trên phần mềm với kích thước ma trận kề tối đa $100 \times 100$.

Cơ sở lý thuyết và phương pháp

Khung lý thuyết của đề tài dựa trên nền tảng toán học rời rạc và các giải thuật đồ thị kinh điển:

  • Mô hình đồ thị:
    • Đồ thị vô hướng $G = (V, E)$ bao gồm tập đỉnh $V \neq \emptyset$ và đa tập hợp các cạnh $E$ là các cặp đỉnh không sắp thứ tự ${i, j}$.
    • Đồ thị có hướng $G = (V, E)$ gồm tập đỉnh $V \neq \emptyset$ và đa tập hợp các cung $E$ là các cặp đỉnh có sắp thứ tự $(i, j)$, không chứa các cạnh song song.
  • Phương pháp biểu diễn đồ thị: Sử dụng ma trận kề $A = [a_{ij}]{n \times n}$ cấp $n \times n$ (với $n$ là số lượng đỉnh của đồ thị). Giá trị phần tử $a{ij} = 1$ nếu tồn tại cạnh hoặc cung nối giữa đỉnh $i$ và đỉnh $j$, ngược lại $a_{ij} = 0$. Đối với đồ thị vô hướng, ma trận kề đối xứng qua đường chéo chính ($a_{ij} = a_{ji}$) và đường chéo chính chứa toàn giá trị 0 ($a_{ii} = 0$) do đồ thị không chứa khuyên.
  • Cơ chế giải thuật:
    • Thuật toán BFS: Vận hành dựa trên cấu trúc hàng đợi (Queue), xuất phát từ một đỉnh nguồn cho trước, thăm và đưa các đỉnh kề chưa duyệt vào hàng đợi để xử lý tuần tự, qua đó tạo ra cây khung duyệt theo chiều rộng.
    • Thuật toán DFS: Vận hành dựa trên cơ chế duyệt sâu theo từng nhánh bằng ngăn xếp (Stack) hoặc giải thuật đệ quy; thuật toán đi xa nhất có thể dọc theo mỗi nhánh trước khi thực hiện quay lui (backtrack).
    • Thuật toán tìm thành phần liên thông: Dựa trên nguyên lý đồ thị liên thông khi chỉ có duy nhất 1 thành phần liên thông (tồn tại đường đi giữa mọi cặp đỉnh). Giải thuật duyệt toàn bộ các đỉnh chưa thăm để gán nhãn từng miền liên thông riêng biệt.

Phương pháp nghiên cứu thực tế:

  • Phương pháp phân tích và tổng hợp: Phân tích các tài liệu lý thuyết đồ thị chuyên ngành, tổng hợp các bước thuật toán để chuẩn hóa logic toán học trước khi chuyển đổi sang ngôn ngữ máy.
  • Phương pháp mô hình hóa và lập trình thực nghiệm: Chuyển đổi mô hình toán học thành các lớp đối tượng, mảng dữ liệu và thuật toán điều khiển trong môi trường Visual Studio; hiện thực hóa các chức năng bằng ngôn ngữ C#.
  • Nguồn dữ liệu: Dữ liệu đồ thị động được người dùng khởi tạo thông qua tương tác trực tiếp (chuột và bàn phím) trên giao diện phần mềm, được lưu trữ nội bộ bằng mảng hai chiều biểu diễn ma trận kề và các danh sách liên kết lưu trữ tọa độ đỉnh, cạnh.

Thiết kế và triển khai hệ thống phần mềm

Đồ án triển khai một ứng dụng máy tính hoàn chỉnh trên nền tảng .NET Framework và Windows Forms với mã nguồn viết bằng ngôn ngữ C#.

Kiến trúc phần mềm và các lớp đối tượng

Hệ thống được thiết kế theo cấu trúc mô-đun hướng đối tượng, phân định giữa logic xử lý thuật toán đồ thị và giao diện trực quan:

  • Lớp dữ liệu và thuật toán (Class_FS_Graph): Chứa các cấu trúc con NodeGraph (lưu trữ tọa độ, chỉ số đỉnh) và Egde (lưu trữ cặp đỉnh và tọa độ đường nối). Lớp này đảm nhận việc chuyển đổi danh sách đỉnh/cạnh sang ma trận kề kích thước $100 \times 100$ (TaolaiMaTranCH, TaolaiMaTranVH), đồng thời chứa lớp Dothi thực thi giải thuật BFS, DFS và xét tính liên thông.
  • Lớp giao diện người dùng (Windows Forms):
    • Form1: Đóng vai trò giao diện chính (trang chủ) quản lý khung nhìn, thanh điều hướng bên trái (panelMenu), các nút chức năng và cơ chế nhúng các form con thông qua hàm openChildForm().
    • FormGraph: Form chịu trách nhiệm tương tác vẽ đồ thị, hiển thị ma trận kề và kích hoạt mô phỏng thuật toán.
    • FormMatrix: Form chuyên biệt hiển thị dữ liệu ma trận.
    • ThongTinSanPham: Form hiển thị thông tin học phần, giảng viên hướng dẫn và nhóm sinh viên thực hiện.

Công nghệ và thư viện hỗ trợ

  • Ngôn ngữ lập trình: C#.
  • Giao diện và đồ họa: Sử dụng System.Windows.Forms và thư viện đồ họa GDI+ (System.Drawing) với đối tượng Graphics và bút vẽ Pen để dựng đường thẳng (DrawLine), vẽ mũi tên đồ thị có hướng (DrawArrowhead), và gán màu sắc trực quan.
  • Thư viện ngoài: Sử dụng thư viện FontAwesome.Sharp để hiển thị các biểu tượng điều hướng trên các nút bấm giao diện (IconButton).
  • Tương tác hệ thống: Tích hợp thư viện liên kết động user32.DLL qua cơ chế P/Invoke với hai hàm API ReleaseCapture() và SendMessage() để cho phép người dùng kéo thả cửa sổ ứng dụng không viền thông qua tiêu đề form (pnlTittle).

Quy trình kiểm thử và phân bổ công việc

Quá trình triển khai phần mềm được phân chia cụ thể giữa các thành viên trong nhóm I_Lalisa_4:

STT Họ và tên Mã số sinh viên Nhiệm vụ đảm trách Kết quả tự đánh giá
1 Nguyễn Phước Thịnh 46.176 Lập trình mã nguồn chính, sửa lỗi thuật toán và giao diện Hoàn thành tốt
2 Nguyễn Huỳnh Thị Tuyết My 46.109 Thực hiện video demo, chỉnh sửa giao diện, kiểm thử chương trình, viết báo cáo Hoàn thành tốt
3 Khổng Tín Hào 46.048 Soạn thảo văn bản báo cáo đồ án Hoàn thành tốt
4 Dư Thị Như Quỳnh 46.151 Soạn thảo văn bản báo cáo đồ án Hoàn thành tốt

Công tác kiểm thử phần mềm được thực hiện xuyên suốt quá trình xây dựng chức năng, tập trung vào việc bắt lỗi thao tác người dùng (như chưa vẽ đỉnh mà bấm duyệt, chưa chọn cạnh cần xóa, đồ thị không tồn tại đường đi giữa hai đỉnh được chọn) và kiểm tra tính chính xác của các đường đi thuật toán trả về.

Nội dung chính theo từng chương

CHƯƠNG 1: TỔNG QUAN VỀ 1 SỐ KIẾN THỨC CỦA LÝ THUYẾT ĐỒ THỊ

Chương 1 hệ thống hóa toàn bộ lý thuyết nền tảng phục vụ cho việc xây dựng đồ án. Các nội dung chính bao gồm:

  • Định nghĩa đồ thị: Định nghĩa chi tiết về đồ thị vô hướng gồm tập đỉnh $V$ và tập cạnh $E$ không sắp thứ tự; định nghĩa đồ thị có hướng gồm tập đỉnh $V$ và tập các cung có sắp thứ tự, quy định rõ đồ thị có hướng trong đề tài không chứa cạnh song song.
  • Ma trận kề: Phân tích định nghĩa ma trận vuông $A = [a_{ij}]$ cấp $n \times n$. Nhấn mạnh hai tính chất toán học của ma trận kề đồ thị vô hướng: tính đối xứng qua đường chéo chính ($a_{ij} = a_{ji}$) và các phần tử trên đường chéo chính luôn bằng 0 ($a_{ii} = 0$) do đồ thị không có khuyên.
  • Thuật toán tìm kiếm theo chiều rộng (BFS): Nêu bản chất thuật toán duyệt dựa trên đỉnh gốc và danh sách đỉnh kề, chỉ rõ hai mục đích áp dụng gồm tìm đường đi từ đỉnh gốc tới một đỉnh đích và tìm đường đi tới tất cả các đỉnh còn lại. Các bước duyệt đồ thị liên thông $G = {v_1, v_2, \dots, v_n}$ được chuẩn hóa theo 4 bước lặp để thu được cây khung $T$.
  • Thuật toán tìm kiếm theo chiều sâu (DFS): Trình bày nguyên lý phát triển xa nhất theo từng nhánh xuất phát từ gốc, sử dụng cơ chế quay lui khi gặp đỉnh lá hoặc đỉnh đã duyệt. Mô tả thuật toán dưới hai dạng cài đặt (đệ quy và không đệ quy dùng ngăn xếp).
  • Đồ thị liên thông và các thành phần liên thông: Nêu định nghĩa đồ thị liên thông là đồ thị có duy nhất 1 thành phần liên thông (luôn có đường đi giữa hai đỉnh bất kỳ). Định nghĩa thành phần liên thông là các đồ thị con liên thông cực đại của một đồ thị không liên thông.

CHƯƠNG 2: MÔ PHỎNG THUẬT TOÁN BẰNG NGÔN NGỮ LẬP TRÌNH C#

Chương 2 trình bày chi tiết việc cài đặt các giải thuật đồ thị bằng mã nguồn C#:

  • Cài đặt thuật toán BFS: Sử dụng cấu trúc hàng đợi Queue<int> Q để quản lý các đỉnh chờ duyệt, mảng visited[] để đánh dấu các đỉnh đã xử lý, và mảng LuuVet[] để ghi nhận đỉnh cha phục vụ truy vết. Hàm duyetBFS(int s, int f) thực hiện khởi tạo mảng lưu vết với giá trị -1, gọi hàm BFS(s), sau đó truy hồi từ đỉnh đích f về đỉnh xuất phát s thông qua vòng lặp while (j != s) để tạo chuỗi kết quả đường đi.
  • Cài đặt thuật toán DFS: Sử dụng giải thuật đệ quy. Hàm DFS(int s) đánh dấu visited[s] = 1, duyệt qua các đỉnh kề $i$ từ $0$ đến sodinh - 1, ghi nhận LuuVet[i] = s và tiếp tục gọi đệ quy DFS(i). Hàm duyetDFS(int s, int f) quản lý việc khởi tạo và xuất kết quả chuỗi truy vết tương tự BFS.
  • Cài đặt thuật toán tìm thành phần liên thông: Hàm xetLT() khởi tạo mảng đánh dấu visited, đặt biến đếm miền liên thông nTPLT = 0. Vòng lặp duyệt qua các đỉnh, nếu phát hiện đỉnh chưa xét thì tăng biến nTPLT++ và gọi hàm duyệt để gán nhãn cho toàn bộ các đỉnh thuộc cùng thành phần liên thông đó. Hàm thanhPhanLienThong() trả về một mảng chuỗi string[] TPLT, trong đó phần tử TPLT[0] lưu tổng số miền liên thông và các phần tử tiếp theo lưu danh sách các đỉnh thuộc từng thành phần liên thông tương ứng.

CHƯƠNG 3: MINH HỌA TRỰC QUAN THUẬT TOÁN BẰNG GIAO DIỆN ĐỒ HỌA

Chương 3 mô tả chi tiết kiến trúc giao diện người dùng và cơ chế tương tác trực quan của phần mềm:

  • Giao diện trang chủ (Form1): Bố trí hiển thị logo Trường Đại học Sư phạm Thành phố Hồ Chí Minh, thông tin khoa, học phần, mã lớp và giảng viên hướng dẫn. Hệ thống menu phân cấp gồm ba khu vực chức năng: "Đồ thị", "Ma trận" và "Thông tin về sản phẩm". Giao diện được định dạng với bảng màu sắc tùy chỉnh qua cấu trúc RGBcolors và các hiệu ứng active nút bấm, hỗ trợ thu nhỏ (btnhide) và phóng to/phục hồi kích thước cửa sổ (btnZoom).
  • Giao diện thông tin sản phẩm (ThongTinSanPham): Được kích hoạt khi người dùng chọn mục tương ứng trên thanh điều hướng để xem thông tin chi tiết về đồ án.
  • Giao diện đồ thị và ma trận (FormGraph): Bao gồm các khối chức năng tương tác đồ họa hoàn chỉnh:
    • Vẽ đồ thị: Cho phép chọn loại đồ thị (có hướng hoặc vô hướng). Khi thêm đỉnh, người dùng kích hoạt nút "Thêm Đỉnh" (chuyển trạng thái sang nút "Dừng"), sau đó click chuột vào panel đồ họa (pnlVeDoThi) để tạo các đỉnh dưới dạng các nút bấm (Button). Khi xóa đỉnh, người dùng chọn đỉnh cần xóa và nhấn "Xóa", chương trình tự động xóa các cạnh liên quan và cập nhật lại ma trận kề.
    • Vẽ và xóa cạnh: Người dùng chọn lần lượt hai đỉnh và nhấn nút "Thêm Cạnh". Hệ thống kiểm tra tính hợp lệ bằng hàm check(x, y) để tránh vẽ cạnh trùng, sau đó dùng DrawLine (cho đồ thị vô hướng) hoặc vẽ thêm mũi tên với DrawArrowhead (cho đồ thị có hướng). Chức năng xóa cạnh cho phép loại bỏ liên kết giữa hai đỉnh đã chọn và gán lại giá trị 0 trong ma trận kề.
    • Chức năng duyệt và xét liên thông: Hỗ trợ ba chế độ: "Duyệt BFS", "Duyệt DFS" và "Xét Liên Thông". Đối với BFS/DFS, người dùng có thể chọn cách duyệt "Duyệt Toàn Bộ" (đánh dấu toàn bộ đường đi bằng hàm DanhDauDuongDiTB) hoặc "Duyệt Từng Bước" (đánh dấu từng bước chuyển tiếp qua hàm DanhDauDuongDiTB2). Đối với chức năng xét liên thông, phần mềm hiển thị số thành phần liên thông, liệt kê các đỉnh thuộc từng thành phần và sử dụng bút vẽ Pen với các màu sắc phân biệt để tô màu trực quan các thành phần liên thông trên bảng vẽ.
    • Hiển thị ma trận: Sau khi hoàn tất vẽ đồ thị, thao tác nhấn nút "Xác nhận" (btnXacNhan_Click) sẽ kích hoạt hàm tái tạo ma trận (TaolaiMaTranVH hoặc TaolaiMaTranCH), hiển thị toàn bộ ma trận số nhị phân lên khung hiển thị văn bản, đồng thời nạp dữ liệu vào lớp thuật toán để sẵn sàng duyệt.

Kết quả và đóng góp

Kết quả thực nghiệm của đồ án được thể hiện qua các sản phẩm cụ thể:

  • Ứng dụng phần mềm hoàn chỉnh: Xây dựng thành công ứng dụng trên Windows Forms cho phép người dùng tự do dựng đồ thị có hướng hoặc vô hướng trực quan bằng chuột, tự động sinh ma trận kề tương ứng, và mô phỏng chính xác đường đi theo thuật toán BFS, DFS cũng như xác định các thành phần liên thông.
  • Tính năng hiển thị hai chế độ: Triển khai thành công hai phương thức minh họa duyệt đồ thị gồm duyệt toàn bộ và duyệt từng bước, giúp người dùng nắm bắt được diễn biến từng bước nhảy của giải thuật.
  • Tính năng phân tách miền liên thông bằng màu sắc: Ứng dụng tự động nhận diện đồ thị liên thông hay không liên thông; trường hợp không liên thông, chương trình đếm chính xác số thành phần liên thông và tô màu đồ họa phân biệt giữa các nhóm đỉnh-cạnh thuộc các miền khác nhau.
  • Báo cáo và sản phẩm hỗ trợ: Nhóm sinh viên đã hoàn thành báo cáo chuyên đề chi tiết, sản phẩm video demo minh họa hoạt động của chương trình và tổ chức kiểm thử đầy đủ các chức năng.

Các giải pháp và đóng góp kỹ thuật:

  • Chuyển đổi trực tiếp giữa mô hình hình học và cấu trúc dữ liệu: Nhóm đã xây dựng cơ chế ánh xạ giữa các đối tượng nút bấm điều khiển trên panel (Button) với tọa độ đồ họa và ma trận kề nội bộ, loại bỏ sự phức tạp khi phải cấu hình đồ thị bằng văn bản thủ công.
  • Đóng góp trong học tập: Đồ án tạo ra một công cụ học tập trực quan phục vụ cho chính sinh viên học phần Lý thuyết đồ thị và ứng dụng, hỗ trợ đối chiếu kết quả tính toán lý thuyết trên giấy với mô phỏng thuật toán thực tế trên máy tính.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của đề tài (dựa trên phạm vi và mã nguồn văn bản):

  • Giới hạn kích thước ma trận: Cấu trúc ma trận kề trong mã nguồn được khởi tạo cố định ở kích thước $100 \times 100$ (Matrix = new int[100, 100]), chưa tối ưu hóa cấp phát bộ nhớ động khi số lượng đỉnh nhỏ hoặc mở rộng khi số lượng đỉnh vượt quá 100.
  • Phạm vi dạng đồ thị: Chương trình chỉ hỗ trợ đơn đồ thị vô hướng và có hướng với trọng số đơn vị (0 và 1), chưa hỗ trợ đồ thị có trọng số trên các cạnh, đa đồ thị hoặc đồ thị có khuyên.
  • Xử lý chuỗi truy vết: Thuật toán chuyển đổi đường đi sang chuỗi (kq += Convert.ToString(s)) dựa trên giả định chỉ số đỉnh là các ký tự đơn, có thể gây nhầm lẫn khi số đỉnh đạt từ 10 trở lên nếu không có ký tự phân tách rõ ràng.
  • Nền tảng công nghệ: Ứng dụng sử dụng Windows Forms truyền thống kết hợp thư viện đồ họa GDI+, phụ thuộc vào hệ điều hành Windows và chưa có khả năng triển khai đa nền tảng hoặc trên môi trường web.

Hướng nghiên cứu tiếp:

  • Mở rộng chức năng thuật toán: Bổ sung các giải thuật tìm đường đi ngắn nhất trên đồ thị có trọng số (thuật toán Dijkstra, thuật toán Bellman-Ford, thuật toán Floyd-Warshall) và các thuật toán tìm cây khung nhỏ nhất (Kruskal, Prim).
  • Cải tiến giao diện và tương tác: Nâng cấp đồ họa cho phép kéo thả di chuyển đỉnh trực tiếp trên bảng vẽ, hỗ trợ lưu/mở dữ liệu đồ thị từ các tệp định dạng chuẩn.

Giá trị tham khảo

Đồ án là tài liệu tham khảo hữu ích cho:

  • Sinh viên chuyên ngành Công nghệ Thông tin, Sư phạm Tin học và Kỹ thuật Phần mềm đang học tập học phần Lý thuyết đồ thị và ứng dụng hoặc Cấu trúc dữ liệu và giải thuật.
  • Người học lập trình C# Windows Forms: Tài liệu cung cấp các đoạn mã nguồn mẫu giá trị về kỹ thuật xử lý đồ họa GDI+ (vẽ đường thẳng, vẽ mũi tên định hướng, xử lý khử răng cưa AntiAlias), kỹ thuật gọi Windows API để tùy biến cửa sổ không viền (ReleaseCapture, SendMessage), và cách phân phối trạng thái nút bấm linh hoạt.
  • Giảng viên và trợ giảng: Có thể sử dụng phần mềm như một công cụ hỗ trợ trực quan trong các bài giảng lý thuyết để minh họa cách duyệt đồ thị theo chiều rộng, chiều sâu và phân rã các thành phần liên thông.

Câu hỏi thường gặp

Đồ án lưu trữ và biểu diễn dữ liệu đồ thị bên dưới giao diện như thế nào?

Dữ liệu đồ thị được biểu diễn thông qua ma trận kề hai chiều cấp $100 \times 100$ kiểu số nguyên (int[,] Matrix), kết hợp với hai danh sách đối tượng: ListarrNod (lưu trữ các đối tượng đỉnh NodeGraph chứa tọa độ $x, y$) và ListarrEgde (lưu trữ các đối tượng cạnh Egde). Khi người dùng thao tác vẽ hoặc xóa đỉnh/cạnh, hệ thống sẽ tự động gọi các hàm TaolaiMaTranVH() hoặc TaolaiMaTranCH() để đồng bộ lại các phần tử 0 và 1 trong ma trận kề.

Thuật toán BFS và DFS trong mã nguồn C# thực hiện truy vết đường đi giữa hai đỉnh ra sao?

Cả hai thuật toán đều sử dụng một mảng một chiều LuuVet[] có kích thước tương ứng số đỉnh, khởi tạo giá trị ban đầu là -1. Trong quá trình duyệt, khi đi từ đỉnh $s$ sang đỉnh $i$, giá trị LuuVet[i] = s được ghi nhận. Sau khi duyệt xong, nếu đỉnh đích $f$ đã được đánh dấu thăm (visited[f] == 1), hàm sẽ thực hiện vòng lặp truy vết ngược từ đỉnh đích j = f theo công thức j = LuuVet[j] cho đến khi gặp lại đỉnh xuất phát s, sau đó đảo ngược chuỗi để thu được lộ trình hoàn chỉnh.

Phần mềm xử lý việc phân biệt đồ thị có hướng và vô hướng khi vẽ cạnh như thế nào?

Khi người dùng chọn loại đồ thị tại cbxLoaiDoThi, hàm VeDoThi sẽ kiểm tra chuỗi lựa chọn:

  • Nếu là "Đồ thị Vô Hướng", hệ thống dùng bút vẽ Pen để vẽ một đường thẳng nối giữa hai tọa độ đỉnh bằng phương thức dc.DrawLine(BlackPen, NodeG.t) và cập nhật tính chất đối xứng trong ma trận: Matrix[Dinh1, Dinh2] = 1 và Matrix[Dinh2, Dinh1] = 1.
  • Nếu là "Đồ thị Có Hướng", hệ thống vẽ đường nối đồng thời gọi thêm hàm DrawArrowhead(dc, BlackPen, NodeG.t) để vẽ mũi tên chỉ hướng đi từ đỉnh đầu tới đỉnh cuối, và chỉ cập nhật một chiều trong ma trận: Matrix[Dinh1, Dinh2] = 1.

Cơ chế trực quan hóa các thành phần liên thông khác nhau trên màn hình hoạt động như thế nào?

Sau khi hàm thanhPhanLienThong() xác định được số miền liên thông và danh sách đỉnh thuộc từng miền, hàm btnDuyet_Click sẽ đọc dữ liệu từ mảng TPLT. Nếu đồ thị không liên thông, chương trình duyệt qua từng thành phần liên thông thứ $i$. Mỗi thành phần được gán một màu sắc riêng biệt bằng đối tượng bút vẽ Pen: với 5 thành phần đầu tiên dùng mảng màu cố định a[i - 1], các thành phần từ thứ 6 trở đi sẽ được sinh màu ngẫu nhiên qua hàm Random.Next(). Hệ thống sau đó gọi ResetLT(pen) để tô màu trực quan các đỉnh và cạnh thuộc cùng một thành phần liên thông trên giao diện.

Nhiệm vụ kiểm thử và xây dựng báo cáo được phân công cho những thành viên nào?

Công tác kiểm thử chương trình được giao cho sinh viên Nguyễn Huỳnh Thị Tuyết My (MSSV: 46.109), người đồng thời phụ trách làm video demo, đóng góp chỉnh sửa giao diện và viết báo cáo. Hai sinh viên Khổng Tín Hào (MSSV: 46.048) và Dư Thị Như Quỳnh (MSSV: 46.151) chịu trách nhiệm chính trong việc soạn thảo toàn bộ văn bản báo cáo đồ án. Mã nguồn chính và sửa lỗi thuật toán do sinh viên Nguyễn Phước Thịnh (MSSV: 46.176) phụ trách.

Kết luận

Đồ án môn học của nhóm sinh viên Trường Đại học Sư phạm Thành phố Hồ Chí Minh đã hiện thực hóa thành công các khái niệm lý thuyết đồ thị trừu tượng thành một công cụ phần mềm trực quan trên nền tảng C# Windows Forms. Sản phẩm đáp ứng đầy đủ các yêu cầu kỹ thuật về tạo lập ma trận kề, mô phỏng duyệt đồ thị theo chiều rộng, chiều sâu và phân tách các thành phần liên thông đồ thị bằng màu sắc đồ họa. Đây là một tài liệu học tập và nghiên cứu thực nghiệm hoàn chỉnh, mang tính ứng dụng rõ nét cho sinh viên ngành công nghệ thông tin trong việc tiếp cận môn học Lý thuyết đồ thị và ứng dụng.