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

Lý thuyết đồ thị là một phân ngành toán học rời rạc và cấu trúc dữ liệu cơ bản trong khoa học máy tính, cung cấp các mô hình toán học để biểu diễn các mối quan hệ nhị phân giữa các đối tượng. Trong thực tế phát triển phần mềm và tối ưu hóa hệ thống, các bài toán tìm đường đi ngắn nhất, duyệt mạng lưới, phân tích tính liên thông và xây dựng cây khung nhỏ nhất đòi hỏi những cấu trúc dữ liệu lưu trữ và giải thuật xử lý có hiệu năng xác định. Đề tài tập trung vào việc hiện thực hóa các thuật toán lý thuyết đồ thị cơ bản và nâng cao thông qua ngôn ngữ lập trình hướng đối tượng Java, sử dụng mô hình ma trận kề làm cấu trúc biểu diễn trung tâm.

Mục tiêu và nhiệm vụ nghiên cứu của đề tài bao gồm:

  1. Xây dựng lớp trừu tượng cơ sở Graphs để quản lý các thuộc tính cốt lõi của đồ thị gồm số đỉnh, ma trận trọng số và các phương thức tải dữ liệu từ tệp tin văn bản thông qua luồng nhập xuất FileReader và BufferedReader.
  2. Hiện thực hóa các giải thuật duyệt đồ thị kinh điển bao gồm duyệt theo chiều sâu (Depth-First Search - DFS) sử dụng ngăn xếp (Stack) và duyệt theo chiều rộng (Breadth-First Search - BFS) sử dụng hàng đợi (Queue).
  3. Cài đặt các thuật toán kiểm tra tính hợp lệ, tính đối xứng của đồ thị vô hướng, tính liên thông và đếm số lượng thành phần liên thông (soThanphanlienthong).
  4. Thiết kế các giải thuật tìm cây bao trùm (Spanning Tree) bằng phương pháp DFS, BFS và các thuật toán tìm cây khung nhỏ nhất (Minimum Spanning Tree - MST) theo thuật toán Kruskal và thuật toán Prim.
  5. Triển khai thuật toán tìm đường đi ngắn nhất Dijkstra từ một đỉnh nguồn đến tất cả các đỉnh còn lại, kết hợp truy vết đường đi thông qua mảng phụ trợ.
  6. Mở rộng lớp Directedgraph kế thừa từ Graphs để xử lý đồ thị có hướng, bao gồm tính toán bậc vào (degIn), bậc ra (degOut), tổng bậc, kiểm tra tính liên thông mạnh (isconecstrongly), cùng việc xác định và tìm chu trình/đường đi Euler (findEulerCycle, findEulerPath).

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

  • Đối tượng nghiên cứu: Các cấu trúc dữ liệu biểu diễn đồ thị (ma trận kề int[][] maxtrix), danh sách cạnh (Edges), và tập hợp các giải thuật đồ thị thuần túy trong môi trường Java SE.
  • Phạm vi nghiên cứu: Giới hạn trong đồ thị hữu hạn đỉnh, biểu diễn dưới dạng ma trận vuông cấp $N \times N$, áp dụng cho cả đồ thị vô hướng và đồ thị có hướng, đồ thị có trọng số không âm đối với bài toán tìm đường đi ngắn nhất và cây khung.

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

Khung lý thuyết của đề tài dựa trên lý thuyết đồ thị trừu tượng $G = (V, E)$, trong đó $V$ là tập đỉnh có kích thước $|V| = \text{numvext}$ và $E$ là tập cạnh nối các đỉnh. Cấu trúc lưu trữ được lựa chọn là ma trận kề $A$ kích thước $n \times n$, trong đó phần tử $A[i][j]$ biểu diễn sự tồn tại của cạnh nối từ đỉnh $i$ đến đỉnh $j$ hoặc trọng số của cạnh đó.

