Sửa đổi Cấu trúc dữ liệu phi tuyến

Chú ý: Bạn chưa đăng nhập và địa chỉ IP của bạn sẽ hiển thị công khai khi lưu các sửa đổi.

Bạn có thể tham gia như người biên soạn chuyên nghiệp và lâu dài ở Bách khoa Toàn thư Việt Nam, bằng cách đăng ký và đăng nhập - IP của bạn sẽ không bị công khai và có thêm nhiều lợi ích khác.

Các sửa đổi có thể được lùi lại. Xin hãy kiểm tra phần so sánh bên dưới để xác nhận lại những gì bạn muốn làm, sau đó lưu thay đổi ở dưới để hoàn tất việc lùi lại sửa đổi.

Bản hiện tại Nội dung bạn nhập
Dòng 4: Dòng 4:
 
Các cấu trúc dữ liệu phi tuyến tiêu biểu là đồ thị và cây.
 
Các cấu trúc dữ liệu phi tuyến tiêu biểu là đồ thị và cây.
  
==Đồ thị==
+
Đồ thị. Đồ thị bao gồm đỉnh và cạnh, trong đó đỉnh biểu diễn các thực thể và cạnh biểu diễn mối liên hệ giữa các thực thể đó. Nếu đỉnh i có mối liên hệ với đỉnh j thì gọi là đỉnh i kề với đỉnh j. Khi ứng dụng vào các bài toán cụ thể, còn có thể đưa thêm các thông tin khác như chiều và trọng số của mối quan hệ, tương ứng với khái niệm đồ thị có hướng và đồ thị có trọng số.
Đồ thị bao gồm đỉnh và cạnh, trong đó đỉnh biểu diễn các thực thể và cạnh biểu diễn mối liên hệ giữa các thực thể đó. Nếu đỉnh i có mối liên hệ với đỉnh j thì gọi là đỉnh i kề với đỉnh j. Khi ứng dụng vào các bài toán cụ thể, còn có thể đưa thêm các thông tin khác như chiều và trọng số của mối quan hệ, tương ứng với khái niệm đồ thị có hướng và đồ thị có trọng số.
 
  
 
Các phép toán cơ bản với đồ thị được chia thành hai nhóm chính:
 
Các phép toán cơ bản với đồ thị được chia thành hai nhóm chính:
 +
 
#Các phép toán với đỉnh: thêm đỉnh, dỡ bỏ đỉnh, thay đổi giá trị của đỉnh;
 
#Các phép toán với đỉnh: thêm đỉnh, dỡ bỏ đỉnh, thay đổi giá trị của đỉnh;
 +
 
#Các phép toán với cạnh: thêm cạnh, dỡ bỏ cạnh, truy cập vào giá trị trọng số, thay đổi trọng số, kiểm tra xem đỉnh i có kề với đỉnh j hay không.
 
#Các phép toán với cạnh: thêm cạnh, dỡ bỏ cạnh, truy cập vào giá trị trọng số, thay đổi trọng số, kiểm tra xem đỉnh i có kề với đỉnh j hay không.
  
 
Các ngôn ngữ lập trình bậc cao không cài đặt đồ thị như một kiểu dữ liệu có sẵn mà phải xây dựng dựa trên một số kiểu dữ liệu khác. Hai cách phổ biến nhất để xây dựng cấu trúc dữ liệu đồ thị là sử dụng ma trận kề và danh sách kề.
 
Các ngôn ngữ lập trình bậc cao không cài đặt đồ thị như một kiểu dữ liệu có sẵn mà phải xây dựng dựa trên một số kiểu dữ liệu khác. Hai cách phổ biến nhất để xây dựng cấu trúc dữ liệu đồ thị là sử dụng ma trận kề và danh sách kề.
 +
 
