Toán tin vuotlen.com

Đồ thị (Graph)

Cấu trúc dữ liệu đồ thị (Graph Data Structure) là một cấu trúc dữ liệu được sử dụng để mô hình hóa các quan hệ giữa các đối tượng. Đồ thị bao gồm một tập hợp các đỉnh (vertices hoặc nodes) và một tập hợp các cạnh (edges) kết nối các đỉnh đó.

Các thành phần chính của đồ thị:

  1. Đỉnh (Vertex hoặc Node): Đỉnh là một phần tử cơ bản của đồ thị, đại diện cho một đối tượng trong hệ thống. Mỗi đỉnh có thể mang thông tin riêng biệt.

  2. Cạnh (Edge): Cạnh là liên kết giữa hai đỉnh, đại diện cho một mối quan hệ giữa hai đối tượng. Cạnh có thể là có hướng (directed) hoặc vô hướng (undirected).

Các loại đồ thị:

  1. Đồ thị vô hướng (Undirected Graph): Các cạnh trong đồ thị không có hướng. Nếu có cạnh giữa hai đỉnh A và B, thì ta có thể đi từ A đến B và ngược lại.

  2. Đồ thị có hướng (Directed Graph hoặc Digraph): Các cạnh trong đồ thị có hướng. Mỗi cạnh được biểu diễn bởi một cặp có thứ tự, ví dụ từ đỉnh A đến đỉnh B.

  3. Đồ thị có trọng số (Weighted Graph): Mỗi cạnh trong đồ thị có một trọng số (weight) gắn liền, biểu thị mức độ hoặc chi phí để di chuyển giữa hai đỉnh.

Cách biểu diễn đồ thị:

  1. Danh sách kề (Adjacency List): Mỗi đỉnh lưu trữ danh sách các đỉnh kề của nó. Đây là cách biểu diễn tiết kiệm không gian cho đồ thị thưa (sparse graph).

    Ví dụ:

    0: 1, 2
    1: 0, 3
    2: 0, 3
    3: 1, 2

  2. Ma trận kề (Adjacency Matrix): Một ma trận 2 chiều, trong đó mỗi hàng và mỗi cột tương ứng với một đỉnh, và giá trị tại vị trí (i, j) biểu diễn cạnh từ đỉnh i đến đỉnh j. Cách biểu diễn này tốn nhiều không gian hơn nhưng cho phép truy cập nhanh.

    Ví dụ:

    (Ma trận kề cho đồ thị vô hướng)
      0 1 2 3
    0 0 1 1 0
    1 1 0 0 1
    2 1 0 0 1
    3 0 1 1 0

  3. Danh sách cạnh (Edge List): Một danh sách các cạnh, mỗi cạnh là một cặp đỉnh. Cách biểu diễn này thích hợp cho các thuật toán duyệt cạnh.

    Ví dụ:

    
(0, 1), (0, 2), (1, 3), (2, 3)

Các thao tác cơ bản trên đồ thị:

  1. Thêm đỉnh: Thêm một đỉnh mới vào đồ thị.
  2. Thêm cạnh: Thêm một cạnh mới giữa hai đỉnh.
  3. Xóa đỉnh: Xóa một đỉnh và các cạnh liên quan.
  4. Xóa cạnh: Xóa một cạnh giữa hai đỉnh.
  5. Duyệt đồ thị: Sử dụng các thuật toán duyệt như BFS (Breadth-First Search) và DFS (Depth-First Search) để thăm tất cả các đỉnh của đồ thị.
  6. Tìm đường đi: Tìm đường đi ngắn nhất giữa các đỉnh sử dụng các thuật toán như Dijkstra hoặc Floyd-Warshall.

Các ứng dụng của đồ thị:

Cấu trúc dữ liệu đồ thị là một phần quan trọng trong khoa học máy tính và được sử dụng rộng rãi trong nhiều lĩnh vực khác nhau.