Các nguyên lý thuật toán được sử dụng gồm:

  • Nguyên lý duyệt đồ thị: Duyệt theo chiều sâu DFS dựa trên cấu trúc LIFO (Last-In-First-Out) hoặc đệ quy; duyệt theo chiều rộng BFS dựa trên cấu trúc FIFO (First-In-First-Out) để thăm các đỉnh theo từng mức khoảng cách.
  • Nguyên lý cây khung và tối ưu hóa cây khung: Cây khung của đồ thị liên thông $n$ đỉnh là một đồ thị con liên thông chứa toàn bộ $n$ đỉnh và đúng $n - 1$ cạnh không chứa chu trình. Thuật toán Kruskal tiếp cận theo hướng tham lam (greedy) trên tập cạnh đã sắp xếp tăng dần trọng số; thuật toán Prim phát triển cây khung từ một đỉnh gốc bằng cách liên tục bổ sung cạnh có trọng số nhỏ nhất nối từ tập đỉnh đã xét sang tập đỉnh chưa xét.
  • Nguyên lý đường đi ngắn nhất Dijkstra: Sử dụng mảng khoảng cách $L$, mảng truy vết $P$ và tập đỉnh đã tối ưu $R$ để xác định đường đi có tổng trọng số nhỏ nhất từ đỉnh nguồn $s$.
  • Định lý Euler cho đồ thị có hướng: Đồ thị có hướng liên thông mạnh có chu trình Euler khi và chỉ khi mọi đỉnh $v$ đều thỏa mãn bán bậc vào bằng bán bậc ra ($\text{degIn}(v) = \text{degOut}(v)$). Đồ thị có đường đi Euler khi tồn tại duy nhất một đỉnh có $\text{degOut} - \text{degIn} = 1$ (đỉnh bắt đầu) và một đỉnh có $\text{degIn} - \text{degOut} = 1$ (đỉnh kết thúc), các đỉnh còn lại có bán bậc vào bằng bán bậc ra.

Phương pháp nghiên cứu và phát triển:

  • Phương pháp phân tích thiết kế hướng đối tượng (OOP): Phân tách hệ thống thành lớp trừu tượng cơ sở Graphs, lớp thực thể dữ liệu cạnh Edges, và lớp chuyên biệt Directedgraph.
  • Phương pháp thực nghiệm thuật toán: Đọc dữ liệu từ file văn bản phẳng thông qua BufferedReader, nạp trực tiếp vào ma trận 2 chiều int[][], kiểm thử các trường hợp dữ liệu đồ thị liên thông, không liên thông, đơn đồ thị và đa đồ thị.

Thiết kế và triển khai

Hệ thống mã nguồn được tổ chức theo cấu trúc phân cấp lớp trong Java, quản lý các tác vụ từ xử lý dữ liệu đầu vào đến thực thi giải thuật tính toán.

Tên lớp / Cấu trúc Kiểu thành phần Thuộc tính chính Phương thức / Chức năng chính
Graphs abstract class int numvext
int[][] maxtrix
int v		 load(String pATH)
checkValid(int[][] matrix)
checkUnGraph(int[][] matrix)
DFSGraph(int[][] matrix, int startVex)
BFSGraph(int[][] matrix, int v)
soThanphanlienthong()
SpanningTreeByKruskal(int[][] matrix)
SpanningTreeByPrim(int[][] matrix, int verStart)
Dijkstra(int[][] matrix, int s)
Edges class int x
int y
int w		 getX(), getY(), getW()
setX(int), setY(int), setW(int)
toString()
Directedgraph class (kế thừa Graphs) int[][] P
private int[] path1
private int count		 numEdges()
degIn(int v), degOut(int v)
isconecstrongly(int[][] matrix)
isEulerGraph(int[][] matrix)
isHalfEulerGraph(int[][] matrix)
findEulerCycle(int[][] matrix)
findEulerPath(int[][] matrix)

