Lý Thuyết Đồ Thị

Phân Loại Đồ Thị

• Đồ thị vô hướng: Cạnh không có hướng xác định
• Đồ thị có hướng: Cạnh xác định chiều đi giữa các đỉnh
• Đồ thị có trọng số: Cạnh mang giá trị trọng lượng

Bậc Đỉnh

• Vô hướng: Số cạnh nối với đỉnh
• Có hướng: Bao gồm bậc vào (số cạnh hướng tới) và bậc ra (số cạnh đi ra)

Tính Liên Thông

• Đồ thị liên thông (vô hướng): Mọi cặp đỉnh có đường nối
• Đồ thị liên thông mạnh (có hướng): Mọi cặp đỉnh có đường đi hai chiều
• Thành phần liên thông: Tập con liên thông cực đại

Biểu Diễn Đồ Thị

Ma trận kề: Dùng mảng 2 chiều kích thước V×V

• Ưu điểm: Kiểm tra cạnh nhanh, phù hợp đồ thị dày
• Nhược điểm: Tốn bộ nhớ với đồ thị thưa

Danh sách kề: Mảng kết hợp danh sách liên kết

• Ưu điểm: Tiết kiệm bộ nhớ, duyệt láng giềng hiệu quả
• Nhược điểm: Kiểm tra cạnh chậm hơn

Phương Pháp Duyệt

• Tìm kiếm theo chiều sâu (DFS)
• Tìm kiếm theo chiều rộng (BFS)

Tìm Kiếm Theo Chiều Sâu (DFS)

Khác Biệt với BFS

• DFS: Duyệt sâu theo nhánh, sử dụng backtracking khi gặp ngõ cụt
• BFS: Duyệt theo tầng, xử lý toàn bộ đỉnh cùng mức

Khung Thuật Toán DFS

void dfs(Tham số) {
  if (Điều kiện dừng) {
    Lưu kết quả;
    return;
  }
  for (Đỉnh kề : danh sách kề) {
    Xử lý đỉnh;
    dfs(Đồ thị, đỉnh kề);
    Hoàn tác xử lý; // Backtrack
  }
}

Bài Toán: Tìm Tất Cả Đường Đi

Khởi Tạo Đồ Thị

Ma trận kề:

int[][] maTran = new int[soDinh + 1][soDinh + 1];
for (int i = 0; i < soCanh; i++) {
  int diemDau = scanner.nextInt();
  int diemCuoi = scanner.nextInt();
  maTran[diemDau][diemCuoi] = 1;
}

Danh sách kề:

List<List<Integer>> dsKe = new ArrayList<>(soDinh + 1);
for (int i = 0; i <= soDinh; i++) {
  dsKe.add(new ArrayList<>());
}
while (soCanh-- > 0) {
  int diemDau = scanner.nextInt();
  int diemCuoi = scanner.nextInt();
  dsKe.get(diemDau).add(diemCuoi);
}

Thuật Toán DFS

Với ma trận kề:

void timDuong(int[][] maTran, int dinhHienTai, int dich) {
  if (dinhHienTai == dich) {
    ketQua.add(new ArrayList<>(duongDi));
    return;
  }
  for (int i = 1; i <= tongDinh; i++) {
    if (maTran[dinhHienTai][i] == 1) {
      duongDi.add(i);
      timDuong(maTran, i, dich);
      duongDi.remove(duongDi.size() - 1);
    }
  }
}

Với danh sách kề:

void timDuong(List<List<Integer>> dsKe, int dinhHienTai, int dich) {
  if (dinhHienTai == dich) {
    ketQua.add(new ArrayList<>(duongDi));
    return;
  }
  for (int ke : dsKe.get(dinhHienTai)) {
    duongDi.add(ke);
    timDuong(dsKe, ke, dich);
    duongDi.remove(duongDi.size() - 1);
  }
}

Thực Thi Chương Trình

public class TimDuong {
  static List<List<Integer>> ketQua = new ArrayList<>();
  static List<Integer> duongDi = new ArrayList<>();
  
  public static void main(String[] args) {
    // Khởi tạo đồ thị (chọn 1 trong 2 cách)
    duongDi.add(1); // Bắt đầu từ đỉnh 1
    timDuong(doThi, 1, dich); // Gọi DFS
    
    if (ketQua.isEmpty()) System.out.println(-1);
    for (List<Integer> p : ketQua) {
      // In kết quả
    }
  }
}