# I. Lí thuyết:
## 1. Trình bày mối quan hệ giữa cấu trúc dữ liệu và giải thuật, cho ví dụ minh họa
Cấu trúc dữ liệu và giải thuật có mối quan hệ mật thiết.
+ Cấu trúc dữ liệu là **cách tổ chức, lưu trữ dữ liệu** trong máy tính điện tử một cách có thứ tự, có hệ thống **nhằm sử dụng dữ liệu một cách hiệu quả.**
+ Giải thuật là một **hệ thống chặt chẽ** và rõ ràng các quy tắc nhằm xác định một **dãy các thao tác trên những đối tượng**, sao cho sau một số bước hữu hạn thực hiện thao tác đó, ta thu được kết quả mong muốn.
+ Cấu trúc dữ liệu và giải thuật có **mối liên hệ chặt chẽ với nhau**, chúng luôn tồn tại song song, đi kèm nhau theo công thức: **CTDL + GT = chương trình.**
+ Các phần tử của dữ liệu thường có **mối quan hệ với nhau**; ngoài ra nếu biết tổ chức chúng theo các cấu trúc dữ liệu thích hợp thì việc thực hiện các phép toán xử lý trên các dữ liệu sẽ **càng thuận lợi hơn**, đạt hiệu quả cao hơn. Với cấu trúc dữ liệu đã chọn, ta sẽ có **giải thuật tương ứng**. Để có một chương trình tốt, ta cần phải chọn được cấu trúc dữ liệu phù hợp và chọn được một giải thuật đúng đắn.
Ví dụ: Giả sử ta có 1 danh sách các trường đại học và cao đẳng trên cả nước mỗi trường có các thông tin sau: Tên trường, địa chỉ, SĐT phòng đào tạo. Ta muốn viết một chương trình trên máy tính để khi cho biết “tên trường” máy sẽ hiện ra màn hình cho ta: “địa chỉ” và “số điện thoại phòng đào tạo” của trường đó.
- Một cách đơn giản là cứ duyệt tuần tự các tên trường trong danh sách cho tới khi tìm thấy trên trường cần tìm thì sẽ đói chiếu ra “địa chỉ” và “số điện thoại phòng đào tạo” của trường đó. Cách tìm tuần tự này rõ ràng chỉ chấp nhận được khi danh sách ngắn còn danh sách dài thì rất mất thời gian.
- Nếu ta biết tổ chức lại danh sách bằng cách sắp xếp theo thứ tự từ điển của tên trường, thì có thể áp dụng 1 giải thuật tìm kiếm khác tốt hơn, tương tự như ta vẫn thường làm khi tra từ điển. Cách tìm này nhanh hơn cách trên rất nhiều nhưng không thể áp dụng được với dữ liệu chưa được sắp xếp.
- Nếu lại biết tổ chức thêm 1 bảng mục lục chỉ dẫn theo chữ cái đầu tiên của tên trường, thì khi tìm “địa chỉ” và “số điện thoại phòng đào tạo” của HVKTMM ta sẽ bỏ qua được các tên trường mà chữ cái đầu không phải là “H”.
Như vậy có thể nói giữa hai yếu tô này có mối quan hệ mật thiết. Có thể coi chúng như hình với bóng, không thể nói tới cái này mà không nhắc tới cái kia.
## 2. Trình bày mối quan hệ giữa cấu trúc dữ liệu và các phép toán trên cấu trúc dữ liệu.
Mối quan hệ giữa cấu trúc dữ liệu và các phép toán trên cấu trúc dữ liệu là **mối quan hệ tương hỗ, không thể tách rời**.
- Cấu trúc dữ liệu là cách tổ chức dữ liệu một cách khoa học và hợp lí, nhằm đạt được hiệu quả khai thác tối đa.
- Các phép toán trên CTDL là các thao tác thực hiện trên CTDL, được thiết kế dựa trên các đặc điểm của CTDL tương ứng.
$\rightarrow$ Vì vậy, khi chọn một cấu trúc dữ liệu, ta phải nghĩ ngay tới các phép toán tác động trên cấu trúc ấy, và ngược lại, nói tới phép toán thì lại phải chú ý tới phép toán đó tác động trên các trúc dữ liệu nào. Cho nên người ta thường quan niệm: nói tới cấu trúc dữ liệu là b**ao hàm luôn cả phép toán tác động đến cấu trúc ấy.**
## 3. Trình bày sự khác nhau giữa cấu trúc dữ liệu và cấu trúc lưu trữ, cho ví dụ minh hoạ.
- Cấu trúc dữ liệu (Data Structure)
Là cách tổ chức logic để lưu và quản lý dữ liệu sao cho thao tác (thêm, xóa, tìm kiếm, duyệt,...) hiệu quả
- Cấu trúc lưu trữ: Là cách cài đặt vật lý (tổ chức cụ thể) của dữ liệu trong bộ nhớ (RAM, ổ đĩa...). Liên quan đến việc phân bố bộ nhớ, địa chỉ, dạng lưu,...
Ví dụ minh hoạ:
- Danh sách liên kết đơn
Cấu trúc dữ liệu: Danh sách liên kết đơn (Single Linked List) gồm các node, mỗi node chứa dữ liệu và con trỏ trỏ đến node tiếp theo.
Cấu trúc lưu trữ: Các node này được lưu rải rác trong bộ nhớ heap, không liên tục.
- Mảng
Cấu trúc dữ liệu: Mảng (Array) — tập hợp các phần tử cùng kiểu, đánh chỉ số.
Cấu trúc lưu trữ: Mảng được lưu liên tục trong bộ nhớ (các phần tử kế nhau), dễ truy cập nhanh qua địa chỉ.
## 4. Trình bày những đặc điểm về cấu trúc dữ liệu trong các ngôn ngữ lập trình bậc cao, có liên hệ với ngôn ngữ C.
- Trong ngôn ngữ LT bậc cao, dữ liệu được phân nhánh thành các kiểu dữ liệu, quyết định cách tổ chức và các phép toán thực hiện được trên các kiểu dữ liệu đó
- Trong các ngôn ngữ lập trình khác nhau, các kiểu dữ liệu cơ bản có thể khác nhau. Các kiểu dữ liệu được tạo thành từ nhiều kiểu dữ liệu khác nhau được gọi là kiểu dữ liệu có cấu trúc. Các dữ liệu thuộc kiểu dữ liệu cấu trúc được gọi là cấu trúc dữ liệu.
k
$\rightarrow$ Một cấu trúc dữ liệu phức hợp **gồm nhiều thành phần dữ liệu**, mỗi thành phần là dữ liệu cơ sở hoặc là cấu trúc dữ liệu đã được xây dựng. Những thành phần này tạo nên một cấu trúc dữ liệu được liên kết với nhau theo một cách nào đó.
Trong ngôn ngữ lập trình C phương pháp để liên kết dữ liệu :
* Liên kết dữ liệu cùng kiểu tạo thành mảng dữ liệu.
* Liên kết các dữ liệu thành mảng cấu trúc trong C.
* Sử dụng con trỏ để liên kết dữ liệu.
## 5. Trình bày cách Phân tích thời gian thực hiện giải thuật. Định nghĩa O lớn.
Phân tích thời gian thực hiện giải thuật được thực hiện như sau:
- **Bước 1:** Xác định đầu vào chính và kích thước đầu vào:
Trước tiên, cần xác định đầu vào của giải thuật và kích thước n biểu diễn độ lớn của đầu vào (ví dụ: số phần tử trong mảng, số đỉnh trong đồ thị, v.v.).
- **Bước 2:** Xác định các phép tính cơ bản, phép toán tích cực,...
- **Bước 3**: Xác định số vòng lặp, đệ quy theo từng trường hợp
- **Bước 4**: Viết hàm thời gian T(n)
**Định nghĩa O lớn:** ta có thời gian thực hiện 1 giải thuật là T(n) = cn^2^ (c là hằng số) thì ta nói độ phúc tạp tính toán của giải thuật này có cấp n^2^ và ký hiệu là: T(n) = O(n^2^)
1 hàm f(n) = O(g(n)) có g(n) là số cấp khi tồn tại c và n~0~ sao cho:
$$
f(n) \le cg(n) \hspace{0.5cm} khi\hspace{0.1cm} (n \ge n_0)
$$
Another way:
>Big O (ký hiệu là O) là một cách để miêu tả độ phức tạp của thuật toán khi số lượng input n tăng lên. Big O có thể là về độ phức tạp về thời gian (time complexity) hoặc về không gian (space complexity).
## 6. Trình bày cách Xác định độ phức tạp tính toán của giải thuật, với những nội dung: Qui tắc tổng, Phép toán tích cực, thời gian chạy của các câu lệnh lặp, cho ví dụ minh hoạ.
- **Quy tắc tổng**:
Giả sử $T1(n)$ và $T2(n)$ là thời gian thực hiện của 1 đoạn chương trình $P1$ và $P2$, mà $T1(n) = O(f(n))$; $T2(n) = O(g(n))$ thì thời gian thực hiện $P1$ và $P2$ tiếp theo sẽ là: $T1(n) + T2(n) = O(max(f(n),g(n))$.
Ví dụ:
```
for (int i = 0; i < n; i++)
A[i] = 0; // O(n)
for (int j = 0; j < n; j++)
for (int k = 0; k < n ; k++)
B[j] = 1; // O(n^2)
=> O(n^2+n) = O(n^2)
```
- **Phép toán tích cực**: Đó là phép toán mà số lần thực hiện không ít hơn các phép toán khác, thường được sử dụng để. Ví dụ:
```
s = 0;
for (i=0; i<=n;i++){
p =1;
for (j=1;j<=i;j++){}
p = p * x / j;
s = s+p;
}
```
Phép toán tích cực chính là `p = p * x / j`, bởi trong toàn bộ chương trình thì không có phép toán nào được thực hiện nhiều hơn phép toán này.
- **Thời gian chạy của các câu lệnh lặp**: Các câu lệnh lặp (for, while) là các câu lệnh được thực thi lặp đi lặp lại cho đến khi thỏa mãn một hoặc nhiều điều kiện dừng nào đó. Để đánh giá thời gian thực hiện một câu lệnh lặp, trước hết ta cần đánh giá số tối đa các lần lặp, kết hợp với thời gian thực thi của từng lệnh trong vòng lặp.
Ví dụ:
```
for (int i = 0; i < n; i++) // O(n)
{
A[i] = 0; // O(1)
for (int j = 0; j < n; j++) // O(n)
{
A[i] += j; // O(1)
}
}
```
Đánh giá: Vòng ngoài for $(i = 0; i < n; i++)$: n lần. Trong mỗi i: Lệnh `A[i] = 0`: $O(1)$. Vòng lặp `for (j = 0; j < n; j++)`: n lần × $O(1)$ = $O(n)$. => Tổng cho mỗi i: $O(1) + O(n) = O(n)$ => Tất cả i: $n * O(n)=O(n^2)$
## 7. Trình bày Phương pháp chia để trị hàm mô tả ý tưởng phương pháp này, cho ví dụ minh hoạ.
**Ý tưởng chung** của phương pháp này là:
- Chia vấn đề cần giải thành một số vấn đề con.
- Mỗi vấn đề con được giải quyết **độc lập**. Sau đó, ta kết hợp nghiệm của các vấn đề con để nhận được nghiệm của vấn đề đã cho.
**VD:**
Tính tổng 1 dãy số
```
int sum(arr[], l, r) {
if (l == r) return arr[l]; // đk dừng khi chỉ còn 1 phần tử
mid = (l + r) / 2;
leftSum = sum(arr, l, mid);
rightSum = sum(arr, mid + 1, r);
return leftSum + rightSum;
}
```
## 8. Trình bày Phương pháp qui hoạch động. Trình bày cách áp dụng Phương pháp quy hoạch để giải bài toán “Sắp xếp các đồ vật vào ba lô”, với số lượng các đồ vật không hạn chế.
- Chia bài toán ban đầu thành các **bài toán con nhỏ hơn**, đơn giản hơn để giải quyết từng phần một, từ đó giải quyết được bài toán lớn
- Bài toán con thường lặp đi lặp lại. Nghiệm của các bài toán con được lưu vào các bảng để sử dụng sau này thay vì tính đi tính lại.
Các bước thực hiện:
- Đưa ra cách tính nghiệm của các bài toán con đơn giản nhất.
- Tìm ra các công thức (hoặc các quy tắc) xây dựng nghiệm của bài toán thông
qua nghiệm của các bài toán con.
- Thiết kế bảng để lưu nghiệm của các bài toán con.
- Tính nghiệm của các bài toán con từ nhỏ đến lớn và lưu vào bảng.
- Xây dựng nghiệm của bài toán từ bảng.
**Bài toàn sắp xếp cái ba lô:**
>Đề bài:
Ba lô có sức chứa tối đa $W$, $n$ loại đồ vật, mỗi loại có khối lượng $w_i$ và giá trị $v_i$, được chọn không giới hạn số lượng.
Tìm cách chọn đồ vật để tổng khối lượng $≤ W$ và tổng giá trị lớn nhất.
Giải quyết:
1. Xác định bài toán con: Gọi F(w) là giá trị lớn nhất có thể đạt được với trọng lượng tối đa w. Từng bước tìm ra F(w) tốt nhất với từng giá trị w từ 1 đến W và lưu lại.
2. Xác định công thức truy hồi: $F(k,V) = max[F(k-1, W-x_kv_k) + x_kw_k]$
3. Thực hiện tính toán, lưu vào bảng. Với mỗi w, xét tất cả các loại đồ vật.
4. Truy vết từ bảng để tìm ra phương án tối ưu nhất
## 9. Trình bày Phương pháp quay lui và hàm mô tả ý tưởng phương pháp này.
Quay lui (backtracking) là một phương pháp thiết kế giải thuật được sử dụng để tìm tất cả lời giải hoặc tìm lời giải tốt nhất cho những bài toán cần thử nhiều khả năng để tìm ra được khả năng tốt nhất là đáp án cho bài toán.
Tại mỗi bước, thuật toán sẽ kiểm tra xem lựa chọn hiện tại có hợp lệ không. Nếu có, ta tiếp tục thử các bước tiếp theo. Nếu không hoặc nếu đến một điểm không thể tiếp tục, ta sẽ quay lui, phục hồi từ trạng thái trước đó và thử một hướng đi khác và cứ thế tiếp tục thử. Nhờ đó, ta hạn chế được số lượng trường hợp cần xét, từ đó tiết kiệm thời gian và tài nguyên.
>hoặc viết ngắn gọn là cách hoạt động của backtrack:
Xây dựng lời giải từng bước. Tại mỗi bước đều thử tất cả các khả năng hợp lệ. Nếu đi đến cuối mà lời giải thoả mãn điều kiện, ta lưu hoặc xuất lời giải. Nếu không thỏa mãn thì thực hiện quay lui, chuyển hướng sang hướng đi khác.
```c=
Backtrack(i)
{
for (mỗi giá trị có thể gán cho x[i])
{
x[i] = giá trị đó;
if (x[1..i] thỏa mãn điều kiện)
{
if (i == n)
Xuất hoặc lưu lời giải;
else
Backtrack(i + 1);
}
// Không thỏa mãn => quay lui, thử giá trị khác
}
}
```
## 10. Trình bày Phương pháp nhánh cận hàm mô tả ý tưởng phương pháp này.
Phương pháp nhánh cận được sử dụng để tìm đáp án của bài toán tối ưu, phương pháp có thể được mô tả dưới dạng 1 cây tìm kiếm, trong đó mỗi nhánh đại diện cho 1 lựa chọn.
Tại mỗi bước thuật toán sẽ ước lượng cận trên và cận dưới của 1 nhánh gồm nhiều giá trị khác nhau. Nếu nhánh đó không thể có nghiệm tốt hơn (tùy thuộc vào điều kiện đề bài) nghiệm tối ưu (ở bước trước đó) thì ta loại bỏ khỏi các bước tiếp theo và cứ thế tiếp tục xét cho đến khi hết tập nghiệm.
Trong trường hợp tập nghiệm ta xét tới rỗng, ta thực hiện quay lui và chọn 1 nghiệm khác, nếu thành công ta tiếp tục xét để tìm nghiệm tốt hơn.
$\rightarrow$ Không cần phải duyệt hết toàn bộ nghiệm, mà chỉ xét các nhánh có tiềm năng.
```c=
Branch_bound(i){
for (mỗi i thuộc tập nghiệm){
lưu lại tình trạng xét nghiệm hiện tại
if(nghiệm mới có giá trị tốt hơn nghiệm tối ưu){
chọn nghiệm mới làm nghiệm tối ưu
}
else{
if (các giá trị cận tốt hơn gái trị nghiệm tối ưu){
Branh_bound(i+1);
// gọi đệ quy để tiếp tục tìm nghiệm trong nhánh đó
}
}
Phục hồi lại tình trạng trước đó // ta quay lui nếu tập rỗng
}
}
```
## 11. Trình bày Phương pháp tham ăn. Trình bày cách áp dụng Phương pháp tham ăn để giải bài toán “Bài toán sắp xếp các đồ vật vào ba lô”, với số lượng các đồ vật không hạn chế. Minh hoạ cho trường hợp có 3 đồ vật và chọn ít nhất 2 đồ vật.
Phương pháp tham ăn là phương pháp xây dựng lời giải từng bước, tại mỗi bước chọn phương án tốt nhất (tối ưu cục bộ) mà không quan tâm đến hậu quả lâu dài. Ý tưởng chính là: Chọn từng bước sao cho lợi ích lớn nhất ngay tại thời điểm đó.
**Bài toán sắp xếp đồ vật vào ba lô:**
Có nhiều loại đồ vật, mỗi loại có: trọng lượng $w_i$, giá trị $v_i$. Ba lô có sức chứa tối đa $W$. Mục tiêu: Chọn số lượng các đồ vật sao cho tổng giá trị lớn nhất mà tổng trọng lượng không vượt quá $W$.
Áp dụng tham ăn vào bài toán này: Ta sẽ tính đơn giá của từng vật trên 1 đơn vị trọng lượng, sắp xếp theo thứ tự giảm dần. Mỗi lần chọn thì chọn càng nhiều đồ vật có đơn giá tốt nhất trước, cho đến khi ba lô đầy hoặc hết trọng lượng cho phép.
Ví dụ: Ta có các loại đồ vật như sau:
|Đồ vật | Giá trị $v_i$ |Trọng lượng $w_i$|
|:------:|:--------------:|:----------------:|
|1|60|10|
|2|100|20|
|3|120|30|
Ba lô có sức chứa W = 50.
Ta tính đơn giá của từng vật, sau đó sắp xếp lại:
|Đồ vật | Giá trị $v_i$ |Trọng lượng $w_i$|Đơn giá/kg|
|:------:|:--------------:|:----------------:|:-------:|
|1|60|10|6|
|2|100|20|5|
|3|120|30|4|
Thực hiện theo tham ăn: Với W = 50, có thể chọn tối đa được 5 đồ vật 1 để được giá trị max = 60. Tuy nhiên với yêu cầu đề bài là chọn tối thiểu 2 loại đồ vật thì phương án này không hợp lệ.
Điều chỉnh lại: Nếu lấy 4 đồ vật 1, trọng lượng còn lại là 10 => không đựng được thêm đồ vật nào. Lấy 3 đồ vật 1, thêm 1 đồ vật có đơn giá cao tiếp theo là đồ vật 2 => vừa đủ. Tổng giá trị sẽ là 60x3 + 100x1 = 280. Đây là phương án cần tìm.
## 12. Trình bày nguyên tắc thiết kế Top-Down, cho ví dụ minh hoạ.
Thiết kế Top-Down là phương pháp thiết kế hệ thống (chương trình, thuật toán...) bằng cách:
- Bắt đầu từ mục tiêu tổng thể (bài toán lớn).
- Chia nhỏ dần thành các bài toán con (subproblems).
- Tiếp tục chia đến khi mỗi phần đủ đơn giản, có thể dễ dàng lập trình và kiểm tra được.
Đây là cách phân tích tổng quát toàn bộ vấn đề, xuất phát từ dữ kiện và các mục tiêu đặt ra để đề cập đến những công việc chủ yếu trước, rồi sau đó mới đi dần vào giải quyết các phần việc cụ thể một cách chi tiết hơn .
Ví dụ: Cần viết chương trình quản lý bán hàng chạy trên máy tính, với các yêu cầu là: hàng ngày phải nhập các hoá đơn bán hàng, hoá đơn nhập hàng, tìm kiếm các hoá đơn đã nhập để xem hoặc sửa lại; In các hoá đơn cho khách hàng; tính doanh thu, lợi nhuận trong khoảng thời gian bất kỳ; Tính tổng hợp kho, tính doanh số của từng mặt hàng, từng khách hàng.
Xuất phát từ rất nhiều các yêu cầu trên ta không thể có ngay giải thuật để xử lý,
mà nên chia bài toán thành 3 nhiệm vụ chính cần giải quyết như sau:
1) Xử lý các danh mục để quản lý và theo dõi các thông tin về hàng hoá và
khách hàng.
2) Xử lý dữ liệu về các hoá đơn bán hàng, hoá đơn nhập hàng.
3) In các báo cáo về doanh thu, lợi nhuận.
Các nhiệm vụ ở mức đầu này thường vẫn còn tương đối phức tạp, nên cần phải
chia tiếp thành các nhiệm vụ con. Chẳng hạn nhiệm vụ “Xử lý danh mục” được chia
thành hai là “Danh mục hàng hoá” và “Danh mục khách hàng”.
Trong “Danh mục hàng hoá” lại có thể chia thành các nhiệm vụ nhỏ hơn như:
1) Thêm hàng mới
2) Tìm kiếm hàng
3) Tổng hợp kho
Những nhiệm vụ con này cũng có thể chia thành các nhiệm vụ nhỏ hơn, nhằm tối ưu cho việc xử lí bài toán
## 13. Trình bày Phương pháp tinh chỉnh từng bước, cho ví dụ minh hoạ.
Phương pháp tinh chỉnh từng bước còn gọi là phương pháp thiết kế dần dần. Tổng quan các bước của phương pháp này sẽ bắt đầu từ việc viết mô tả tổng thể (hàm chính) rồi phân tách thành các phần con lớn, sau đó tinh chỉnh tiếp từng phần con, thành các bước chi tiết hơn, lặp lại cho đến khi đủ chi tiết để thực hiện.
Ví dụ với bài toán: Nhập số nguyên n, in ra tất cả các số nguyên tố nhỏ hơn hoặc bằng n.
Bước 1: mô tả tổng quát như sau:
```
TimSoNguyenTo(n):
Với mỗi số i từ 2 đến n
Nếu i là số nguyên tố
In i
```
Bước 2: Phân tích thành các hàm phụ:
```
TimSoNguyenTo(n):
Cho i từ 2 đến n
Nếu LaSoNguyenTo(i)
In i
LaSoNguyenTo(i):
Kiểm tra i có phải số nguyên tố không
```
Bước 3: Tinh chỉnh hàm kiểm tra SNT:
```
LaSoNguyenTo(i):
Nếu i < 2 → Không phải số nguyên tố
Cho j từ 2 đến sqrt(i)
Nếu i chia hết cho j → Không phải số nguyên tố
Nếu không chia hết cho số nào → Là số nguyên tố
```
Bước 4: Chi tiết hoá sẵn sàng để lập trình:
```
LaSoNguyenTo(i):
if i < 2:
return False
for j = 2 to sqrt(i):
if i % j == 0:
return False
return True
TimSoNguyenTo(n):
for i = 2 to n:
if LaSoNguyenTo(i):
print(i)
```
## 14. Trình bày ưu điểm, nhược điểm của ba phương pháp sắp xếp: sắp xếp nhanh (Quick - sort), sắp xếp kiểu vun đống (Heap - sort), sắp xếp kiểu hoà nhập (Merge - sort). Trình bày những nhận xét khi sử dụng các phương pháp sắp xếp
QuickSort:
- Ưu: Nhanh, cài đặt đơn giản, không yêu cầu bộ nhớ
- Nhược: Trong trường hợp dãy bị sắp xếp sẵn => O(n^2).
-> Nên sử dụng để sắp xếp mảng
MergeSort:
- Ưu: Độ phức tạp luôn ổn định O(n log n), kể cả trường hợp xấu.
- Nhược: Cần thêm bộ nhớ phụ O(n), vì phải có mảng phụ để gộp.
-> Thích hợp cho DSLK
Heap Sort:
- Ưu: Độ phức tạp luôn ổn định O(n log n), kể cả trường hợp xấu. Không yêu cầu bộ nhớ ngoài.
- Nhược: Tốc độ thực tế thường chậm hơn Quick Sort, vì nhiều thao tác duy trì heap.
-> ban đầu bảng có khuynh hướng ít nhiều có thứ tự ngược với thứ tự sắp xếp thì HEAP_SORT lại tỏ ra thuận lợi.
Việc khẳng định một kỹ thuật sắp xếp nào vừa nói trên luôn luôn tốt hơn mọi kỹ thuật khác là một điều không nên. Việc chọn một phương pháp sắp xếp thích hợp thường tuỳ thuộc vào từng yêu cầu, từng điều kiện cụ thể.
# II.Giải thuật:
## 1. Chuyen trung to sang hau to
```clike=
int check(op)
{
IF op == '+' OR op == '-':
return 1
ELSE IF op == '*' OR op == '/':
return 2
ELSE:
return 0 //
}
trung_to_sang_hau_to(input){
stack S //Tao ngan xep
string out
for char in input:
if isdigit(char):
out += char \\them vao ket qua
else if char == "(":
PUSH(S,char)
else if char == ")":
while TOP(S) != "(":
out += POP(S)
POP(S) //Bo dau (
else://la dau + - * /
while S!= NULL && TOP(S) != "(" && check(TOP(S)) >= check(char):
out+= POP(S)
PUSH(S,char)
while S!=NULL:
out+=POP(S)
}
```
## 2. Dinh gia bieu thuc hau to:
```clike=
void make_equation(Z,Y,char){
z = atoi(Z)
y = atoi(Y)
if char == "+"{
return z + y
}
else if char == "-"{
return z - y
}
else if char == "*"{
return z*y
}
else{
return z/y
}
}
for char in input:
if char is number:
PUSH(S,T,char)
else:
Y = POP(S,T)
Z = POP(S,T)
W = make_equation(Z,Y,char)
PUSH(S,T,W)
printf(POP(S, T));
```
Minh hoạ diễn biến của quá trình đọc biểu thức và sự thay đổi trong STACK với biểu thức: `8 4 - 6 3 / +` theo dạng:
Diễn biến đọc biểu thức | Diễn biến STACK | Thực hiện phép toán
| Diễn biến đọc biểu thức| Diễn biến Stack| Thực hiện phép toán |
| :---------------- | :------ | :---- |
|`8` 4 - 6 3 / +|[8]<-T| Đẩy 8 vào ngăn xếp |
|`4` - 6 3 / +|[8,4]<-T|Đẩy 4 vào ngăn xếp|
|`-` 6 3 / +|[4]<-T|Lấy 8 và 4 từ ngăn xếp thực hiện phép trừ, rồi đẩy kết quả trở lại ngăn xếp.|
|`6` 3 / +|[4,6]<-T|Đẩy 6 vào ngăn xếp|
|`3` / +|[4,6,3]<-T|Đẩy 3 vào ngăn xếp|
| `/` +|[4,2]<-T|Lấy 6 và 3 từ ngăn xếp thực hiện phép chia, rồi đẩy kết quả trở lại ngăn xếp.|
| `+`|[6]<-T|Lấy 4 và 2 từ ngăn xếp thực hiện phép cộng, rồi đẩy kết quả trở lại ngăn xếp.|
>Kết quả cuối cùng bằng 6.
## 3. Bo sung nut moi trong dslk kep
```clike=
BOSUNG(){
P = malloc()
P->Data = X
P->P_R = P->P_L = NULL
if (R == NULL):
L=R=P
else:
if (Q == L): //Neu Q la nut cuc trai
P->P_R = Q
Q->P_L = P
L=P
else:
//Cách 1:
P->P_L = Q->P_L
P->P_R = Q
Q->P_L = P
P->P_L->P_R = P;
//Cách 2:
P->P_L = Q->P_L
Q->P_L->P_R = P
P->P_R = Q
Q->P_L = P
}
```
## 4. Xoa mot nut trong DSLK kep:
```clike=
Xoanode{
if (Pdau==Pcuoi==Q):
Pdau=Pcuoi=NULL
elif (Pdau == Q):
Pdau = Pdau->P_R
Pdau->P_L = null
elif (Pcuoi == Q):
Pcuoi = Pcuoi->P_L
P_cuoi->P_R = null
else:
Q->P_L->P_R = Q->P_R
Q->P_R->P_L = Q->P_L
free(Q)
}
```
## 5. Giai thuat cong hai da thuc:
```clike=
ATTACH(COEF, EXP, tail){
T = malloc()
T->EXP = EXP
T->COEF = COEF;
T->next = null
if (C!=null){
tail->next = T
}
else{
C = T
}
tail = T
}
conghaidathuc(A,B,C){
P=A
Q=B
C=null
while (P!=null && Q!=null){
if (P->EXP=Q->EXP){
H = P->COEF + Q->COEF
if (H!=0){
ATTACH(H, P->EXP, D);
}
}
else{
if (P->EXP >Q->EXP){
ATTACH(P->COEF, P->EXP, D);
P = P->next;
}
else{
ATTACH(Q->COEF, Q->EXP, D);
Q = Q->next;
}
}
}
if (Q==null){
while (P!=null){
ATTACH(P->COEF, P->EXP, D);
P = P->next;
}
}
else{
while (Q!=null){
ATTACH(Q->COEF, Q->EXP, D);
Q = Q->next;
}
}
D->next = null
}
```
## 6. Giai thuat floyd:
```clike=
floyd(n, dist, prev_node){
for (int i = 0; i<n;i++){ //Tao ma tran prev
for (int j = 0; j<n;j++){
if (i!=j && dist[i][j] != INF){
prev_node[i][j] = i
}
}
}
for (int k = 0; k<n;k++){
for (int i = 0; i<n;i++){
for (int j = 0; j<n;j++){
if dist[i][j] > dist[i][k] + dist[k][j]{
dist[i][j] > dist[i][k] + dist[k][j]
prev_node[i][j] = prev_node[k][j]
}
}
}
}
return dist, prev_node
}
path_make(prev_node, start, end){
s = start
e = end
if (prev_node[s][e] == start){
print("(%d, %d) ", start, end);
} else {
prev = P[s][v];
path_make(prev_node,s, prev);
printf("(%d, %d) ", prev, end);
}
}
}
```
## 7. Giai thừa (Dùng stack + đệ quy)
Giải thuật đệ quy:
```clike=
Giaithua(n){
if (n = 0):
return 1;
else:
return n*Giaithua(n-1);
}
```
Giải thuật sử dụng stack:
```
giaithua(n){
stack s
int res
for (int i = n; i>0; i--){
PUSH(S,i)
}
while (!isempty(s)){
res *= POP(s)
}
return res
}
```
Giải thuật sử dụng đệ quy + stack:
```c=
factorial(n){
//Sử dụng stack S, TOP là con trỏ trỏ tới đỉnh S
//Mỗi phần tử trong S sẽ gồm N: lưu giá trị n hiện hành và con trỏ P: lưu địa chỉ quay lui.
//Biến cấu trúc TEMP là biến trung chuyển gồm para và address lần lượt có chức năng giống N và P.
//PARA: parameter(Tham Số); RETADD: Return Address (Địa chỉ quay lui)
TOP = -1;// S ban đầu rỗng
//ta giả sử TEMP đã lưu những giá trị cần thiết para = n, address = đcc(địa chỉ chính)
Bước 1:
PUSH(S, TOP, TEMP); //Lưu para và address vào S
Bước 2:
if (TOP.N == NULL){
giaithua = 1;
goto Bước 4;
}
else{
para = TOP.N - 1;
address = Bước 3;
}
goto Bước 1; // Đệ quy sẽ bắt đầu chạy từ đây
Bước 3:
giaithua = TOP.N * giaithua;
Bước 4:
TEMP = POP(S, TOP);
goto address;
Bước 5:
return giaithua;
}
```
Minh hoạ diễn biến của STACK, trong quá trình thực hiện giải thuật ứng với n = 3, theo dạng: Số mức | Các bước thực hiện | Nội dung của STACK
|Số mức | Các bước thực hiện | Nội dung của STACK|
| :---------------- | :------ | :---- |
|Vào mức 1|Bước 1: PUSH(A,-1,(3,ĐCC))<br> Bước 2: N!=0, Para = 2, ADD = Bước 3| [3 ; ĐCC] <-T|
|Vào mức 2|Bước 1: PUSH(A,0,(2,Bước 3)) <br> Bước 2: N!=0, Para = 1, ADD = Bước 3| [2 ; Bước 3] <- T <br> [3 ; ĐCC]|
|Vào mức 3|Bước 1: PUSH(A,1,(1,Bước 3)) <br> Bước 2: N!=0, Para = 0, ADD = Bước 3| [1 ; Bước 3] <- T <br>[2 ; Bước 3] <br> [3 ; ĐCC]|
|Vào mức 4|Bước 1: PUSH(A,2,(0,Bước 3)) <br> Bước 2: N=0, giaithua = 1| [0 ; Bước 3] <- T <br> [1 ; Bước 3]<br>[2 ; Bước 3] <br> [3 ; ĐCC]|
|Quay lại mức 3|Bước 4: POP(A,3), goto Bước 3 <br> Bước 3: giaithua = 1 * 1|[1 ; Bước 3]<-T<br>[2 ; Bước 3] <br> [3 ; ĐCC]|
|Quay lại mức 2| POP(A,2), goto Bước 3 <br> Bước 3: giaithua = 1 * 2|[2 ; Bước 3]<-T <br> [3 ; ĐCC]|
|Quay lại mức 1| POP(A,1), goto Bước 3 <br> Bước 3: giaithua = 3 * 2 = 6|[3 ; ĐCC]<- T|
||Bước 4: POP(A,0)<br> goto ĐCC; return 6|[]|
## 8. Giai thuat kiem tra dau ngoac:
```clike=
ngoac(input){
stack s
for (i = 0; i<len(input); i++){
if input[i] == "("{
PUSH(s,input(i))
}
else if input[i] == ")"{
if (isEmpty(s)){
print("Invalid!")
return
}
else{
POP(s)
}
}
else{
continue
}
}
}
```
## 9. Quick Sort:
Chọn pivot là cuối danh sách:
```clike=
partition(A, low,high){
int pivot = A[high]
int i = low -1
for (j = low; j<high;j++){
if (A[j] < pivot){
i++
swap(A[i], A[j])
}
}
i++
swap(A[i], A[high])
return i
}
quicksort(A, low, high){
if low < high{
pivot_index = partition(A, low, high)
quicksort(A,low, pivot_index - 1)
quicksort(A,pivot_index + 1, high)
}
}
```
Cách 2: pivot ở đầu
```clike=
partition(A, low, high){
int pivot = A[low]
int i = low + 1
int j = high
do{
while (A[i] < pivot){
i++
}
while (A[j] > pivot){
j--
}
if (i<j){
swap(A[i], A[j])
i++
j--
}
}while(i<=j)
swap(A[j], A[low])
return j
}
quicksort(A, low, high){
if low < high{
pivot_index = partition(A, low, high)
quicksort(A,low, pivot_index - 1)
quicksort(A,pivot_index + 1, high)
}
}
```
Đánh giá thời gian thực hiện giải thuật:
- Trường hợp tốt nhất dãy luôn được chia thành 2 phần bằng nhau:
khi đó thì $T(n) = O(n\log n)$
- Trung bình: $T(n) = O(n \log n)$
- Xấu nhất khi mà pivot luôn là phần tử bé nhất hoặc lớn nhất trong dãy: $T(n) = O(n^2)$
## 10. Merge Sort
```clike=
merge(A, left, mid, right){
int n1 = mid - left + 1 //xac dinh so phan tu cua 2 nua
int n2 = right - mid + 1
int L1[n1], int L2[n2]
for (int i = 0; i<n1;i++){ //Sao chep du lieu vao mang tam
L1[i] = A[left + i]
}
for (int j = 0; j<n2;j++){
L2[j] = A[mid + 1 + j]
}
int i = 0; j = 0; k = left
while (i<n1 && j<n2){
if (L1[i] < L2[j]){
A[k] = L1[i]
i++
}
else{
A[k] = L2[j]
j++
}
k++
}
while (i<n1){
A[k] = L1[i]
i++
k++
}
while (j<n2){
A[k] = L2[j]
j++
k++
}
}
mergesort(A,left,right){
if (left<right){
mid = (left + right) / 2
mergesort(A,left,mid)
mergesort(A,mid+1,right)
merge(A,left,mid,right)
}
}
```
Đánh giá thời gian tính toán:
Merger Sort luôn có thời gian tính toán là $O(n\log n)$
## 11. Bubble sort
```clike=
bubbleSort(arr, n){
for (i = 0; i < n-1; i++){
for (j = 0; j < n-i-1; j++){
if (arr[j] > arr[j+1]){
x = arr[j];
arr[j] = arr[j+1];
arr[j+1] = x;
}
}
}
}
```
## 12. Heap Sort
```clike=
heapify(A,n,i){
left_node = 2i+1
right_node = 2i+2
max = i
if (A[left_node] > A[max] && left<n){ //kiem tra nut ben trai
max = left_node
}
if (A[right_node] > A[max] && right<n){ //kiem tra nut ben phai
max = right_node
}
if (max !=i){ //doi neu can thiet
swap(A[max], A[i])
heapify(A,n,max) //khi doi thi co the bi sai lech
} //=> can doi lai de duy tri cau truc heap
}
heapsort(A,n){
for (int i = (n/2) - 1; i>=0; i--){ //xay dung max_heap, duyet dan tu node n/2-1
heapify(A,n,i) // vi cac node con lai khong the la cha
}
for (int i = n - 1; i>0; i++){
swap(A[0], A[i])
heapify(A,i,0) // moi khi doi can duy tri cau truc heap
}
}
```
## 13. Duyệt cây nhị phân (STACK)
Duyệt trước **NLR**
```clike=
TRUOC(T){
//T là con trỏ trỏ tới gốc cây, S là ngăn xếp, TOP trỏ tới đỉnh S, P trỏ tới nút đang xét
if (T == NULL){
printf("Cây rỗng"); return;
}
else {
TOP = -1;
PUSH(S, TOP, T); //Đẩy gốc vào đỉnh stack
}
//Thực hiện duyệt
while (TOP > -1){
P = POP(S, TOP);
while(P != NULL){
printf(P->DATA); //In data của P
if (P->P_R != NULL)
PUSH(S, TOP, P->P_R); //Đẩy cây con phải vào stack
P = P->P_L; //Tiếp tục đi xuống cây con trái
}
}
}
```
Duyệt giữa **LNR**
```clike=
GIUA(T){
//T là con trỏ trỏ tới gốc cây, S là ngăn xếp, TOP trỏ tới đỉnh S, P trỏ tới nút đang xét
if (T == NULL){
printf("Cây rỗng"); return;
}
else{
TOP = -1;
P = T;
}
while (P != NULL || TOP > -1){
while (P != NULL){
PUSH(S, TOP, P);
P = P->P_L; //Nhảy đến khi gặp NULL ở cây con trái
}
P = POP(S, TOP);
printf(P->DATA);
//Khi còn lại gốc
// P nhảy về gốc đồng thời POP đỉnh stack P = POP
// In giá trị của gốc printf
P = P->P_R; //Nhày xuống cây con phải nếu khác NULL tiếp tục PUSH check cây con trái(nếu có) đến khi NULL, nếu không sẽ printf
}
}
```
Duyệt sau **LRN**
```clike=
SAU(T){
//T là con trỏ trỏ tới gốc cây, S là ngăn xếp, TOP trỏ tới đỉnh S, P trỏ tới nút đang xét
// S1, S2: 2 ngăn xếp dùng để duyệt
// TOP1, TOP2: đỉnh stack
if (T == NULL){
printf("Cây rỗng"); return;
}
else{
TOP1 = -1; TOP2 = -1;
PUSH(S, TOP1, T);
}
while (TOP1 > -1){
P = POP(S, TOP1);
PUSH(S, TOP2, P);
if (P->P_L != NULL){
PUSH(S, TOP1, P->P_L);
}
if (P->P_R != NULL){
PUSH(S, TOP1, P->P_R);
}
}
while (TOP2 > -1){
P = POP(S, TOP2);
printf(P->DATA);
}
}
```
## 14. Bài toán quân hậu:
```clike=
N = 8 //so luong quan hau
int row[N] //mang luu cot dat hau
int col[N] //mang luu cot da co hau
int diag1[2*N -1] //mang luu hang cheo da co hau
int diag2[2*N-1] //mang luu hang cheo da co hau
int count = 0 //so cach dat quan hau
void try(int row){
for (int c =0; c<N;c++){
if (col[c] != 1 && diag1[row + c] !=1 && diag2[row-c+N-1]!=1){
//dat hau tai hang row cot c
row[row] = c
col[c] = 1
diag1[row+c] = 1
diag2[row-c+N-1] = 1
if (row == N-1){ //dat xong 8 quan hau
count++
}
else{ //dat hang ke tiep
try(row+1)
}
//quay lui bo danh dau
col[c] = 0
diag1[row+c] = 0
diag2[row-c+N-1] = 0
}
}
}
```
## 15. Tìm kiếm có bổ sung:
```clike=
//Ham tim kiem sau do them neu ko tim thay
Node *findatain(Node *root, int x){
if(root == NULL){
P = malloc();
P->data = x;
P->left = NULL;
P->right = NULL;
root = P;
return P;
}
if(root->data == x){
printf("Đã có giá trị đó trên cây\n");
}
else if(x < root->data){
root->left = findatain(root->left, x); // cập nhật lại left
}
else if(x > root->data){
root->right = findatain(root->right, x); // cập nhật lại right
}
}
```
```clike=
BTS(root, x){
Q = null, P = root
while (P!=Null){ //Tìm và trả về vị trí của node cần tìm
if (x == P->Key){
return
}
Q = P;
if (x<P->Key){
P= P->P_L
}
else{
P= P->P_R
}
}
R = malloc()//nếu không tìm thấy, tạo node mới
R->Key = x
R->P_L = R->P_R = null
if (root == NULL){//nếu cây rỗng
root = R
}
else{
if (x < Q->Key){
Q->P_L = R
}
else{
Q->P_R = R
}
}
print("Khong tim thay, da bo sung")
}
```
## 16. Loại bỏ 1 nút trên cây tìm kiếm:
```clike=
BST_xoanode(T,x){
P = T, Q = NULL
while (P!=null){
if (P->Key == x){ \\Tìm thấy
break
}
Q = P //Bằng cách này mà Q luôn là nút cha của P
if (P->Key > x){
P = P->P_L
}
else{
P = P->P_R
}
}
if (P==NULL){ \\Tìm không thấy
return
}
if(P->P_L !=null && P->P_R!=null){ //nếu là cây con hoàn chỉnh
Node = P //thì chọn nút cực phải của cây con trái làm nút thay thế
Q=P
P = P->P_L //nhảy sang cây con trái
while (P->P_R !=null){ \\Tìm nút cực phải
Q = P
P = P->P_R
}
Node->Key = P->Key
} //Khi này cần xóa nút P hiện đang là nút cực phải cây con trái
if (P->P_L!=NULL){ //Nếu P có cây con trái
Child = P->L
}
else{ Nếu P là lá, không có cây con
Child = P->R //Có thể thay bằng dòng Child = null
}
if(P==T){ //trường hợp nút cần xóa là nút gốc
T = Child
}
else{
if(Q->P_L == P){
Q->P_L = Child
}
else{
Q->P_R = Child
}
}
free(P)
}
```
## 17. Tô màu đồ thị (tham ăn)
```clike=
to_mau(i, color){ //có tất cả n đỉnh
//Tô màu cho đỉnh i bằng color(màu mới)
//link là biến ktra các đỉnh có kề nhau ko, link = 0 là ko có, link = 1 là có
//count là biến đếm số đỉnh đc tô cùng màu mới, marked là mảng lưu các đỉnh đc tô cùng 1 màu mới
// mảng a[][] = 1 tức là có cung nối giữa 2 đỉnh và ngược lại a[][] = 0
int j, k, link, count = 1, marked[];
kq[i] = color; //tô màu cho đỉnh i bằng color và lưu vào kết quả
marked[count] = i; //đánh dấu i đã được tô
for (k = i+1; k <= n; k++){ //tìm đỉnh chưa tô
link = 0;
j = 1;
while (!link && j <= count){ // ktra nếu k kề với đỉnh nào trong marked ko?
if (a[k][marked[j]] == 1){ //Phát hiện có đỉnh kề với k
link = 1;
}else{ // không có đỉnh kề với k, kiểm tra các đỉnh tiếp theo trong marked
j++;
}
}
if (link == 0){ //đỉnh k ko có cung nối
kq[k] = color; // tô màu mới cho đỉnh k
marked[++count] = k; // đánh dấu k đã được tô
}
}
}
//Tìm nốt đỉnh chưa được tô màu
main(){
for (i = 1;i<=n;i++){
if (kq[i] == 0){
to_mau(i,++color);
}
}
}
```
```clike=
to_mau(i, color){
kq[i] = color;
for (k = 1; k <= n; k++){
if (kq[k] == 0){ // chỉ xét đỉnh chưa tô
int co_ke = 0;
for (j = 1; j <= n; j++){
if (kq[j] == color && a[k][j] == 1){
co_ke = 1;
break;
}
}
if (co_ke == 0){
kq[k] = color;
}
}
}
}
main(){
for (i = 1; i <= n; i++){
if (kq[i] == 0){
to_mau(i, ++color);
}
}
}
```
## 18. Tìm kiếm nhị phân
```clike=
BS(A,low,high,x){//A là tập hợp cần tìm, x là giá trị cần tìm,
// low và high là vị trí cận trên và dưới
mid = (low + high) / 2
if(low > high){
print("Not found")
return
}
else{
if (x == A[mid]){
return mid
}
else if (x>A[mid]){
BS(A,mid+1,high,x)
}
else{
BS(A,low,mid-1,x)
}
}
}
```
Đánh giá độ phức tạp thời gian thực hiện giải thuật:
- Trường hợp tốt nhất là khi tìm được giá trị cần tìm ngay lần đầu: $O_{(1)}$
- Trường hợp xấu nhất là khi phải chia thành đoạn nhỏ nhất hoặc không tìm thấy: $O_{\log n}$
## 19. Kiểm tra cây nhị phân tìm kiếm:
```clike=
define MINUS_INF -100000
define POS_INF 100000
isBST(node,low,high){
if (node == null){
return True
}
if (node->data <low || node->data > high){
return False
}
else{
return isBST(node->left,low,node->data) && isBST(node->right, node->data, high)
}
}
validateBST(root){
isBST(root,MINUS_INF,POS_INF)
}
```
Cách khác
```clike=
Duyet_LNR(T){
P=T;
if(P!=NULL){
Duyet_LNR(P->P_L);
A[i]=P->key;
i++;
Duyet_LNR(P->P_R);
}
}
Kiemtra_BST(T){
Duyet_LNR(T);
for(j=0;j<i-1;j++){
if(A[j]>=A[j+1]){
printf(Khong phai BST);
break;
}
}
return;
}
```
## 20. Dijkstra
*Các biến được đặt theo đề bài trong đề cương*
```c=
define inf = 10000
dijkstra(D, n, src){
// n là tổng số đỉnh, src (source) là đỉnh nguồn
// D là mảng lưu độ dài các cạnh, P là mảng lưu đường đi
// 1 là chưa duyệt, 0 là đã duyệt
// dist là mảng lưu độ dài từ src tới các đỉnh còn lại
for (i = 0; i < n; i++){
dist[i] = inf; // ban đầu tất cả độ dài đều là inf
a[i] = 1; // đánh dấu chưa duyệt bằng 1 mảng phụ
}
dist[src] = 0; // đỉnh nguồn sẽ mặc định = 0
while (còn tồn tại u sao cho a[u] == 1){ // duyệt các đỉnh lân cận
min = inf;
for (i = 0; i < n; i++){
if (a[i] == 0 && dist[i] < min){ // tìm đến đỉnh i có độ dài bé nhất
min = dist[i];
u = i; //cập nhật u thành đỉnh i vừa tìm được
}
}
}
// Sau khi duyệt xong u ta duyệt các hàng xóm của u
while (j = 0; j < n; j++){ // Ta xét các đỉnh lân cận của u là j
if (D[u][j] > 0){
k = D[u][j]; // độ dài từ u đến j
if (dist[u] + k < dist[j]){ // nếu ta tìm đc 1 đường đi ngắn hơn đường đi trước đó
dist[j] = dist[u] + k; // cập nhật lại đường đi tới đỉnh j
P[j] = u; // lưu lại đường đi và mảng P
}
}
}
a[u] = 0; // đánh dấu đỉnh u đã duyệt và tới đỉnh tiếp theo
}
```
đang thiếu in đường đi :sob:
## 21. Sắp xếp Topo:
https://www.geeksforgeeks.org/dsa/topological-sorting-indegree-based-solution/
```c=
kahn_topological_sort(Graph g, int V) {
// 1. Khởi tạo và tính toán bậc vào (in-degree) cho mỗi đỉnh
int in_degree[V]; // Mảng `in_degree` để lưu trữ bậc vào của các đỉnh
for (i = 0; i < V; i++) {
in_degree[i] = 0;
}
// Duyệt qua tất cả các cạnh để tính bậc vào
for (u = 0; u < V; u++) {
for each vertex v in g.adjacency_list[u] {
in_degree[v]++;
}
}
// 2. Khởi tạo hàng đợi (queue) và thêm các đỉnh có bậc vào bằng 0
Queue q;
for (i = 0; i < V; i++) {
if (in_degree[i] == 0) //nếu đỉnh có bậc vào bằng 0 thì đưa vào hàng đợi
PUSH(q, i);
}
}
// 3. Xử lý các đỉnh trong hàng đợi
int result[V];// Mảng `result` để lưu trữ thứ tự sắp xếp topological
int count = 0; // Đếm số đỉnh đã được sắp xếp
while (!is_empty(q)) {
// Lấy một đỉnh từ hàng đợi
int u = POP(q);
// Thêm đỉnh này vào kết quả
result[count] = u;
count++;
// Giảm bậc vào của các đỉnh kề và thêm vào hàng đợi nếu bậc vào của chúng bằng 0
for each vertex v in g.adjacency_list[u] {
in_degree[v]--;
if (in_degree[v] == 0) {
PUSH(q, v);
}
}
}
// 4. Kiểm tra xem có chu trình trong đồ thị hay không
if (count < V) {
print("Do thi chua chu trinh, failed");
return;
}
// 5. In kết quả
print("Thứ tự sắp xếp Topological là: ");
for (i = 0; i < count; i++) {
print(result[i] + " ");
}
}
```
Sign in with Wallet
Connect another wallet