* Ma trận kề M là một ma trận vuông với kích thước mỗi chiều là số đỉnh của đồ thị. Giá trị của mỗi phần tử M[i,j] tương ứng với mối quan hệ giữa hai đỉnh i và j. M[i,j] có giá trị bằng 0 khi đỉnh i không kề với đỉnh j, khác 0 trong trường hợp ngược lại. Với đồ thị có hướng thì có thể xảy ra trường hợp M[i,j] = 0 trong khi M[j,i] khác không. Với đồ thị có trọng số thì giá trị M[i,j] là một số thực, tương ứng với giá trị của mối liên hệ giữa hai đỉnh i và j. Trong các ngôn ngữ lập trình bậc cao, ma trận kề thường được cài đặt dưới dạng mảng hai chiều, sử dụng một vùng nhớ liên tục khi chạy chương trình. Cách này rất hiệu quả khi thực hiện các phép toán với cạnh do chỉ cần một thao tác đọc hoặc thay đổi ô nhớ. Tuy nhiên, trong trường hợp số lượng đỉnh của đồ thị có thay đổi thì cách này không phù hợp. Bên cạnh đó, cách xây dựng này sẽ lãng phí bộ nhớ trong trường hợp đồ thị thưa (có rất ít cạnh).
 
* Ma trận kề M là một ma trận vuông với kích thước mỗi chiều là số đỉnh của đồ thị. Giá trị của mỗi phần tử M[i,j] tương ứng với mối quan hệ giữa hai đỉnh i và j. M[i,j] có giá trị bằng 0 khi đỉnh i không kề với đỉnh j, khác 0 trong trường hợp ngược lại. Với đồ thị có hướng thì có thể xảy ra trường hợp M[i,j] = 0 trong khi M[j,i] khác không. Với đồ thị có trọng số thì giá trị M[i,j] là một số thực, tương ứng với giá trị của mối liên hệ giữa hai đỉnh i và j. Trong các ngôn ngữ lập trình bậc cao, ma trận kề thường được cài đặt dưới dạng mảng hai chiều, sử dụng một vùng nhớ liên tục khi chạy chương trình. Cách này rất hiệu quả khi thực hiện các phép toán với cạnh do chỉ cần một thao tác đọc hoặc thay đổi ô nhớ. Tuy nhiên, trong trường hợp số lượng đỉnh của đồ thị có thay đổi thì cách này không phù hợp. Bên cạnh đó, cách xây dựng này sẽ lãng phí bộ nhớ trong trường hợp đồ thị thưa (có rất ít cạnh).
 +
 
* Danh sách kề L là một danh sách với số phần tử là số đỉnh của đồ thị. Mỗi đỉnh i lại có một danh sách L[i] chứa các đỉnh kề với đỉnh i. Với đồ thị có hướng thì có thể xảy ra trường hợp đỉnh j thuộc L[i] nhưng đỉnh i không thuộc L[j]. Với đồ thị có trọng số thì có thể đưa thêm một trường dữ liệu số thực vào mỗi phần tử thuộc L[i] để biểu diễn giá trị của mối liên hệ giữa đỉnh i và đỉnh j. Quá trình xây dựng danh sách kề biểu diễn đồ thị được tiến hành như sau:
 
* Danh sách kề L là một danh sách với số phần tử là số đỉnh của đồ thị. Mỗi đỉnh i lại có một danh sách L[i] chứa các đỉnh kề với đỉnh i. Với đồ thị có hướng thì có thể xảy ra trường hợp đỉnh j thuộc L[i] nhưng đỉnh i không thuộc L[j]. Với đồ thị có trọng số thì có thể đưa thêm một trường dữ liệu số thực vào mỗi phần tử thuộc L[i] để biểu diễn giá trị của mối liên hệ giữa đỉnh i và đỉnh j. Quá trình xây dựng danh sách kề biểu diễn đồ thị được tiến hành như sau:
 +
 
** Định nghĩa ĐỈNH là kiểu dữ liệu chứa nhiều trường, trong đó có một trường cho phép trỏ đến một biến khác cũng có kiểu ĐỈNH (kiểu dữ liệu đệ quy). Một số trường còn lại được dùng để chứa các dữ liệu liên quan đến đỉnh và cạnh.
 
** Định nghĩa ĐỈNH là kiểu dữ liệu chứa nhiều trường, trong đó có một trường cho phép trỏ đến một biến khác cũng có kiểu ĐỈNH (kiểu dữ liệu đệ quy). Một số trường còn lại được dùng để chứa các dữ liệu liên quan đến đỉnh và cạnh.
 +
 