Quy trình nạp dữ liệu và thực thi giải thuật:

  1. Khởi tạo và đọc file: Phương thức load(String pATH) mở file qua FileReader, sử dụng BufferedReader.readLine() để đọc số lượng đỉnh numvext, khởi tạo ma trận maxtrix = new int[numvext][numvext], sau đó phân tách chuỗi theo ký tự khoảng trắng split("\\s") để điền các giá trị số nguyên vào từng hàng của ma trận.
  2. Kiểm tra tính hợp lệ: Phương thức checkUnGraph duyệt toàn bộ các cặp chỉ số $(i, j)$ để kiểm tra tính đối xứng $A[i][j] = A[j][i]$.
  3. Quản lý cạnh: Lớp Edges lưu trữ bộ ba $(x, y, w)$ đại diện cho đỉnh đầu, đỉnh cuối và trọng số, phục vụ cơ chế sắp xếp thông qua giao diện Comparator<Edges> trong thuật toán Kruskal.

Nội dung chính theo từng phân hệ thuật toán

Cấu trúc cơ sở và các phép toán cơ bản trên đồ thị (Graphs)

Lớp trừu tượng Graphs đóng vai trò là khung chứa toàn bộ các thuộc tính nền tảng và các giải thuật tổng quát không phụ thuộc vào hướng của cạnh. Ma trận kề maxtrix được cấp phát động dựa trên giá trị numvext. Các hàm kiểm tra cơ bản bao gồm checkValid kiểm tra tính hợp lệ của đường chéo chính và checkUnGraph xác định đồ thị vô hướng.

Về quản lý bậc và liên thông, lớp cung cấp phương thức diTimcacDinhLienThong sử dụng đệ quy để lan truyền nhãn thành phần liên thông trong mảng arr. Phương thức soThanphanlienthong duyệt qua tất cả các đỉnh chưa được đánh dấu để tăng biến đếm stplt và gán nhãn toàn bộ các đỉnh thuộc cùng một thành phần liên thông.

Các giải thuật duyệt đồ thị và tìm kiếm đường đi

Mã nguồn cài đặt hai kỹ thuật duyệt không đệ quy thông qua các cấu trúc dữ liệu của thư viện java.util:

  • Duyệt theo chiều sâu DFSGraph: Sử dụng Stack<Integer> để lưu trữ đỉnh đang xét. Một mảng boolean visited kích thước numvext được khởi tạo với giá trị false. Đỉnh xuất phát startVex được đẩy vào ngăn xếp. Trong vòng lặp while (!stack.isEmpty()), phần tử đỉnh được lấy ra bằng pop(), đánh dấu đã thăm, ghi nhận vào mảng kết quả result, và duyệt qua các đỉnh kề chưa thăm để đưa tiếp vào ngăn xếp.
  • Duyệt theo chiều rộng BFSGraph: Sử dụng hàng đợi Queue<Integer> (khởi tạo qua LinkedList). Đỉnh xuất phát được đưa vào hàng đợi bằng offer(). Các đỉnh kề chưa thăm lần lượt được thăm và đưa vào hàng đợi, tạo thứ tự duyệt theo từng lớp khoảng cách.
  • Tìm đường đi giữa hai đỉnh findPathTwoVexs: Sử dụng Stack và danh sách động ArrayList<Integer> để lần vết các đỉnh kề có kết nối từ đỉnh xuất phát $s$ đến khi gặp đỉnh đích $t$.

Các thuật toán xây dựng cây bao trùm (Spanning Tree)

