Đang chuẩn bị liên kết để tải về tài liệu:
Các cấu trúc dữ liệu đồ thị

Tham khảo tài liệu 'các cấu trúc dữ liệu đồ thị', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Các cấu trúc dữ liệu đồ thị Có nhiều cách khác nhau để lưu trữ các đồ thị trong máy tính. Sử dụng cấu trúc dữ liệu nào thì tùy theo cấu trúc của đồ thị và thuật toán dùng để thao tác trên đồ thị đó. Trên lý thuyết người ta có thể phân biệt giữa các cấu trúc danh sách và các cấu trúc ma trận. Tuy nhiên trong các ứng dụng cụ thể cấu trúc tốt nhất thường là kết hợp của cả hai. Người ta hay dùng các cấu trúc danh sách cho các đồ thị thưa sparse graph do chúng đòi hỏi ít bộ nhớ. Trong khi đó các cấu trúc ma trận cho phép truy nhập dữ liệu nhanh hơn nhưng lại cần lượng bộ nhớ lớn nếu đồ thị có kích thước lớn. Các cấu trúc danh sách . Danh sách liên thuộc Incidence list - Mỗi đỉnh có một danh sách các cạnh nối với đỉnh đó. Các cạnh của đồ thị được có thể được lưu trong một danh sách riêng có thể cài đặt bằng mảng array hoặc danh sách liên kết động linked list trong đó mỗi phần tử ghi thông tin về một cạnh bao gồm cặp đỉnh mà cạnh đó nối cặp này sẽ có thứ tự nếu đồ thị có hướng trọng số và các dữ liệu khác. Danh sách liên thuộc của mỗi đỉnh sẽ chiếu tới vị trí của các cạnh tương ứng tại danh sách cạnh này. . Danh sách kề Adjacency list - Mỗi đỉnh của đồ thị có một danh sách các đỉnh kề nó nghĩa là có một cạnh nối từ đỉnh này đến mỗi đỉnh đó . Trong đồ thị vô hướng cấu trúc này có thể gây trùng lặp. Chẳng hạn nếu đỉnh 3 nằm trong danh sách của đỉnh 2 thì đỉnh 2 cũng phải có trong danh sách của đỉnh 3. Lập trình viên có thể chọn cách sử dụng phần không gian thừa hoặc có thể liệt kê các quan hệ kề cạnh chỉ một lần. Biểu diễn dữ liệu này thuận lợi cho việc từ một đỉnh duy nhất tìm mọi đỉnh được nối với nó do các đỉnh này đã được liệt kê tường minh. Các cấu trúc ma trận . Ma trận liên thuộc Incidence matrix - Đồ thị được biểu diễn bằng một ma trận bj kích thước p X q trong đó p là số đỉnh và q là số cạnh bij 1 chứa dữ liệu về quan hệ giữa đỉnh vi và cạnh Xj. Đơn giản nhất bij 1 nếu đỉnh vi là một trong 2 đầu của cạnh xj bằng 0 trong các trường hợp khác. . Ma trận kề Adjaceny .