** L và L[i] là các danh sách liên kết (xt. Cấu trúc dữ liệu tuyến tính) cấp phát động với các phần tử của danh sách có kiểu ĐỈNH.
 
** L và L[i] là các danh sách liên kết (xt. Cấu trúc dữ liệu tuyến tính) cấp phát động với các phần tử của danh sách có kiểu ĐỈNH.
  
Dòng 20: Dòng 25:
  
 
Một số bài toán cơ bản sử dụng cấu trúc dữ liệu đồ thị:
 
Một số bài toán cơ bản sử dụng cấu trúc dữ liệu đồ thị:
 +
 
* Duyệt: lần lượt đi qua (thăm) toàn bộ các đỉnh của đồ thị. Quá trình duyệt bắt đầu từ một đỉnh gọi là đỉnh xuất phát và kết thúc khi toàn bộ các đỉnh của đồ thị được thăm hoặc có thể kết thúc sớm khi thăm một đỉnh thỏa mãn một điều kiện nào đó. Hai phương pháp duyệt đồ thị phổ biến nhất là duyệt theo chiều rộng và duyệt theo chiều sâu;
 
* Duyệt: lần lượt đi qua (thăm) toàn bộ các đỉnh của đồ thị. Quá trình duyệt bắt đầu từ một đỉnh gọi là đỉnh xuất phát và kết thúc khi toàn bộ các đỉnh của đồ thị được thăm hoặc có thể kết thúc sớm khi thăm một đỉnh thỏa mãn một điều kiện nào đó. Hai phương pháp duyệt đồ thị phổ biến nhất là duyệt theo chiều rộng và duyệt theo chiều sâu;
 +
 
* Tìm đường: xuất phát từ một đỉnh đầu tìm cách đi qua các cạnh/cung hoặc qua các đỉnh trung gian sao cho thỏa mãn một điều kiện nào đó. Trường hợp đỉnh xuất phát và đỉnh đích trùng nhau, bài toán tìm đường trở thành bài toán tìm chu trình;
 
* Tìm đường: xuất phát từ một đỉnh đầu tìm cách đi qua các cạnh/cung hoặc qua các đỉnh trung gian sao cho thỏa mãn một điều kiện nào đó. Trường hợp đỉnh xuất phát và đỉnh đích trùng nhau, bài toán tìm đường trở thành bài toán tìm chu trình;
 +
 
* Tìm thành phần: tìm một tập con các đỉnh và các cạnh của đồ thị ban đầu sao cho thỏa mãn một số điều kiện nào đó, ví dụ: các đỉnh đều kề với nhau, giữa hai đỉnh bất kì luôn có đường đi nối giữa chúng;
 
* Tìm thành phần: tìm một tập con các đỉnh và các cạnh của đồ thị ban đầu sao cho thỏa mãn một số điều kiện nào đó, ví dụ: các đỉnh đều kề với nhau, giữa hai đỉnh bất kì luôn có đường đi nối giữa chúng;
 +
 
* Gán nhãn: là quá trình gán các ký hiệu cho các cạnh hoặc các đỉnh của đồ thị thỏa mãn một điều kiện nào đó, ví dụ: các đỉnh kề nhau không cùng ký hiệu, các cạnh có chung đỉnh đầu mút không cùng ký hiệu.
 
* Gán nhãn: là quá trình gán các ký hiệu cho các cạnh hoặc các đỉnh của đồ thị thỏa mãn một điều kiện nào đó, ví dụ: các đỉnh kề nhau không cùng ký hiệu, các cạnh có chung đỉnh đầu mút không cùng ký hiệu.
  
