06. Graphs (Đồ thị)

🎯 Mục tiêu học tập

  • Hiểu khái niệm graph và cách biểu diễn
  • Cài đặt DFS và BFS
  • Thuật toán shortest path, MST
  • Ứng dụng graph vào bài toán thực tế

📚 Lý thuyết cơ bản

Graph là gì?

Định nghĩa: Tập hợp vertices (đỉnh) và edges (cạnh) kết nối chúng. G = (V, E) với V là vertices, E là edges.

Phân loại:

  • Directed vs Undirected: Có hướng hay vô hướng
  • Weighted vs Unweighted: Có trọng số hay không
  • Connected vs Disconnected: Liên thông hay không
  • Cyclic vs Acyclic: Có chu trình hay không

🏗️ Cách biểu diễn

1. Adjacency Matrix

int[][] adjMatrix = new int[V][V];
// adjMatrix[i][j] = 1 nếu có edge từ i → j

2. Adjacency List

List<List<Integer>> adjList = new ArrayList<>();
// adjList.get(i) = danh sách neighbors của vertex i

3. Edge List

List<Edge> edges = new ArrayList<>();
// Danh sách tất cả edges

🔍 Graph Traversal

1. Depth-First Search (DFS)

// Dùng Stack hoặc Recursion
// Đi sâu trước khi backtrack

2. Breadth-First Search (BFS)

// Dùng Queue
// Duyệt theo level/distance

🛣️ Shortest Path Algorithms

1. Dijkstra's Algorithm

  • Single-source shortest path
  • Positive weights only
  • Time: O(V²) hoặc O(E log V) với priority queue

2. Bellman-Ford Algorithm

  • Single-source shortest path
  • Có thể có negative weights
  • Detect negative cycles

3. Floyd-Warshall Algorithm

  • All-pairs shortest path
  • Time: O(V³)

🌲 Minimum Spanning Tree (MST)

1. Kruskal's Algorithm

  • Sort edges by weight
  • Use Union-Find to avoid cycles

2. Prim's Algorithm

  • Start from any vertex
  • Greedily add minimum weight edge

📋 Bài tập thực hành

  1. Implement graph representations
  2. DFS và BFS traversal
  3. Detect cycle trong graph
  4. Shortest path algorithms
  5. MST algorithms
  6. Topological sorting

🚀 Chuẩn bị code

mkdir 06-graphs
# Files: Graph.java, GraphTraversal.java, ShortestPath.java, MST.java