README.md

Graph

Phân loại

• Đơn đồ thị, đa đồ thị
• Vô hướng, có hướng
• Có trọng số, không có trọng số

Thuật ngữ

• Cạnh
• Đỉnh
• Cạnh liên thuộc, đỉnh kề
• Đường đi
• Chu trình
• Bậc của đỉnh (graph vô hướng)
• Bán bậc ra, bán bậc vào (graph có hướng)
• Tính liên thông (graph vô hướng)
• Liên thông mạnh, yếu (graph có hướng)

Cài đặt

• Ma trận kề
• Danh sách kề

Thuật toán

• Duyệt graph: bfs, dfs
• Kiểm tra chu trình, tìm đường đi, tính bậc của đỉnh
• Topology sort
• Kosaraju: tìm thành phần liên thông mạnh
• Kiểm tra đồ thị lưỡng cực
• Tìm đỉnh cầu, cạnh cầu
• Tìm chu trình Euler
• Cây khung nhỏ nhất: Kruskal, Prim
• Đường đi ngắn nhất: Dijkstra