==Cây==
+
Cây. Cây bao gồm một nút gốc và các nút con của nút gốc đó, trong đó nút con lại có thể là nút gốc của một cây khác (gọi là cây con). Nút không có nút con được gọi là nút lá. Giữa nút gốc và nút con được là mối quan hệ cha con. Các nút con của cùng một nút gốc được gọi là các nút anh em. Số nút con tối đa của một nút được gọi là bậc của cây. Cây được dùng để mô tả mối quan hệ có phân cấp giữa các thực thể.
Cây bao gồm một nút gốc và các nút con của nút gốc đó, trong đó nút con lại có thể là nút gốc của một cây khác (gọi là cây con). Nút không có nút con được gọi là nút lá. Giữa nút gốc và nút con được là mối quan hệ cha con. Các nút con của cùng một nút gốc được gọi là các nút anh em. Số nút con tối đa của một nút được gọi là bậc của cây. Cây được dùng để mô tả mối quan hệ có phân cấp giữa các thực thể.
 
  
 
Về mặt tổng quát, cây cũng chính là một đồ thị với khái niệm nút tương ứng với khái niệm đỉnh, mối quan hệ cha-con được thể hiện qua các cạnh. Như vậy, cây là một đồ thị mà phải thỏa mãn các điều kiện sau: giữa hai cặp đỉnh chỉ có thể có tối đa một cạnh, luôn có đường đi nối hai đỉnh bất kỳ nhưng không được chứa chu trình.
 
Về mặt tổng quát, cây cũng chính là một đồ thị với khái niệm nút tương ứng với khái niệm đỉnh, mối quan hệ cha-con được thể hiện qua các cạnh. Như vậy, cây là một đồ thị mà phải thỏa mãn các điều kiện sau: giữa hai cặp đỉnh chỉ có thể có tối đa một cạnh, luôn có đường đi nối hai đỉnh bất kỳ nhưng không được chứa chu trình.
Dòng 33: Dòng 41:
  
 
Cây không phải là cấu trúc dữ liệu được xây dựng sẵn trong các ngôn ngữ bậc cao. Cách phổ biến nhất để xây dựng cây bậc A là biểu diễn các nút bằng một kiểu dữ liệu đệ qui như sau:
 
Cây không phải là cấu trúc dữ liệu được xây dựng sẵn trong các ngôn ngữ bậc cao. Cách phổ biến nhất để xây dựng cây bậc A là biểu diễn các nút bằng một kiểu dữ liệu đệ qui như sau:
 +
 
* Định nghĩa NÚT là kiểu dữ liệu chứa nhiều trường;
 
* Định nghĩa NÚT là kiểu dữ liệu chứa nhiều trường;
 +
 
* Trong NÚT có A trường cho phép trỏ đến các biến khác cũng có kiểu NÚT, dùng để chứa địa chỉ của các nút con;
 
* Trong NÚT có A trường cho phép trỏ đến các biến khác cũng có kiểu NÚT, dùng để chứa địa chỉ của các nút con;
 +
 
* Các trường còn lại của NÚT dùng để lưu giá trị khóa và các dữ liệu khác (nếu cần).
 
* Các trường còn lại của NÚT dùng để lưu giá trị khóa và các dữ liệu khác (nếu cần).
  
Dòng 40: Dòng 51:
  
 
Các phép toán cơ bản với cây:
 
Các phép toán cơ bản với cây:
 +
 
* Thêm nút: thêm nút A vào cây dưới dạng nút con của nút B. Trong trường hợp B là nút lá thì A sẽ là nút lá, ngược lại, nếu B đã có nút con thì sẽ xảy ra hai trường hợp sau:
 
* Thêm nút: thêm nút A vào cây dưới dạng nút con của nút B. Trong trường hợp B là nút lá thì A sẽ là nút lá, ngược lại, nếu B đã có nút con thì sẽ xảy ra hai trường hợp sau:
 +
 
** A là nút anh em của các nút con đã có của B,
 
** A là nút anh em của các nút con đã có của B,
 +
 
** A là nút cha của một số hoặc toàn bộ nút con đã có của B.
 
** A là nút cha của một số hoặc toàn bộ nút con đã có của B.
 +
 
* Bỏ nút: bỏ một nút ra khỏi cây, nếu nút bị bỏ không phải là nút là thì một nút con sẽ được đưa lên chèn vào vị trí của nút bị bỏ.
 
* Bỏ nút: bỏ một nút ra khỏi cây, nếu nút bị bỏ không phải là nút là thì một nút con sẽ được đưa lên chèn vào vị trí của nút bị bỏ.
 +
 