Phân hệ cây bao trùm cung cấp cả phương pháp duyệt cây khung không trọng số và cây khung nhỏ nhất có trọng số:

  • Cây khung DFS/BFS: Phương thức SpanningTree (kết hợp visetDFS) và SpanningBFS xây dựng ma trận kề mới tree kích thước $N \times N$, chỉ thêm cạnh addEdge(tree, u, v) khi cạnh đó dẫn tới một đỉnh chưa được viếng thăm (visited[i] == false), đồng thời in ra màn hình tiến trình duyệt cạnh dạng (u + 1)----->(i + 1).
  • Thuật toán Kruskal (SpanningTreeByKruskal): Trích xuất toàn bộ các cạnh có trọng số dương vào danh sách ArrayList<Edges>, sắp xếp danh sách tăng dần theo trọng số $w$ bằng bộ so sánh Comparator<Edges>. Vòng lặp duy trì việc chọn cạnh kế tiếp không tạo chu trình (thông qua hàm checkCycle1) cho đến khi số cạnh trong cây đạt $\text{numvext} - 1$. Trọng số được cập nhật vào ma trận kết quả bằng hàm addweight.
  • Thuật toán Prim (SpanningTreeByPrim): Sử dụng cấu trúc LinkedList<Integer> để lưu trữ tập các đỉnh đã kết nối vào cây khung. Tại mỗi bước, thuật toán duyệt qua toàn bộ các đỉnh đã có trong danh sách, tìm cạnh nối có trọng số min nhỏ nhất dẫn tới một đỉnh chưa thuộc danh sách (!linkedList.contains(i)), sau đó bổ sung đỉnh mới $v$ vào danh sách, tăng biến đếm edge và cộng dồn trọng số vào biến sum.

Thuật toán tìm đường đi ngắn nhất Dijkstra

Mô-đun đường đi ngắn nhất khởi tạo ba mảng trạng thái với kích thước bằng số đỉnh numvext:

  • Mảng khoảng cách $L$: Khởi tạo giá trị Integer.MAX_VALUE cho mọi đỉnh, ngoại trừ $L[s] = 0$.
  • Mảng đỉnh liền trước $P$: Khởi tạo bằng $-1$ cho mọi đỉnh.
  • Mảng trạng thái tối ưu $R$: Khởi tạo false cho mọi đỉnh.

Vòng lặp thực hiện $\text{numvext}$ lần, mỗi bước tìm chỉ số indexMin có $L[\text{indexMin}]$ nhỏ nhất trong số các đỉnh chưa cố định ($!R[i]$). Sau khi cố định $R[\text{indexMin}] = \text{true}$, thuật toán duyệt qua các đỉnh kề để thực hiện bước tối ưu hóa: $$L[i] > L[\text{indexMin}] + \text{matrix}[\text{indexMin}][i] \implies L[i] = L[\text{indexMin}] + \text{matrix}[\text{indexMin}][i], \quad P[i] = \text{indexMin}$$ Kết quả đường đi từ $s$ đến mọi đỉnh $i$ được tái hiện qua hàm đệ quy/lặp printPath(P, L, s, i).

Xử lý đồ thị có hướng và giải thuật Euler (Directedgraph)

Lớp Directedgraph hiện thực các đặc trưng riêng của đồ thị có hướng:

  • Tính bậc: Bậc vào degIn(v) được tính bằng tổng các phần tử trên cột $v$ của ma trận kề ($\sum_{i} \text{matrix}[i][v]$). Bậc ra degOut(v) được tính bằng tổng các phần tử trên hàng $v$ ($\sum_{j} \text{matrix}[v][j]$). Tổng bậc deg(v) được tính bằng tổng của bậc vào và bậc ra.
  • Tính liên thông mạnh: Phương thức isconecstrongly thực hiện duyệt DFS từ các đỉnh để kiểm tra xem từ mỗi đỉnh có thể đi tới toàn bộ các đỉnh còn lại hay không thông qua mảng đánh dấu vised.
  • Chu trình và đường đi Euler:
    • isEulerGraph: Kiểm tra điều kiện đồ thị liên thông mạnh và mọi đỉnh đều có $\text{degIn}(i) == \text{degOut}(i)$.
    • isHalfEulerGraph: Kiểm tra điều kiện đồ thị có đường đi Euler thông qua hàm condition(), yêu cầu tồn tại duy nhất một đỉnh thỏa mãn $\text{degIn} = \text{degOut} + 1$ và duy nhất một đỉnh thỏa mãn $\text{degOut} = \text{degIn} + 1$.
    • findEulerCycle và findEulerPath: Thực hiện xóa dần các cạnh đã đi qua trên bản sao của ma trận (copy[u][v] = 0) và lưu trữ thứ tự các đỉnh đi qua vào danh sách ArrayList<Integer>.

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