* Xoay cây: là quá trình chuyển nút con thành nút cha và ngược lại. Do vậy, có thể làm giảm chiều cao của cây con bên trái hoặc cây con bên phải của nút đi một đơn vị.
 
* Xoay cây: là quá trình chuyển nút con thành nút cha và ngược lại. Do vậy, có thể làm giảm chiều cao của cây con bên trái hoặc cây con bên phải của nút đi một đơn vị.
  
 
Kiểu dữ liệu đệ qui NÚT trình bày phía trên được sử dụng phổ biến nhất để biểu diễn cây vì nó hỗ trợ tốt nhất việc cài đặt các phép toán cơ bản. Bên cạnh đó, còn một số cách biểu diễn khác như:
 
Kiểu dữ liệu đệ qui NÚT trình bày phía trên được sử dụng phổ biến nhất để biểu diễn cây vì nó hỗ trợ tốt nhất việc cài đặt các phép toán cơ bản. Bên cạnh đó, còn một số cách biểu diễn khác như:
 +
 
* Sử dụng các phương pháp biểu diễn đồ thị. Tuy nhiên cách này khá tổng quát và chung chung, không hỗ trợ hiệu quả việc cài đặt các phép toán cơ bản.
 
* Sử dụng các phương pháp biểu diễn đồ thị. Tuy nhiên cách này khá tổng quát và chung chung, không hỗ trợ hiệu quả việc cài đặt các phép toán cơ bản.
 +
 
* Cây nhị phân còn có thể được biểu diễn bằng mảng một chiều (đánh chỉ số từ 0) theo nguyên tắc: nếu nút có chỉ số là i, thì nút con trái và nút con phải sẽ lần lượt có chỉ số là 2i và 2i+1, còn nút cha có chỉ số là [i/2]. Cách này có hiệu quả khi cấu trúc cây là tĩnh, chỉ xây dựng một lần và không có những thay đổi về sau.
 
* Cây nhị phân còn có thể được biểu diễn bằng mảng một chiều (đánh chỉ số từ 0) theo nguyên tắc: nếu nút có chỉ số là i, thì nút con trái và nút con phải sẽ lần lượt có chỉ số là 2i và 2i+1, còn nút cha có chỉ số là [i/2]. Cách này có hiệu quả khi cấu trúc cây là tĩnh, chỉ xây dựng một lần và không có những thay đổi về sau.
  
Dòng 53: Dòng 71:
  
 
Một số cấu trúc cây đặc biệt được phát triển để tối ưu hóa việc tìm kiếm nút chứa từ khóa cụ thể từ trong danh mục bao gồm N khóa khác nhau:
 
Một số cấu trúc cây đặc biệt được phát triển để tối ưu hóa việc tìm kiếm nút chứa từ khóa cụ thể từ trong danh mục bao gồm N khóa khác nhau:
 +
 
* Cây nhị phân tìm kiếm: cây nhị phân trong đó mọi nút thuộc cây con trái đều có giá trị khóa nhỏ hơn giá trị khóa của nút gốc, mọi nút thuộc cây con phải đều có giá trị khóa lớn hơn giá trị khóa của nút gốc. Quá trình thêm nút vào cây nhị phân được thực hiện bằng cách lần lượt đi theo từng nhánh dựa trên việc so sánh giá trị khóa với các nút đã có, cho đến khi tới một nút lá. Nút mới sẽ được thêm vào dưới dạng nút con trái hoặc phải của nút lá tìm được. Để bảo đảm quá trình tìm kiếm luôn có độ phức tạp tính toán là O (logN). một số biến thể sau của cây nhị phân tìm kiếm đã được nghiên cứu và phát triển như: cây đỏ-đen, cây AVL, cây 2-3-4.
 
* Cây nhị phân tìm kiếm: cây nhị phân trong đó mọi nút thuộc cây con trái đều có giá trị khóa nhỏ hơn giá trị khóa của nút gốc, mọi nút thuộc cây con phải đều có giá trị khóa lớn hơn giá trị khóa của nút gốc. Quá trình thêm nút vào cây nhị phân được thực hiện bằng cách lần lượt đi theo từng nhánh dựa trên việc so sánh giá trị khóa với các nút đã có, cho đến khi tới một nút lá. Nút mới sẽ được thêm vào dưới dạng nút con trái hoặc phải của nút lá tìm được. Để bảo đảm quá trình tìm kiếm luôn có độ phức tạp tính toán là O (logN). một số biến thể sau của cây nhị phân tìm kiếm đã được nghiên cứu và phát triển như: cây đỏ-đen, cây AVL, cây 2-3-4.
 +
 
* Cây B và Cây B+: các cấu trúc dữ liệu chuyên dùng cho việc lưu trữ tại bộ nhớ ngoài. Quá trình xây dựng cây hướng tới việc giảm thiểu quá trình truy cập vào các nút trong quá trình tìm kiếm.
 
* Cây B và Cây B+: các cấu trúc dữ liệu chuyên dùng cho việc lưu trữ tại bộ nhớ ngoài. Quá trình xây dựng cây hướng tới việc giảm thiểu quá trình truy cập vào các nút trong quá trình tìm kiếm.
 +
 
* Cây Q, Cây R và Cây k-d: các cấu trúc cây được thiết kế cho việc biểu diễn sự phân cấp các phần tử dựa trên nhiều chiều dữ liệu khác nhau, ví dụ: các dữ liệu đa phương tiện, các dữ liệu không gian. Chức năng chủ yếu của các cấu trúc này là cho phép truy vấn dựa trên khoảng cách giữa các điểm, các vùng được thực hiện một cách nhanh nhất có thể.
 
* Cây Q, Cây R và Cây k-d: các cấu trúc cây được thiết kế cho việc biểu diễn sự phân cấp các phần tử dựa trên nhiều chiều dữ liệu khác nhau, ví dụ: các dữ liệu đa phương tiện, các dữ liệu không gian. Chức năng chủ yếu của các cấu trúc này là cho phép truy vấn dựa trên khoảng cách giữa các điểm, các vùng được thực hiện một cách nhanh nhất có thể.
==Ứng dụng và phát triển==
 
Cấu trúc dữ liệu phi tuyến dạng đồ thị được dùng để biểu diễn sự phụ thuộc của các thực thể thuộc rất nhiều lĩnh vực, vd.:
 
* Biểu diễn sự phụ thuộc lẫn nhau của các công đoạn trong một qui trình hay của các môn trong chương trình học;
 
* Biểu diễn mạng máy tính, mạng lưới cung cấp năng lượng;
 
* Biểu diễn bản đồ, tuyến đường;
 
* Biểu diễn các mối liên hệ trong mạng xã hội;
 
* Biểu diễn các cấu trúc sinh học, vật chất di truyền.
 
  
 
Cấu trúc dữ liệu phi tuyến không được cung cấp bởi các ngôn ngữ lập trình bậc cao như một kiểu dữ liệu sẵn có. Chúng được xây dựng dựa trên các kiểu dữ liệu cơ bản có sẵn và phụ thuộc vào khả năng của ngôn ngữ lập trình.
 
Cấu trúc dữ liệu phi tuyến không được cung cấp bởi các ngôn ngữ lập trình bậc cao như một kiểu dữ liệu sẵn có. Chúng được xây dựng dựa trên các kiểu dữ liệu cơ bản có sẵn và phụ thuộc vào khả năng của ngôn ngữ lập trình.
Dòng 69: Dòng 83:
  
 
Cách xây dựng đồ thị dựa trên danh sách kề và xây dựng cây sử dụng kiểu dữ liệu đệ qui chủ yếu dựa trên việc biểu diễn danh sách liên kết của các ngôn ngữ. Với C hoặc Pascal, quá trình xây dựng này dựa trên việc sử dụng con trỏ và cấp phát động. Người lập trình phải tự cài đặt các thao tác cơ bản như thêm nút, gỡ nút,... và tiến hành việc quản lý bộ nhớ tương ứng. Một số ngôn ngữ ra đời muộn hơn gián tiếp trợ giúp việc xây dựng các lớp biểu diễn đồ thị hoặc cây bằng một số cách sau:
 