Đề tài đã xây dựng thành công bộ thư viện mã nguồn Java hoàn chỉnh, tích hợp đầy đủ các chức năng xử lý đồ thị cơ bản và nâng cao dựa trên cấu trúc ma trận kề.

Nhóm chức năng Tên phương thức / Thuật toán đã cài đặt Cấu trúc dữ liệu hỗ trợ Trạng thái thực thi
Nhập xuất & Quản lý load, printmatrix, addEdge, removeEdge BufferedReader, FileReader, int[][] Đọc ma trận từ file văn bản
Duyệt đồ thị DFSGraph, BFSGraph, DFSRe Stack<Integer>, Queue<Integer>, boolean[] Duyệt lặp và duyệt đệ quy
Phân tích liên thông soThanphanlienthong, isConnected, isconecstrongly int[] index, boolean[] visited Phân rã thành phần và kiểm tra liên thông
Cây bao trùm SpanningTreeByKruskal, SpanningTreeByPrim ArrayList<Edges>, Comparator, LinkedList Xây dựng MST và tính tổng trọng số
Tối ưu đường đi Dijkstra, findPathTwoVexs, printPath int[] L, int[] P, boolean[] R Tìm khoảng cách và in chuỗi đỉnh
Đồ thị Euler findEulerCycle, findEulerPath, isEulerGraph ArrayList<Integer>, int[][] copy Kiểm tra điều kiện và truy vết chu trình/đường đi

Đóng góp kỹ thuật của mã nguồn:

  • Đóng gói toàn bộ các thuật toán đồ thị trong cấu trúc hướng đối tượng có tính kế thừa rõ ràng giữa lớp trừu tượng Graphs và lớp dẫn xuất Directedgraph.
  • Hiện thực trực tiếp các thuật toán MST (Kruskal, Prim) và đường đi ngắn nhất (Dijkstra) từ cấu trúc dữ liệu mảng nguyên thủy kết hợp với các cấu trúc tập hợp chuẩn của Java SE (Stack, Queue, ArrayList, LinkedList) mà không cần sử dụng thư viện đồ thị bên ngoài.

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

Hạn chế trong phạm vi mã nguồn hiện tại:

  • Biểu diễn ma trận kề int[][] tiêu tốn bộ nhớ $O(V^2)$, chưa tối ưu cho các đồ thị thưa (sparse graphs) có số lượng đỉnh lớn.
  • Các phương thức xử lý ngoại lệ trong quá trình đọc file load(String pATH) chỉ dừng lại ở mức in thông báo lỗi System.out.println("error!!"), chưa có cơ chế bắt lỗi chi tiết hoặc phục hồi dữ liệu khi định dạng file sai.
  • Một số phương thức liên quan đến chu trình và đường đi Hamilton (hamCycle, HamiltonPath, KiemtraIshamition) mới chỉ được khai báo dưới dạng phương thức trừu tượng trong lớp Graphs, chưa được hiện thực chi tiết trong lớp con Directedgraph.

Hướng phát triển tiếp theo:

  • Bổ sung cấu trúc biểu diễn danh sách kề (ArrayList<LinkedList<Integer>> hoặc HashMap) để tối ưu hóa không gian lưu trữ và thời gian duyệt cho đồ thị thưa.
  • Hoàn thiện cài đặt giải thuật quay lui (Backtracking) để tìm đường đi và chu trình Hamilton đã được định nghĩa trong giao diện trừu tượng.

Giá trị tham khảo

Tài liệu và bộ mã nguồn này có giá trị tham khảo thiết thực cho:

  • Sinh viên chuyên ngành Công nghệ thông tin, Khoa học máy tính đang học các học phần Cấu trúc dữ liệu và giải thuật, Toán rời rạc hoặc Lập trình Java nâng cao.
  • Lập trình viên cần tài liệu tham khảo về việc cài đặt thủ công các giải thuật tối ưu hóa đồ thị (Dijkstra, Kruskal, Prim, Euler) bằng ngôn ngữ Java SE.
  • Phân đoạn mã nguồn đáng tham khảo nhất là cách tổ chức cấu trúc dữ liệu phụ trợ trong thuật toán Prim (SpanningTreeByPrim) và thuật toán Kruskal (SpanningTreeByKruskal kết hợp lớp Edges), cùng logic kiểm tra điều kiện bán bậc đồ thị Euler trong lớp Directedgraph.

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

1. Cấu trúc dữ liệu nào được sử dụng để đọc và lưu trữ ma trận kề từ tệp tin?
Dữ liệu được nạp thông qua lớp FileReader và BufferedReader trong gói java.io. Dòng đầu tiên đọc kích thước numvext, các dòng tiếp theo được phân tách bằng biểu thức chính quy \\s thông qua phương thức split và lưu trữ trực tiếp vào mảng hai chiều int[][] maxtrix.

2. Thuật toán Kruskal trong mã nguồn sắp xếp các cạnh bằng cách nào?
Mã nguồn sử dụng danh sách ArrayList<Edges> để chứa các đối tượng cạnh Edges(i, j, weight). Danh sách này được sắp xếp thông qua phương thức sort kết hợp với đối tượng Comparator<Edges> ghi đè phương thức compare dựa trên giá trị trọng số o1.w.

3. Làm thế nào để thuật toán Dijkstra trong mã nguồn xác định một đỉnh đã đạt khoảng cách tối ưu?
Thuật toán sử dụng một mảng boolean R có kích thước bằng số đỉnh numvext. Ban đầu mọi phần tử của R đều là false. Trong mỗi bước lặp, đỉnh có nhãn khoảng cách $L$ nhỏ nhất chưa được chọn sẽ được gán R[indexMin] = true và biến đếm countR giảm đi 1 đơn vị.

4. Điều kiện để đồ thị có hướng được xác định là nửa Euler (Half-Euler) trong phương thức condition() là gì?
Phương thức condition() kiểm tra xem đồ thị có đúng một đỉnh thỏa mãn $\text{degIn} = \text{degOut} + 1$ (biến count == 1) và đúng một đỉnh thỏa mãn $\text{degOut} = \text{degIn} + 1$ (biến count1 == 1), đồng thời các đỉnh còn lại phải có bán bậc vào bằng bán bậc ra.

5. Điểm khác biệt giữa hai phương thức duyệt DFS được cài đặt trong lớp Graphs là gì?
Phương thức DFSGraph sử dụng ngăn xếp tường minh Stack<Integer> để duyệt toàn bộ đồ thị theo cơ chế khử đệ quy, trong khi phương thức visetDFS sử dụng kỹ thuật đệ quy trực tiếp để đồng thời duyệt và ghi nhận các cạnh thuộc cây bao trùm vào ma trận kết quả tree.

Kết luận

Đề tài đã triển khai toàn diện cấu trúc dữ liệu và tập giải thuật xử lý lý thuyết đồ thị bằng ngôn ngữ Java thông qua mô hình kế thừa hướng đối tượng. Các thuật toán nền tảng từ duyệt DFS/BFS, phân tích liên thông, tìm cây khung nhỏ nhất Prim/Kruskal, đường đi ngắn nhất Dijkstra đến kiểm tra chu trình Euler trên đồ thị có hướng đều được hiện thực hóa trực tiếp trên ma trận kề. Hệ thống cung cấp cơ sở thực thi chuẩn xác, phục vụ hiệu quả cho việc nghiên cứu và ứng dụng giải thuật toán rời rạc trong lập trình máy tính.