Cách xây dựng đồ thị dựa trên danh sách kề và xây dựng cây sử dụng kiểu dữ liệu đệ qui chủ yếu dựa trên việc biểu diễn danh sách liên kết của các ngôn ngữ. Với C hoặc Pascal, quá trình xây dựng này dựa trên việc sử dụng con trỏ và cấp phát động. Người lập trình phải tự cài đặt các thao tác cơ bản như thêm nút, gỡ nút,... và tiến hành việc quản lý bộ nhớ tương ứng. Một số ngôn ngữ ra đời muộn hơn gián tiếp trợ giúp việc xây dựng các lớp biểu diễn đồ thị hoặc cây bằng một số cách sau:
 +
 
* Cung cấp những lớp biểu diễn danh sách liên kết trong thư viện lập trình như STL của C++, Java Collections Framework;
 
* Cung cấp những lớp biểu diễn danh sách liên kết trong thư viện lập trình như STL của C++, Java Collections Framework;
 +
 
* Cung cấp các lớp dữ liệu xây dựng sẵn cho phép tiến hành linh hoạt việc thêm bớt dữ liệu vào các tập hợp có sẵn như dictionary, set của Python.
 
* Cung cấp các lớp dữ liệu xây dựng sẵn cho phép tiến hành linh hoạt việc thêm bớt dữ liệu vào các tập hợp có sẵn như dictionary, set của Python.
 +
 +
Cấu trúc dữ liệu phi tuyến dạng đồ thị được dùng để biểu diễn sự phụ thuộc của các thực thể thuộc rất nhiều lĩnh vực, vd.:
 +
 +
* Biểu diễn sự phụ thuộc lẫn nhau của các công đoạn trong một qui trình hay của các môn trong chương trình học;
 +
 +
* Biểu diễn mạng máy tính, mạng lưới cung cấp năng lượng;
 +
 +
* Biểu diễn bản đồ, tuyến đường;
 +
 +
* Biểu diễn các mối liên hệ trong mạng xã hội;
 +
 +
* Biểu diễn các cấu trúc sinh học, vật chất di truyền.
  
 
Với dữ liệu đầu vào như trên, các giải thuật xử lý các bài toán duyệt, tìm đường, tìm thành phần, gán nhãn được dùng trong việc phát triển các ứng dụng giải quyết hầu hết các vấn đề phục vụ cho mục đích quản lý, điều hành, nghiên cứu khoa học, ví dụ:
 
Với dữ liệu đầu vào như trên, các giải thuật xử lý các bài toán duyệt, tìm đường, tìm thành phần, gán nhãn được dùng trong việc phát triển các ứng dụng giải quyết hầu hết các vấn đề phục vụ cho mục đích quản lý, điều hành, nghiên cứu khoa học, ví dụ:
 +
 
* Dẫn đường, định hướng;
 
* Dẫn đường, định hướng;
 +
 
* Lập kế hoạch điều khiển các đài quan sát không gian, quá trình in mạch điện tử;
 
* Lập kế hoạch điều khiển các đài quan sát không gian, quá trình in mạch điện tử;
 +
 
* Lên lịch thi, lịch làm việc.
 
* Lên lịch thi, lịch làm việc.
  

Lưu ý rằng tất cả các đóng góp của bạn tại Bách khoa Toàn thư Việt Nam sẽ được phát hành theo giấy phép Creative Commons Ghi công–Chia sẻ tương tự (xem thêm Bản quyền). Nếu bạn không muốn những gì mình viết ra sẽ có thể được bình duyệt và có thể bị sửa đổi, và không sẵn lòng cho phép phát hành lại, xin đừng nhấn nút “Lưu trang”. Đảm bảo rằng chính bạn là tác giả của những gì mình viết ra, hoặc chép nó từ một nguồn thuộc phạm vi công cộng hoặc tự do tương đương. ĐỪNG ĐĂNG NỘI DUNG CÓ BẢN QUYỀN MÀ CHƯA XIN PHÉP!

Hủy bỏ Trợ giúp sửa đổi (mở cửa sổ mới)

Bản mẫu dùng trong trang này: