[Thuật toán] Prim - Tìm cây khung nhỏ nhất

 Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị có số cạnh khoảng m=n (n-1)/2. Trong những tình huống như vậy, thuật toán Prim tỏ ra hiệu quả hơn. Thuật toán Prim còn được mang tên là người láng giềng gần nhất. Trong thuật toán này, bắt đầu tại một đỉnh tuỳ ý s của đồ thị, nối s với đỉnh y sao cho trọng số cạnh c[s, y] là nhỏ nhất. Tiếp theo, từ đỉnh s hoặc y tìm cạnh có độ dài nhỏ nhất, điều này dẫn đến đỉnh thứ ba z và ta thu được cây bộ phận gồm 3 đỉnh 2 cạnh. Quá trình được tiếp tục cho tới khi ta nhận được cây gồm n-1 cạnh, đó chính là cây bao trùm nhỏ nhất cần tìm.
    Trong quá trình thực hiện thuật toán, ở mỗi bước, ta có thể nhanh chóng chọn đỉnh và cạnh cần bổ sung vào cây khung, các đỉnh của đồ thị được sẽ được gán các nhãn. Nhãn của một đỉnh v gồm hai phần, [d[v], near[v]]. Trong đó, phần thứ nhất d[v] dùng để ghi nhận độ dài cạnh nhỏ nhất trong số các cạnh nối đỉnh v với các đỉnh của cây khung đang xây dựng. Phần thứ hai, near[v] ghi nhận đỉnh của cây khung gần v nhất. Thuật toán Prim được mô tả thông qua thủ tục sau:

void Prim(void){
 /*bước khởi tạo*/
 Chọn s là một đỉnh nào đó của đồ thị;
 VH = { s }; T = φ; d[s] = 0; near[s] = s;
 For(v∈V\VH) {
  D[v] = C[s, v]; near[v] = s;
 }
 /* Bước lặp */
 Stop = False;
 While(not stop) {
  Tìm u∈V\VH thoả mãn: d[u] = min{ d[v] với u∈V\VH };
  VH = VH∪{ u }; T = T ∪(u, near[u]);
  If(| VH | ) == n ) {
  H = <VH, T> là cây khung nhỏ nhất của đồ thị;
  Stop = TRUE;
  }Else{
   For(v ∈V\VH) {
    If(d[v] > C[u, v]) {
     D[v] = C[u, v];
     Near[v] = u;
    }
   }
  }
 }
}

Chương trình cài đặt thuật toán Prim tìm cây bao trùm nhỏ nhất được thực hiện như sau:

Tìm cây khung nhỏ nhất với thuật toán Prim

#include<iostream>
#include<conio.h>
using namespace std;
#define TRUE 1 
#define FALSE  0 
#define MAX  10000 
int a[100][100];//ma trận trọng số của đồ thị.
int n;//số đỉnh của đồ thị
int m;//số cạnh của đồ thị.
int sc;//số cạnh của cây khung nhỏ nhất.
int w;//Độ dài của cây khung nhỏ nhất.
int chuaxet[100];//mảng đánh dấu danh sách đỉnh đã thêm vào cây khung nhỏ nhất.
int cck[100][3];//danh sách cạnh của cây khung nhỏ nhất.
void nhap(void){
 int i, j, k;
 freopen("baotrum.in", "r",stdin);
 cin>>n>>m;
 cout<<"So dinh: "<<n<<endl;
 cout<<"So canh: "<<m<<endl;
 //khỏi tạo ma trận trọng số của đồ thị a[i][j] = MAX.
 for (i = 1; i <= n; i++){
  chuaxet[i] = TRUE;//Gán nhãn cho các đỉnh.
  for (j = 1; j <= n; j++)
   a[i][j] = MAX;
 }

 //nhập danh sách cạnh.
 for (int p = 1; p <= m; p++){
  cin>>i>>j>>k;
  a[i][j] = k;
  a[j][i] = k;
 }
}
void PRIM(void){
 int k, top, min, l, t, u;
 int s[100];//mảng chứa các đỉnh của cây khung nhỏ nhất.
 sc = 0; w = 0; u = 1;
 top = 1;
 s[top] = u;// thêm đỉnh u bất kỳ vào mảng s[]
 chuaxet[u] = FALSE;
 while (sc<n - 1) {
  min = MAX;
  //tìm cạnh có độ dài nhỏ nhất với các đỉnh trong mảng s[].
  for (int i = 1; i <= top; i++){
   t = s[i];
   for (int j = 1; j <= n; j++){
    if (chuaxet[j] && min>a[t][j]){
     min = a[t][j];
     k = t;
     l = j;
    }
   }
  }
  sc++;
  w = w + min;
  //thêm vào danh sách cạnh của cây khung.
  cck[sc][1] = k;
  cck[sc][2] = l;
  chuaxet[l] = FALSE; 
  top++;
  s[top] = l;
 }
}
void Result(void){
 cout<<"Do dai ngan nhat:"<< w<<endl;
 cout<<"Cac canh cua cay khung nho nhat"<<endl;
 for (int i = 1; i <= sc; i++)
  cout<< cck[i][1]<<" "<< cck[i][2]<<endl;
}
void main(void){
 nhap(); 
 PRIM();
 Result();
 getch();
}

Ma trận liền kề được tải về tại đây.
Output của chương trình.

So dinh: 6
So canh: 9
Do dai ngan nhat: 56
Cac canh cua cay khung nho nhat
1 3
3 5
5 4
4 6
3 2

Bài tập ứng dùng bạn có thể xem thêm tại đây

[Thuật toán] Tìm cây khung nhỏ nhất

Bài toán cây khung nhỏ nhất của đồ thị là một trong số những bài toán tối ưu trên đồ thị được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống. Trong mục này chúng ta sẽ trình bày những thuật toán cơ bản để giải bài toán này. Trước hết chúng ta phát biểu nội dung của bài toán.
     Cho G = (V, E) là đồ thị vô hướng liên thông với tập đỉnh V = {1,2,..., n} và tập cạnh E gồm m cạnh. Mỗi cạnh e của đồ thị G được gán với một số thực c(e), gọi là độ dài của nó. Giả xử H = (V, T) là cây khung của đồ thị. Ta gọi độ dài c(H) của cây khung H là tổng độ dài của các cạnh của nó:

c(H) = SUM(c(e)) ; e thuộc T

Bài toán đặt ra là trong số tất cả các cây khung của đồ thị G hãy tìm cây khung với độ dài nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị và bài toán đặt ra được gọi là bài toán cây khung nhỏ nhất.
Bài toán xây dựng hệ thống đường sắt: Giả sử ta muốn xây dựng hệ thống đường sắt nối n thành phố sao cho hành khách có thể đi từ bất cứ thành phố nào đến bất kỳ một trong các thành phố còn lại. Mặt khác trên quan điểm kinh tế đòi hỏi là chi phí về  xây dựng hệ thống đường phải là nhỏ nhất. Rõ ràng là đồ thị mà đỉnh là các thành phố còn các cạnh là các tuyến đường sắt nối các thành phố tương ứng với phương án tối ưu phải là cây. Vì vậy, bài toán đặt ra dẫn về bài toán tìm cây khung nhỏ nhất trên đồ thị đầy đủ n đỉnh, mỗi đỉnh tương ứng với một thành phố, với độ dài trên các cạnh chính là chi phí xây dựng đường ray nối hai thành phố tương ứng.
Bài toán nối mạng máy tính: Cần nối mạng một hệ thống gồm n máy vi tính đánh số từ 1 đến n. Biết chi phí nối máy I với máy j là c[i,j] , i,j = 1,2…,n. Hãy tìm cách nối mạng là nhỏ nhất.
Trong đó thuật toán Kruskal và Thuật toán Prim là hai thuật toán phổ biến và nổi tiếng để tìm cây khung nhỏ nhất.

1. Thuật toán Kruskal
2. Thuật toán Prim

[Thuật toán] Tìm đường đi ngắn nhất Floyd

 Xét đồ thị G =<V, E>: trong đó |V| = n, |E| = m. Với mỗi cạnh (u, v)∈E, ta đặt tương ứng với nó một số thực A<u,v> được gọi là trọng số của cạnh. Ta sẽ đặt A[u,v]=∞ nếu (u, v)∉E. Nếu dãy v0, v1,..., vk là một đường đi trên G thì tổng của tất cả các cạnh (A[vi-1,vi]) được gọi là độ dài của đường đi.
     Bài toán tìm đường đi ngắn nhất trên đồ thị dưới dạng tổng quát có thể được phát biểu dưới dạng sau: Tìm đường đi ngắn nhất từ một đỉnh xuất phát s∈V(đỉnh nguồn) đến đỉnh cuối t∈V(đỉnh đích). Đường đi như vậy được gọi là đường đi ngắn nhất từ s đến t, độ dài của đường đi d(s,t) được gọi là khoảng cách ngắn nhất từ s đến t (trong trường hợp tổng quát d(s,t) có thể âm). Nếu như không tồn tại đường đi từ s đến t thì độ dài đường đi d(s,t)=∞. Nếu như mỗi chu trình trong đồ thị đều có độ dài dương thì trong đường đi ngắn nhất sẽ không có đỉnh nào bị lặp lại, đường đi như vậy được gọi là đường đi cơ bản. Nếu như đồ thị tồn tại một chu trình nào đó có độ dài âm, thì đường đi ngắn nhất có thể không xác định, vì ta có thể đi qua chu trình âm đó một số lần đủ lớn để độ dài của nó nhỏ hơn bất kỳ một số thực cho trước nào.
1. Thuật toán gán nhãn.
     Có rất nhiều thuật toán khác nhau được xây dựng để tìm đường đi ngắn nhất. Nhưng tư tưởng chung của các thuật toán đó có thể được mô tả như sau:
     Từ ma trận trọng số A[u,v], u,v∈V, ta tìm cận trên d[v] của khoảng cách từ s đến tất cả các đỉnh v∈V. Mỗi khi phát hiện thấy d[u] + A[u,v] < d[v] thì cận trên d[v] sẽ được làm tốt lên bằng cách gán d[v] = d[u] + A[u, v]. Quá trình sẽ kết thúc khi nào ta không thể làm tốt hơn lên được bất kỳ cận trên nào, khi đó d[v] sẽ cho ta giá trị ngắn nhất từ đỉnh s đến đỉnh v. Giá trị d[v] được gọi là nhãn của đỉnh v. Ví dụ dưới đây thể hiện tư tưởng trên bằng một thuật toán gán nhãn tổng quát như sau:
 Ví dụ.Tìm đường đi ngắn nhất từ đỉnh A đến đỉnh I trên đồ thị hình sau:

Thuật toán tìm đường đi ngắn nhất Floyd

• Bước 1.Gán cho nhãn đỉnh A là 0; 

• Bước 2.Trong số các cạnh (cung) xuất phát từ A, ta chọn cạnh có độ dài nhỏ nhất, sau đó gán nhãn cho đỉnh đó bằng nhãn của đỉnh A cộng với độ dài cạnh tương ứng. Ta chọn được đỉnh C có trọng số AC = 5, nhãn d[C] = 0 + 5 = 5. 

• Bước 3.Tiếp đó, trong số các cạnh (cung) đi từ một đỉnh có nhãn là A hoặc C tới một đỉnh chưa được gán nhãn, ta chọn cạnh sao cho nhãn của đỉnh cộng với trọng số cạnh tương ứng là nhỏ nhất gán cho nhãn của đỉnh cuối của cạnh. Như vậy, ta lần lượt gán được các nhãn như sau: d[B] = 6 vì d[B] <d[C] + | CB| = 5 + 4; d[E] = 8; Tiếp tục làm như vậy cho tới khi đỉnh I được gán nhãn đó chính là độ dài đường đi ngắn nhất từ A đến I. Thực chất, nhãn của mỗi đỉnh chính là đường đi ngắn nhất từ đỉnh nguồn tới nó. 

Quá trình có thể được mô tả như trong bảng dưới đây.

Bước	Đỉnh được gán nhãn	Nhãn các đỉnh	Đỉnh đã dùng để gán nhãn
Khởi tạo	A	0	A
1	C	0+5 =5	A
2	B	0+6 = 6	A
3	E	0+8 = 8	A
4	D	5+4 = 9	C
5	F	5+7 = 13	B
6	H	8+6 = 14	E
7	G	9+6 = 15	D
8	I	15 + 3 = 18	G

Như vậy, độ dài đường đi ngắn nhất từ A đến I là 18. Đường đi ngắn nhất từ A đến I qua các đỉnh: A-> C-> D -> G -> I.
2. Thuật toán Floy
    Để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị, chúng ta có thể sử dụng n lần thuật toán Ford_Bellman hoặc Dijkstra (trong trường hợp trọng số không âm). Tuy nhiên, trong cả hai thuật toán được sử dụng đều có độ phức tạp tính toán lớn (chí ít là O(n^3)). Trong trường hợp tổng quát, người ta thường dùng thuật toán Floy được mô tả như sau:

void Floy(void)
/* Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh*/
/*Input :  Đồ thị cho bởi ma trận trọng số a[i, j], i, j = 1, 2,..., n.*/
/*Output: - Ma trận đường đi ngắn nhất giữa các cặp đỉnh d[i, j], i, j = 1, 2,...,n;
d[i,j] là độ dài ngắn nhất từ i đến j.
Ma trận ghi nhận đường đi p[i, j], i, j = 1, 2,..., n
p[i, j] ghi nhận đỉnh đi trước đỉnh j trong đường đi ngắn nhất;
*/
{
 /*bước khởi tạo*/
 for (i = 1; i≤n; i++) {
  for (j = 1; j≤n; j++) {
   d[i, j] = a[i, j];
   p[i, j] = i;
  }
 }
 /*bước lặp */
 for (k = 1; k≤n; k++) {
  for (i = 1; i≤n; i++){
   for (j = 1; j≤n; j++) {
    if (d[i, j] > d[i, k] + d[k, j]) {
     d[i, j] = d[i, k] + d[k, j];
     p[i, j] = p[k, j];
    }
   }
  }
 }
}

Chương trình cài đặt thuật toán Foly tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị được thể hiện như sau:

#include<iostream>
#include<conio.h>
using namespace std;
#define MAX 10000 
#define TRUE 1 
#define FALSE  0 
int A[50][50];// ma trận trọng số của đồ thị.
int D[50][50];//la mang chua cac gia tri khoan cach ngan nhat tu i den j
int S[50][50];//S la mang chua gia tri phan tu ngay sau cua i tren duong di ngan nhat tu i->j */
int n;//số đỉnh của đồ thị
int u;//đỉnh đầu của đường đi
int v;//đỉnh cuối của đường đi
void Init(void){
 freopen("FLOYD.IN", "r", stdin);
 cin>>n>>u>>v;
 cout<<"So dinh cua do thi: "<< n <<endl;
 //nhập ma trận trọng số
 for (int i = 1; i <= n; i++){
  for (int j = 1; j <= n; j++){
   cin>>A[i][j];
   if (i != j && A[i][j] == 0)
    A[i][j] = MAX;
  }
 }
}
void Result(void){
 if (D[u][v] >= MAX) {
  cout<<"Khong co duong di";
 }
 else {
  cout<<"Duong di ngan nhat tu "<<(char)(u+'A'-1)<<" den "<<(char)(v + 'A' -1)<< " co do dai la "<<D[u][v]<<endl;
  cout<<"Duong di: "<<(char)(u + 'A' - 1);//in đỉnh đầu dưới dạng char.
  while (u != v) {
   cout<<"->"<<(char)(S[u][v] +'A' -1);//in ra đường đi dưới dạng char.
   u = S[u][v];
  }
 }
}
void Floy(void){
 int i, j, k, found;
 for (i = 1; i <= n; i++){
  for (j = 1; j <= n; j++){
   D[i][j] = A[i][j];
   if (D[i][j] == MAX) S[i][j] = 0;
   else S[i][j] = j;
  }
 }
 /* Mang D[i,j] la mang chua cac gia tri khoan cach ngan nhat tu i den j
 Mang S la mang chua gia tri phan tu ngay sau cua i tren duong di
 ngan nhat tu i->j */
 for (k = 1; k <= n; k++){
  for (i = 1; i <= n; i++){
   for (j = 1; j <= n; j++){
    if (D[i][k] != MAX && D[i][j] > (D[i][k] + D[k][j])){
     // Tim D[i,j] nho nhat co the co 
     D[i][j] = D[i][k] + D[k][j];
     S[i][j] = S[i][k];
     //ung voi no la gia tri cua phan tu ngay sau i 
    }
   }
  }
 }
}
void main(void){
 Init();
 Floy();
 Result();
 getch();
}

File FLOYD.IN được tải về tại đây.
Output của chương trình:

So dinh cua do thi: 9
Duong di ngan nhat tu A den I co do dai la 18
Duong di: A->C->D->D->I

[Thuật toán] Tìm đường đi ngắn nhất Dijkstra

 Xét đồ thị G =<V, E>: trong đó |V| = n, |E| = m. Với mỗi cạnh (u, v)∈E, ta đặt tương ứng với nó một số thực A<u,v> được gọi là trọng số của cạnh. Ta sẽ đặt A[u,v]=∞ nếu (u, v)∉E. Nếu dãy v0, v1,..., vk là một đường đi trên G thì tổng của tất cả các cạnh ( A[vi-1,vi]) được gọi là độ dài của đường đi.
     Bài toán tìm đường đi ngắn nhất trên đồ thị dưới dạng tổng quát có thể được phát biểu dưới dạng sau: Tìm đường đi ngắn nhất từ một đỉnh xuất phát s∈V(đỉnh nguồn) đến đỉnh cuối t∈V(đỉnh đích). Đường đi như vậy được gọi là đường đi ngắn nhất từ s đến t, độ dài của đường đi d(s,t) được gọi là khoảng cách ngắn nhất từ s đến t (trong trường hợp tổng quát d(s,t) có thể âm). Nếu như không tồn tại đường đi từ s đến t thì độ dài đường đi d(s,t)=∞. Nếu như mỗi chu trình trong đồ thị đều có độ dài dương thì trong đường đi ngắn nhất sẽ không có đỉnh nào bị lặp lại, đường đi như vậy được gọi là đường đi cơ bản. Nếu như đồ thị tồn tại một chu trình nào đó có độ dài âm, thì đường đi ngắn nhất có thể không xác định, vì ta có thể đi qua chu trình âm đó một số lần đủ lớn để độ dài của nó nhỏ hơn bất kỳ một số thực cho trước nào.
1. Thuật toán gán nhãn.
     Có rất nhiều thuật toán khác nhau được xây dựng để tìm đường đi ngắn nhất. Nhưng tư tưởng chung của các thuật toán đó có thể được mô tả như sau:
     Từ ma trận trọng số A[u,v], u,v∈V, ta tìm cận trên d[v] của khoảng cách từ s đến tất cả các đỉnh v∈V. Mỗi khi phát hiện thấy d[u] + A[u,v] < d[v] thì cận trên d[v] sẽ được làm tốt lên bằng cách gán d[v] = d[u] + A[u, v]. Quá trình sẽ kết thúc khi nào ta không thể làm tốt hơn lên được bất kỳ cận trên nào, khi đó d[v] sẽ cho ta giá trị ngắn nhất từ đỉnh s đến đỉnh v. Giá trị d[v] được gọi là nhãn của đỉnh v. Ví dụ dưới đây thể hiện tư tưởng trên bằng một thuật toán gán nhãn tổng quát như sau:
 Ví dụ.Tìm đường đi ngắn nhất từ đỉnh A đến đỉnh I trên đồ thị hình sau:

Thuật toán tìm đường đi ngắn nhất Dijkstra

• Bước 1.Gán cho nhãn đỉnh A là 0; 

• Bước 2.Trong số các cạnh (cung) xuất phát từ A, ta chọn cạnh có độ dài nhỏ nhất, sau đó gán nhãn cho đỉnh đó bằng nhãn của đỉnh A cộng với độ dài cạnh tương ứng. Ta chọn được đỉnh C có trọng số AC = 5, nhãn d[C] = 0 + 5 = 5. 

• Bước 3.Tiếp đó, trong số các cạnh (cung) đi từ một đỉnh có nhãn là A hoặc C tới một đỉnh chưa được gán nhãn, ta chọn cạnh sao cho nhãn của đỉnh cộng với trọng số cạnh tương ứng là nhỏ nhất gán cho nhãn của đỉnh cuối của cạnh. Như vậy, ta lần lượt gán được các nhãn như sau: d[B] = 6 vì d[B] <d[C] + | CB| = 5 + 4; d[E] = 8; Tiếp tục làm như vậy cho tới khi đỉnh I được gán nhãn đó chính là độ dài đường đi ngắn nhất từ A đến I. Thực chất, nhãn của mỗi đỉnh chính là đường đi ngắn nhất từ đỉnh nguồn tới nó. 

Quá trình có thể được mô tả như trong bảng dưới đây.

Bước	Đỉnh được gán nhãn	Nhãn các đỉnh	Đỉnh đã dùng để gán nhãn
Khởi tạo	A	0	A
1	C	0+5 =5	A
2	B	0+6 = 6	A
3	E	0+8 = 8	A
4	D	5+4 = 9	C
5	F	5+7 = 13	B
6	H	8+6 = 14	E
7	G	9+6 = 15	D
8	I	15 + 3 = 18	G

Như vậy, độ dài đường đi ngắn nhất từ A đến I là 18. Đường đi ngắn nhất từ A đến I qua các đỉnh: A-> C-> D -> G -> I.
2. Thuật toán Dijkstra.
     Thuật toán tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại được Dijkstra đề nghị áp dụng cho trường hợp đồ thị có hướng với trọng số không âm. Thuật toán được thực hiện trên cơ sở gán tạm thời cho các đỉnh. Nhãn của mỗi đỉnh cho biết cận trên của độ dài đường đi ngắn nhất tới đỉnh đó. Các nhãn này sẽ được biến đổi (tính lại) nhờ một thủ tục lặp, mà ở mỗi bước lặp một số đỉnh sẽ có nhãn không thay đổi, nhãn đó chính là độ dài đường đi ngắn nhất từ s đến đỉnh đó.
Bạn cũng có thể xem thêm thuật toán Floyd - Tìm đường đi ngắn nhất ở đây.
Thuật toán có thể được mô tả bằng thủ tục Dijkstra như sau:

void Dijkstra(void)
/*Đầu vào G=(V, E) với n đỉnh có ma trận trọng sốA[u,v]≥0; s∈V */
/*Đầu ra là khoảng cách nhỏ nhất từ s đến các đỉnh còn lại d[v]: v∈V*/
/*Truoc[v] ghi lại đỉnh trước v trong đường đi ngắn nhất từ s đến v*/
{
 /* Bước 1: Khởi tạo nhãn tạm thời cho các đỉnh*/
 for (v∈V) {
  d[v] = A[s, v];
  truoc[v] = s;
 }
 d[s] = 0; T = V\{s}; /*T là tập đỉnh có nhãn tạm thời*/
 /* Bước lặp */
 while (T != φ) {
  Tìm đỉnh u∈T sao cho d[u] = min{ d[z] | z∈T };
  T = T\{u}; /*cố định nhãn đỉnh u*/;
  For(v∈T) { /* Gán lại nhãn cho các đỉnh trong T*/
   If(d[v] > d[u] + A[u, v]) {
    d[v] = d[u] + A[u, v];
    truoc[v] = u;
   }
  }
 }
}

Chương trình cài đặt thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác của đồ thị có hướng với trọng số không âm được thực hiện như sau:

#include<iostream>
#include<conio.h>
using namespace std;
#define MAX 50 
#define TRUE 1 
#define FALSE  0
#define VOCUNG 10000000
int n;//số đỉnh của đồ thị.
int s;//đỉnh đầu.
int t;//đỉnh cuối
char chon;
int truoc[MAX];//mảng đánh dấu đường đi.
int d[MAX];//mảng đánh dấu khoảng cách.
int Matrix[MAX][MAX];//ma trận trọng số
int chuaxet[MAX];//mảng đánh dấu đỉnh đã được gán nhãn.

void Init(void){
 freopen("DIJKSTRA.IN","r", stdin);
 cin>>n;
 cout<<"So dinh : "<< n<<endl;
 cin>>s>>t;//nhập đỉnh đầu và đỉnh cuối của đồ thị.
 //nhập ma trận của đồ thị.
 for (int i = 1; i <= n; i++){
  for (int j = 1; j <= n; j++){
   cin>>Matrix[i][j];
   if (Matrix[i][j] == 0) Matrix[i][j] = VOCUNG;
  }
 }
}
void Result(void){
 cout<<"Duong di ngan nhat tu "<<(char)(s+'A'-1)<<" den "<<(char)(t + 'A' -1)<< " la"<<endl;
 cout<<(char)(t + 'A' - 1)<<"<=";//in đỉnh cuối dưới dạng char.
 int i = truoc[t];
 while (i != s){
  cout<<(char)(i +'A' -1)<<"<=";//in ra kết quả dưới dạng char.
  i = truoc[i];
 }
 cout<<(char)(s+'A' -1);//in đỉnh đầu dưới dạng char.
 cout<<endl<<"Do dai duong di la : "<< d[t];
}
void Dijkstra(void){
 int u, minp;
 //khởi tạo nhãn tạm thời cho các đỉnh.
 for (int v = 1; v <= n; v++){
  d[v] = Matrix[s][v];
  truoc[v] = s;
  chuaxet[v] = FALSE;
 }
 truoc[s] = 0;
 d[s] = 0;
 chuaxet[s] = TRUE;
 //bươc lặp
 while (!chuaxet[t]) {
  minp = VOCUNG;
  //tìm đỉnh u sao cho d[u] là nhỏ nhất
  for (int v = 1; v <= n; v++){
   if ((!chuaxet[v]) && (minp > d[v])){
    u = v;
    minp = d[v];
   }
  }
  chuaxet[u] = TRUE;// u la dinh co nhan tam thoi nho nhat 
  if (!chuaxet[t]){
   //gán nhãn lại cho các đỉnh.
   for (int v = 1; v <= n; v++){
    if ((!chuaxet[v]) && (d[u] + Matrix[u][v] < d[v])){
     d[v] = d[u] + Matrix[u][v];
     truoc[v] = u;
    }
   }
  }
 }
}
void main(void){
 Init();
 Dijkstra();
 Result();
 getch();
}

File DIJKSTRA.IN được tải về tại đây.
Output của chương trình.

So dinh: 9
Duong di ngan nhat tu A den I la
I<=G<=D<=C<=A
Do dai duong di la: 18

[Thuật toán] Prim - Tìm cây khung nhỏ nhất

 Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị có số cạnh khoảng m=n (n-1)/2. Trong những tình huống như vậy, thuật toán Prim tỏ ra hiệu quả hơn. Thuật toán Prim còn được mang tên là người láng giềng gần nhất. Trong thuật toán này, bắt đầu tại một đỉnh tuỳ ý s của đồ thị, nối s với đỉnh y sao cho trọng số cạnh c[s, y] là nhỏ nhất. Tiếp theo, từ đỉnh s hoặc y tìm cạnh có độ dài nhỏ nhất, điều này dẫn đến đỉnh thứ ba z và ta thu được cây bộ phận gồm 3 đỉnh 2 cạnh. Quá trình được tiếp tục cho tới khi ta nhận được cây gồm n-1 cạnh, đó chính là cây bao trùm nhỏ nhất cần tìm.
    Trong quá trình thực hiện thuật toán, ở mỗi bước, ta có thể nhanh chóng chọn đỉnh và cạnh cần bổ sung vào cây khung, các đỉnh của đồ thị được sẽ được gán các nhãn. Nhãn của một đỉnh v gồm hai phần, [d[v], near[v]]. Trong đó, phần thứ nhất d[v] dùng để ghi nhận độ dài cạnh nhỏ nhất trong số các cạnh nối đỉnh v với các đỉnh của cây khung đang xây dựng. Phần thứ hai, near[v] ghi nhận đỉnh của cây khung gần v nhất. Thuật toán Prim được mô tả thông qua thủ tục sau:

void Prim(void){
 /*bước khởi tạo*/
 Chọn s là một đỉnh nào đó của đồ thị;
 VH = { s }; T = φ; d[s] = 0; near[s] = s;
 For(v∈V\VH) {
  D[v] = C[s, v]; near[v] = s;
 }
 /* Bước lặp */
 Stop = False;
 While(not stop) {
  Tìm u∈V\VH thoả mãn: d[u] = min{ d[v] với u∈V\VH };
  VH = VH∪{ u }; T = T ∪(u, near[u]);
  If(| VH | ) == n ) {
  H = <VH, T> là cây khung nhỏ nhất của đồ thị;
  Stop = TRUE;
  }Else{
   For(v ∈V\VH) {
    If(d[v] > C[u, v]) {
     D[v] = C[u, v];
     Near[v] = u;
    }
   }
  }
 }
}

Chương trình cài đặt thuật toán Prim tìm cây bao trùm nhỏ nhất được thực hiện như sau:

Tìm  cây khung nhỏ nhất với thuật toán Prim

#include<iostream>
#include<conio.h>
using namespace std;
#define TRUE 1 
#define FALSE  0 
#define MAX  10000 
int a[100][100];//ma trận trọng số của đồ thị.
int n;//số đỉnh của đồ thị
int m;//số cạnh của đồ thị.
int sc;//số cạnh của cây khung nhỏ nhất.
int w;//Độ dài của cây khung nhỏ nhất.
int chuaxet[100];//mảng đánh dấu danh sách đỉnh đã thêm vào cây khung nhỏ nhất.
int cck[100][3];//danh sách cạnh của cây khung nhỏ nhất.
void nhap(void){
 int i, j, k;
 freopen("baotrum.in", "r",stdin);
 cin>>n>>m;
 cout<<"So dinh: "<<n<<endl;
 cout<<"So canh: "<<m<<endl;
 //khỏi tạo ma trận trọng số của đồ thị a[i][j] = MAX.
 for (i = 1; i <= n; i++){
  chuaxet[i] = TRUE;//Gán nhãn cho các đỉnh.
  for (j = 1; j <= n; j++)
   a[i][j] = MAX;
 }

 //nhập danh sách cạnh.
 for (int p = 1; p <= m; p++){
  cin>>i>>j>>k;
  a[i][j] = k;
  a[j][i] = k;
 }
}
void PRIM(void){
 int k, top, min, l, t, u;
 int s[100];//mảng chứa các đỉnh của cây khung nhỏ nhất.
 sc = 0; w = 0; u = 1;
 top = 1;
 s[top] = u;// thêm đỉnh u bất kỳ vào mảng s[]
 chuaxet[u] = FALSE;
 while (sc<n - 1) {
  min = MAX;
  //tìm cạnh có độ dài nhỏ nhất với các đỉnh trong mảng s[].
  for (int i = 1; i <= top; i++){
   t = s[i];
   for (int j = 1; j <= n; j++){
    if (chuaxet[j] && min>a[t][j]){
     min = a[t][j];
     k = t;
     l = j;
    }
   }
  }
  sc++;
  w = w + min;
  //thêm vào danh sách cạnh của cây khung.
  cck[sc][1] = k;
  cck[sc][2] = l;
  chuaxet[l] = FALSE; 
  top++;
  s[top] = l;
 }
}
void Result(void){
 cout<<"Do dai ngan nhat:"<< w<<endl;
 cout<<"Cac canh cua cay khung nho nhat"<<endl;
 for (int i = 1; i <= sc; i++)
  cout<< cck[i][1]<<" "<< cck[i][2]<<endl;
}
void main(void){
 nhap(); 
 PRIM();
 Result();
 getch();
}

Ma trận liền kề được tải về tại đây.
Output của chương trình.

So dinh: 6
So canh: 9
Do dai ngan nhat: 56
Cac canh cua cay khung nho nhat
1 3
3 5
5 4
4 6
3 2

Bài tập ứng dùng bạn có thể xem thêm tại đây

[Thuật toán] Kruskal - Tìm cây khung nhỏ nhất

Xem thuật toán Prim - tìm cây khung nhỏ nhất tại đây.
Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H=<V, T> theo từng bước như sau:
1.  Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số cạnh;
2.  Xuất phát từ tập cạnh T=φ, ở mỗi bước, ta sẽ lần lượt duyệt trong danh sách các cạnh đã được sắp xếp, từ cạnh có trọng số nhỏ đến cạnh có trọng số lớn để tìm ra cạnh mà khi bổ sung nó vào T không tạo thành chu trình trong tập các cạnh đã được bổ sung vào T trước đó;
3.  Thuật toán sẽ kết thúc khi ta thu được tập T gồm n-1 cạnh.
Thuật toán được mô tả thông qua thủ tục Kruskal như sau:

void  Kruskal(void){
 T = φ;
 While(| T | < (n - 1) and(E≠ φ)){
  Chọn cạnh e ∈E là cạnh có độ dài nhỏ nhất;
 E: = E\ {e};
  if (T ∪{ e }: không tạo nên chu trình)
   T = T ∪{ e };
 }
 if (| T | <n - 1)
  Đồ thị không liên thông;
} 

Khối lượng tính toán nhiều nhất cảu thuật toán chính là ở bước sắp xếp các cạnh của đồ thị theo thứ tự không giảm của độ dài các cạnh để bổ xung vào cây khung. Đối với đồ thị cỡ m cạnh thì  cần phải thực hiện cỡ m*logm phép toán để sắp xếp. Tuy nhiên, để xây dựng cây khung nhỏ nhất với n-1 cạnh, ta không cần sắp xếp toàn bộ mà chỉ cần xét phần trên cảu dãy đó. Để làm việc đó ta có thể sử dụng các thủ tục sắp xếp vun đống (Heap sort).
Trong thuật toán Kruskal việc lựa chọn cạnh để bổ xung đòi hỏi phải có một thủ tục hiệu quả đế kiểm tra tập cạnh T ∪ { e } có chứa chu trình hay không. Chú ý, các cạnh trong T ở bước lặp trung gian sẽ tạo thành một rừng. Cạnh e cần khảo sát sẽ tạo thành chu trình với các cạnh trong T khi và chỉ khi cả hai đỉnh đầu của nó thuộc cùng một cây con trong rừng nói trên. Do đó thêm cạnh e vào T không tạo thành chu trình khi và chỉ khi nó phải nối 2 cây khác nhau trong T. Một trong những phương pháp hiệu quả để thực hiện việc kiểm tra này là phân hoạch các đỉnh của đồ thị thành các tập con không giao nhau. Chẳng hạn với đồ thị sau.

Tìm cây khung nhỏ nhất với thuật toán Kruskal

Ta có tập con có 6 tập con 1 phần tử: {1},{2},{3},{4},{5},{6}. Sau khi bổ xung cạnh có độ dài nhỏ nhất {3,5} ta có các tập con : {1},{2},{3,5},{4},{6}. Tiếp theo ta thêm cạnh {4,6} ta được các tập con {1},{2},{3,5},{4,6}. Tiếp theo ta thêm canh {4,5} ta được các tập con {1},{2},{3,5,4,6}. Cạnh có độ dài tiếp theo là {5,6} nhưng do hai đầu của nó thuộc cùng một tập con {3,5,4,6} nên cạnh {5,6} không được chọn.
Chương trình tìm cây khung nhỏ nhất theo thuật toán Kruskal được thể hiện như sau:

#include<iostream>
#include<conio.h>
using namespace std;
#define MAX 50 
#define TRUE 1 
#define FALSE  0 
int n, m, minl, connect;
int dau[500], cuoi[500], w[500];//mảng chứa đỉnh đầu, cuối và độ dài các cạnh của đồ thị.
int daut[50], cuoit[50], father[50];
void Init(void){
 freopen("baotrum.in", "r",stdin);
 cin>>n>>m;
 cout<<"So dinh do thi: "<< n <<endl;
 cout<<"So canh do thi:" << m <<endl;
 //nhập danh sách kề
 for (int i = 1; i <= m; i++){
  cin>>dau[i]>>cuoi[i]>>w[i];
 }
}
void Heap(int First, int Last){
 int j, k, t1, t2, t3;
 j = First;
 while (j <= (Last / 2)){
  if ((2 * j) < Last && w[2 * j + 1] < w[2 * j])
   k = 2 * j + 1;
  else
   k = 2 * j;
  if (w[k] < w[j]){
   t1 = dau[j];
   t2 = cuoi[j];
   t3 = w[j];
   dau[j] = dau[k];
   cuoi[j] = cuoi[k];
   w[j] = w[k];
   dau[k] = t1;
   cuoi[k] = t2;
   w[k] = t3;
   j = k;
  }
  else j = Last;
 }
}
int Find(int i){
 int tro = i;
 while (father[tro] > 0)
  tro = father[tro];
 return(tro);
}
void Union(int i, int j){
 int x = father[i] + father[j];
 if (father[i] > father[j]) {
  father[i] = j;
  father[j] = x;
 }
 else {
  father[j] = i;
  father[i] = x;
 }
}
void Krusal(void){
 int last, u, v, r1, r2, ncanh, ndinh;
 for (int i = 1; i <= n; i++)
  father[i] = -1;
 //sử dụng thuật toán vun đống để sắp xếp các cạnh của đồ thị theo thứ tự không giảm của độ dài.
 for (int i = m / 2; i > 0; i--)
  Heap(i, m);

 last = m; ncanh = 0; ndinh = 0; minl = 0; connect = TRUE;
 //Lựa chọn cạnh bổ xung vào cây khung.
 while (ndinh < n - 1 && ncanh < m){
  ncanh = ncanh + 1;
  u = dau[1];
  v = cuoi[1];
  //tìm gốc của phân hoạch 1.
  r1 = Find(u);
  //tìm gốc của phân hoạch 2.
  r2 = Find(v);
  if (r1 != r2) {//nếu hai gốc khác nhau thì cạnh đang xét có thể thêm được vào đồ thị.
   ndinh = ndinh + 1;
   Union(r1, r2);
   daut[ndinh] = u;
   cuoit[ndinh] = v;
   minl = minl + w[1];
  }
  dau[1] = dau[last];
  cuoi[1] = cuoi[last];
  w[1] = w[last];
  last = last - 1;
  Heap(1, last);
 }
 if (ndinh != n - 1) connect = FALSE;
}
void Result(void){
 cout<<"Do dai cay khung nho nhat:"<< minl<<endl;
 cout<<"Cac canh cua cay khung nho nhat:"<<endl;
 for (int i = 1; i < n; i++)
  cout<< daut[i]<<" "<<cuoit[i]<<endl;
}
void main(void){
 Init();
 Krusal();
 Result();
 getch();
}

Ma trận liền kề được tải về tại đây.
Output của chương trình.

So dinh: 6
So canh: 9
Do dai ngan nhat: 56
Cac canh cua cay khung nho nhat
3 5
4 6
4 5
1 3
2 3

Bài tập ứng dùng bạn có thể xem thêm tại đây

[Thuật toán] Tìm cây bao trùm

     Bài toán tìm cây bao trùm nhỏ nhất là một trong những bài toán tối ưu trên đồ thị có ứng dụng trong nhiều lĩnh vực khác nhau của thực tế. Bài toán được phát biểu như sau:
Cho G=<V, E>là đồ thị vô hướng liên thông với tập đỉnh V = {1, 2,..., n }và tập cạnh E gồm m cạnh. Mỗi cạnh e của đồ thị được gán với một số không âm c(e) được gọi là độ dài của nó. Giả sử H=<V, T>là một cây bao trùm của đồ thị G. Ta gọi độ dài c(H) của cây bao trùm H là tổng độ dài các cạnh: c(H) = SUM(c(e)). Bài toán được đặt ra là, trong số các cây khung của đồ thị hãy tìm cây khung có độ dài nhỏ nhất của đồ thị.
    Để minh họa cho những ứng dụng của bài toán này, chúng ta có thể tham khảo hai mô hình thực tế của bài toán.
Bài toán nối mạng máy tính.Một mạng máy tính gồm n máy tính được đánh số từ 1, 2,..., n. Biết chi phí nối máy i với máy j là c[i, j], i, j = 1, 2,..., n. Hãy tìm cách nối mạng sao cho chi phí là nhỏ nhất.
Bài toán xây dựng hệ thống cable.Giả sử ta muốn xây dựng một hệ thống cable điện thoại nối n điểm của một mạng viễn thông sao cho điểm bất kỳ nào trong mạng đều có đường truyền tin tới các điểm khác. Biết chi phí xây dựng hệ thống cable từ điểm i đến điểm j là c[i,j]. Hãy tìm cách xây dựng hệ thống mạng cable sao cho chi phí là nhỏ nhất.
     Để giải bài toán cây bao trùm nhỏ nhất, chúng ta có thể liệt kê toàn bộ cây bao trùm và chọn trong số đó một cây nhỏ nhất. Phương án như vậy thực sự không khả thi vì số cây bao trùm của đồ thị là rất lớn cỡ n^n-2, điều này không thể thực hiện được với đồ thị với số đỉnh cỡ chục.
Để tìm một cây bao trùm chúng ta có thể thực hiện theo các bước như sau:

• Bước 1.Thiết lập tập cạnh của cây bao trùm là φ. Chọn cạnh e = (i, j)có độ dài nhỏ nhất bổ sung vào T.

• Bước 2. Trong số các cạnh thuộc E \ T, tìm cạnh e = (i1, j1)có độ dài nhỏ nhất sao cho khi bổ sung cạnh đó vào T không tạo nên chu trình. Để thực hiện điều này, chúng ta phải chọn cạnh có độ dài nhỏ nhất sao cho hoặc i1∈Tvà j1∉T, hoặc j1∈Tvà i1∉T

• Bước 3. Kiểm tra xem T đã đủ n-1 cạnh hay chưa? Nếu T đủ n-1 cạnh thì nó chính là cây bao trùm ngắn nhất cần tìm. Nếu T chưa đủ n-1 cạnh thì thực hiện lại bước 2. 

Ví dụ. Tìm cây bao trùm nhỏ nhất của đồ thị trong hình:

• Bước 1. Đặt T=φ. Chọn cạnh (3, 5) có độ dài nhỏ nhất bổ sung vào T.

• Buớc 2. Sau ba lần lặp đầu tiên, ta lần lượt bổ sung vào các cạnh (4,5), (4, 6). Rõ ràng, nếu bổ sung vào cạnh (5, 6) sẽ tạo nên chu trình vì đỉnh 5, 6 đã có mặt trong T. Tình huống tương tự cũng xảy ra đối với cạnh (3, 4) là cạnh tiếp theo của dãy. Tiếp đó, ta bổ sung hai cạnh (1, 3), (2, 3) vào T.

• Buớc 3. Tập cạnh trong T đã đủ n-1 cạnh: T={ (3, 5), (4,6), (4,5), (1,3), (2,3)} chính là cây bao trùm ngắn nhất.

Chương trình cài đặt:

#include <stdio.h> 
#include <conio.h> 
#include <stdlib.h>
#include <math.h> 
#include <dos.h> 
#define MAX 50 
#define TRUE 1 
#define FALSE  0 
int E1[MAX], E2[MAX], D[MAX], EB[MAX], V[MAX];
/*  E1  :  Lưu trữtập đỉnh
đầu của các cạnh;
E2  : Lưu trữtập đỉnh cuối của các cạnh;
D  : Độdài các cạnh;
EB  : Tập cạnh cây bao trùm ;
V  : Tập đỉnh của đồthịcũng là tập đỉnh của cây bao trùm;
*/
int i, k, n, m, sc, min, dai;
FILE *fp;
void Init(void){
 fp = fopen("BAOTRUM.IN", "r");
 if (fp == NULL){
  printf("\n Khong co file Input");
  getch(); return;
 }
 fscanf(fp, "%d%d", &n, &m);
 printf("\n So dinh do thi:%d", n);
 printf("\n So canh do thi:%d", m);
 printf("\n Danh sach canh:");
 for (i = 1; i <= m; i++){
  fscanf(fp, "%d%d%d", &E1[i], &E2[i], &D[i]);
  printf("\n%4d%4d%4d", E1[i], E2[i], D[i]);
 }
 fclose(fp);
 for (i = 1; i <= m; i++) EB[i] = FALSE;
 for (i = 1; i <= n; i++) V[i] = FALSE;
}
void STREE_SHORTEST(void){
 /* Giai đoạn 1 của thuật toán là tìm cạnh k có độdài nhỏnhất*/
 min = D[1]; k = 1;
 for (i = 2; i <= m; i++) {
  if (D[i] < min){
   min = D[i]; k = i;
  }
 }
 /* Kết nạp cạnh k vào cây bao trùm*/
 EB[k] = TRUE; V[E1[k]] = TRUE; V[E2[k]] = TRUE; sc = 1;
 do {
  min = 32000;
  for (i = 1; i <= m; i++){
   if (EB[i] == FALSE && (
    ((V[E1[i]]) && (V[E2[i]] == FALSE)) ||
    ((V[E1[i]] == FALSE) && (V[E2[i]] == TRUE)))
    && (D[i] < min)){
    min = D[i]; k = i;
   }
  }
  /* Tìm k là cạnh nhỏnhất thỏa mãn điều kiện nếu kết nạp
  cạnh vào cây sẽkhông tạo nên chu trình*/
  EB[k] = TRUE; V[E1[k]] = TRUE; V[E2[k]] = TRUE; sc = sc + 1;
 } while (sc != (n - 1));
}
void Result(void){
 printf("\n Cay bao trum:");
 dai = 0;
 for (i = 1; i <= m; i++){
  if (EB[i]){
   printf("\n Canh %4d %4d dai %4d", E1[i], E2[i], D[i]);
   dai = dai + D[i];
  }
 }
 printf("\n Do dai cay bao trum:%d", dai);
}
void main(void){
 Init();
 STREE_SHORTEST();
 Result();
 getch();
}

[Thuật toán] Thuật toán quay lui (Back Track)

     Phương pháp sinh kế tiếp có thể giải quyết được các bài toán liệt kê khi ta nhận biết được cấu hình đầu tiên & cấu hình cuối cùng của bài toán. Tuy nhiên, không phải cấu hình sinh kế tiếp nào cũng được sinh một cách đơn giản từ cấu hình hiện tại, ngay kể cả việc phát hiện cấu hình ban đầu cũng không phải dễ tìm vì nhiều khi chúng ta phải chứng minh sự tồn tại của cấu hình. Do vậy, thuật toán sinh kế tiếp chỉ giải quyết được những bài toán liệt kê đơn giản. Để giải quyết những bài toán tổhợp phức tạp, người ta thường dùng thuật toán quay lui (Back Track) sẽ được trình bày dưới đây.
     Nội dung chính của thuật toán này là xây dựng dần các thành phần của cấu hình bằng cách thử tất cả các khả năng. Giả sử cần phải tìm một cấu hình của bài toán x = (x1, x2,.., xn) mà i-1 thành phần x1, x2,.., xi-1 đã được xác định, bây giờ ta xác định thành phần thứ i của cấu hình bằng cách duyệt tất cả các khả năng có thể có và đánh số các khả năng từ 1..ni. Với mỗi khả năng j, kiểm tra xem j có chấp nhận được hay không. Khi đó có thể xảy ra hai trường hợp:

• Nếu chấp nhận j thì xác định xi theo j, nếu i=n thì ta được một cấu hình cần tìm, ngược lại xác định tiếp thành phần xi+1

• Nếu thử tất cả các khả năng mà không có khả năng nào được chấp nhận thì quay lại bước trước đó để xác định lại xi-1

     Điểm quan trọng nhất của thuật toán là phải ghi nhớ lại mỗi bước đã đi qua, những khả năng nào đã được thử để tránh sự trùng lặp. Để nhớ lại những bước duyệt trước đó, chương trình cần phải được tổ chức theo cơ chế ngăn xếp (Last in first out). Vì vậy, thuật toán quay lui rất phù hợp với những phép gọi đệ qui. Thuật toán quay lui xác định thành phần thứ i có thể được mô tả bằng thủ tục Try(i) như sau:

void Try(int i) {
 int  j;
 for (j = 1; j < ni; j++) {
  if (<Chấp nhận j >) {
   <Xác định xi theo j>
    if (i == n)
     < Ghi nhận cấu hình > ;
    else  Try(i + 1);
  }
 }
}

Có thể mô tả quá trình tìm kiếm lời giải theo thuật toán quay lui bằng cây tìm kiếm lời giải sau:

Dưới đây là một số ví dụ sử dụng thuật toán quay lui.

1. Liệt kê các xâu nhị phân có độ dài n.
2. Liệt kê các tập con k  của tập n phần tử.
3. Liệt kê các hoán vị của tập n phần tử.
4. Bài toán xếp hậu. Liệt kê tất cả các cách xếp n quân hậu trên bàn cờ n x n sao cho chúng không ăn được nhau.

[Thuật toán] Người du lịch

Bài toán: Một người du lịch muốn đi thăm quan n thành phố T1, T2, …, Tn. Xuất phát từ một thành phố nào đó, người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua đúng một lần, rồi quay trở lại thành phố xuất phát. Biết cij là chi phí đi từ thành phố Ti đến thành phố Tj(i = 1, 2,.., n), hãy tìm hành trình với tổng chi phí là nhỏ nhất.
Giải: Có thể viết lại dưới dạng: (π(1), π(2), π(2), π(3),..., π(n-1), π(n), π(n), π(1) Trong đó mỗi thành phần: π(j-1), π(j) sẽ được gọi là một cạnh của hành trình.
Khi tiến hành tìm kiếm lời giải bài toán người du lịch chúng ta phân tập các hành trình thành 2 tập con: Tập những hành trình chứa một cặp cạnh (i, j) nào đó còn tập kia gồm những hành trình không chứa cạnh này. Ta gọi việc làm đó là sự phân nhánh, mỗi tập con như vậy được gọi là một nhánh hay một node của cây tìm kiếm. Quá trình phân nhánh được minh hoạ bởi hình sau:

Phân nhánh hành trình

Sau khi phân nhánh và tính cận dưới giá trị hàm mục tiêu trên mỗi tập con. Việc tìm kiếm sẽ tiếp tục trên tập con có giá trị cận dưới nhỏ hơn. Thủ tục này được tiếp tục cho đến khi ta nhận được một hành trình đầy đủ tức là một phương án cuả bài toán. Khi đó ta chỉ cần xét những tập con các phương án nào có cận dưới nhỏ hơn giá trị của hàm mục tiêu tại phương án đã tìm được. Quá trình phân nhánh và tính cận trên tập các phương án của bài toán thông thường cho phép rút ngắn một cách đáng kể quá trình tìm kiếm do ta loại được rất nhiều tập con .
1. Thủ tục rút gọn
Do người du lịch đi qua mỗi thành phố đúng một lần nên tổng chi phí của một hành trình của người du lịch sẽ chứa đúng một phần tử của mỗi hàng và đúng một phần tử của mỗi cột trong ma trận chi phí C. Do đó, nếu ta cộng hay trừ bớt mỗi phần tử của một hàng (hay cột) của ma trận C đi cùng một số α thì độ dài của tất cả các hành trình đều giảm đi α vì thế hành trình tối ưu cũng sẽ không bị thay đổi (vẫn là hành trình đó với chi phí giảm đi  α). Vì vậy, nếu ta tiến hành bớt đi các phần tử của mỗi hàng và mỗi cột đi một hằng số sao cho ta thu được một ma trận gồm các phần tử không âm mà trên mỗi hàng, mỗi cột đều có ít nhất một số 0, thì tổng các số trừ đó cho ta cận dưới của mọi hành trình. Thủ tục bớt này được gọi là thủ tục rút gọn, các hằng số trừ ở mỗi hàng (cột) sẽ được gọi là hằng số rút gọn theo hàng (cột), ma trận thu được được gọi là ma trận rút gọn. Thủ tục sau cho phép rút gọn ma trận một ma trận A kích thước k × k đồng thời .

float Reduce(float A[][max], int k) {
 sum = 0;
 for (i = 1; i≤k; i++){
  r[i] = < phần tử nhỏ nhất của hàng i >;
  if (r[i] > 0) {
   <Bớt mỗi phần tử của hàng i đi r[i] >;
   sum = sum + r[i];
  }
 }
 for (j = 1; j≤k; j++) {
  s[j]: = <Phần tử nhỏ nhất của cột j>;
  if (s[j] > 0)
   sum = sum + S[j];
 }
 return(sum);
} 

Ví dụ.Giả sử ta có ma trận chi phí với n= 6 thành phố sau:

	1	2	3	4	5	6	r[i]
1	∞	3	93	13	33	9	3
2	4	∞	77	42	21	16	4
3	45	17	∞	36	16	28	16
4	39	90	80	∞	56	7	7
5	28	46	88	33	∞	25	25
6	3	88	18	46	92	∞	3
s[j]	0	0	15	8	0	0

     Đầu tiên trừ bớt mỗi phần tử của các hàng 1, 2, 3, 4, 5, 6 cho các hằng số rút gọn tương ứng là ( 3, 4, 16, 7, 25, 3), sau đó trong ma trận thu được ta trừ bớt các phần tử của cột 3 và 4 tương ứng là (15, 8) ta nhận được ma trận rút gọn sau:

	1	2	3	4	5	6
1	∞	0	75	2	30	6
2	0	∞	58	30	17	12
3	29	1	∞	12	0	12
4	32	83	58	∞	49	0
5	3	21	48	0	∞	0
6	0	85	0	35	89	∞

Tổng các hằng số rút gọn là 3+4+16+7+25+3+15+8 = 81, vì vậy cận dưới cho tất cả các hành trình là 81 (không thể có hành trình có chi phí nhỏ hơn 81).
Bây giờ ta xét cách phân tập các phương án ra thành hai tập. Giả sử ta chọn cạnh (6, 3) để phân nhánh. Khi đó tập các hành trình được phân thành hai tập con, một tập là các hành trình đi qua cạnh này, còn một hành trình không đi qua cạnh này. Vì hành trình không đi qua cạnh (6,3) nên ta có thể cấm hành trị đi qua bằng cách đặt C[6, 3] = ∞. Do C[6, 3] = ∞ nên ma trận thu được sẽ có thể rút gọn bằng cách bớt đi mỗi phần tử của cột 3 đi 48 và không bớt gì các phần tử của hàng thứ 6. Như vậy ta thu được cận dưới của hành trình không chứa cạnh (6,3) là 81 + 48 = 129. Còn đối với tập chứa cạnh (6, 3) ta phải loại hàng 6, cột 3 khỏi ma trận tương ứng với nó, bởi vì đã đi theo cạnh (6, 3) thì không thể đi từ 6 sang bất sang bất cứ nơi nào khác và cũng không được phép đi bất cứ đâu từ 3. Kết quả nhận được là ma trận với bậc giảm đi 1. Ngoài ra, do đã đi theo cạnh (6, 3) nên không được phép đi từ 3 đến 6 nữa, vì vậy cần cấm đi theo cạnh (3, 6) bằng cách đặt C(3, 6) = ∞. Cây tìm kiếm lúc này có dạng như trong hình.

Phân nhánh hành trình chứa cạnh (6,3)

Cận dưới = 81
	1	2	4	5	6
1	∞	0	2	30	6
2	0	∞	30	17	12
3	29	1	12	0	∞
4	32	83	∞	49	0
5	3	21	0	∞	0

Hình 4

Cận dưới = 129
	1	2	3	4	5	6
1	∞	0	27	2	30	6
2	0	∞	10	30	17	12
3	29	1	∞	12	0	12
4	32	83	10	∞	49	0
5	3	21	0	0	∞	0
6	0	85	∞	35	89	∞

Hình 5
 Cạnh (6,3) được chọn để phân nhánh vì phân nhánh theo nó ta thu được cận dưới của nhánh bên phải là lớn nhất so với việc phân nhánh theo các cạnh khác. Qui tắc này sẽ được áp dụng ở để phân nhánh ở mỗi đỉnh của cây tìm kiếm. Trong quá trình tìm kiếm chúng ta luôn đi theo nhánh bên trái trước. Nhánh bên trái sẽ có ma trận rút gọn với bậc giảm đi 1. Trong ma trận của nhánh bên phải ta thay một số bởi ∞, và có thể rút gọn thêm được ma trận này khi tính lại các hằng số rút gọn theo dòng và cột tương ứng với cạnh phân nhánh, nhưng kích thước của ma trận vẫn giữ nguyên.
     Do cạnh chọn để phân nhánh phải là cạnh làm tăng cận dưới của nhánh bên phải lên nhiều nhất, nên để tìm nó ta sẽ chọn số không nào trong ma trận mà khi thay nó bởi ∞ sẽ cho ta tổng hằng số rút gọn theo dòng và cột chứa nó là lớn nhất. Thủ tục đó có thể được mô tả như sau để chọn cạnh phân nhánh (r, c).
2. Thủ tục chọn cạnh phân nhánh (r,c).

void BestEdge(A, k, r, c, beta)
Đầu vào : Ma trận rút gọn A kích thước k ×k
Kết quảra : Cạnh phân nhánh(r, c) và tổng hằng số rút gọn theo dòng r cột c là beta.
{
 beta = -∞;
 for (i = 1; i≤k; i++){
  for (j = 1; j≤k; j++) {
   if (A[i, j] == 0){
    minr = < phần tử nhỏ nhất trên dòng i khác với A[i, j];
    minc = <phần tử nhỏ nhất trên cột j khác với A[i, j];
    total = minr + minc;
    if (total > beta) {
     beta = total;
     r = i; /* Chỉ số dòng tốt nhất*/
     c = j; /* Chỉ số cột tốt nhất*/
    }
   }
  }
 }
}

    Trong ma trận rút gọn 5 ×5 của nhánh bên trái hình 4, số không ở vị trí (4, 6) sẽ cho tổng hằng số rút gọn là 32 ( theo hàng 4 là 32, cột 6 là 0). Đây là hệ số rút gọn có giá trị lớn nhất đối với các số không của ma trận này. Việc phân nhánh tiếp tục sẽ dựa vào cạnh (4, 6). Khi đó cận dưới của nhánh bên phải tương ứng với tập hành trình đi qua cạnh (6,3) nhưng không đi qua cạnh (4, 6) sẽ là 81 + 32 = 113. Còn nhánh bên trái sẽ tương ứng với ma trận 4 ×4 (vì ta phải loại bỏ dòng 4 và cột 6). Tình huống phân nhánh này được mô tả trong hình 5.
     Nhận thấy rằng vì cạnh (4, 6) và (6, 3) đã nằm trong hành trình nên cạnh (3, 4) không thể đi qua được nữa (nếu đi qua ta sẽ có một hành trình con từ những thành phố này). Để ngăn cấm việc tạo thành các hành trình con ta sẽ gán cho phần tử ở vị trí (3, 4) giá trị ∞.

Phân nhánh hành trình chứa cạnh (6,30

Ngăn cấm tạo thành hành trình con:
Tổng quát hơn, khi phân nhánh dựa vào cạnh (iu, iv) ta phải thêm cạnh này vào danh sách các cạnh của node bên trái nhất. Nếu iu là đỉnh cuối của một đường đi (i1, i2,.., iu) và jv là đỉnh đầu của đường đi (j1, j2,.., jk) thì để ngăn ngừa khả năng tạo thành hành trình con ta phải ngăn ngừa khả năng tạo thành hành hành trình con ta phải cấm cạnh (jk, i1). Để tìm i1 ta đi ngược từ iu, để tìm jk ta đi xuôi từ j1 theo danh sách các cạnh đã được kết nạp vào hành trình.

Phân nhánh tìm hành trình ngắn nhất

    Tiếp tục phân nhánh từ đỉnh bên trái bằng cách sử dụng cạnh (2,1) vì số không ở vị trí này có hằng số rút gọn lớn nhất là 17 + 3 = 20 ( theo dòng 2 là 17, theo cột 1 là 3). Sau khi phân nhánh theo cạnh (2, 1) ma trận của nhánh bên trái có kích thước là 3 ×3. Vì đã đi qua (2, 1) nên ta cấm cạnh (2, 1) bằng cách đặt C[1, 2] = ∞, ta thu được ma trận sau:

	2	4	5
1	∞	2	30
3	1	∞	0
5	21	0	∞

Ma trận này có thể rút gọn được bằng cách bớt 1 tại cột 1 và bớt 2 đi ở dòng 1 để nhận được ma trận cấp 3:

	2	4	5
1	∞	0	28
3	0	∞	0
5	20	0	∞

     Ta có cận dưới của nhánh tương ứng là 81 + 1 + 2 = 84. Cây tìm kiếm cho đến bước này được thể hiện trong hình 6.
Chú ý rằng, sau khi đã chấp nhận n-2 cạnh vào hành trình thì ma trận còn lại sẽ có kích thước là 2 ×2. Hai cạnh còn lại của hành trình sẽ không phải chọn lựa nữa mà được kết nạp ngay vào chu trình (vì nó chỉ còn sự lựa chọn duy nhất). Trong ví dụ trên sau khi đã có các cạnh (6, 3), (4,6), (2, 1), (1,4) ma trận của nhánh bên trái nhất có dạng:

	2	5
3	∞	0
5	0	∞

     Vì vậy ta kết nạp nốt cạnh (3, 5), (5, 2) vào chu trình và thu được hành trình: 1, 4, 6, 3, 5, 2, 1 với chi phí là 104.
     Trong quá trình tìm kiếm, mỗi node của cây tìm kiếm sẽ tương ứng với một ma trận chi phí A. Ở bước đầu tiên ma trận chi phí tương ứng với gốc chính là ma trận C. Khi chuyển động từ gốc xuống nhánh bên trái xuống phĩa dưới, kích thước của các ma trận chi phí A sẽ giảm dần. Cuối cùng khi ma trận A có kích thước 2×2 thì ta chấm dứt việc phân nhánh và kết nạp hai cạnh còn lại để thu được hành trình của người du lịch. Dễ dàng nhận thấy ma trận cuối cùng rút gọn chỉ có thể ở một trong hai dạng sau:

	w	x
u	∞	0
v	0	∞

	w	x
u	0	∞
v	∞	0

     Trong đó u, v, x, y có thể là 4 đỉnh khác nhau hoặc 3 đỉnh khác nhau. Để xác định xem hai cạnh nào cần được nạp vào hành trình ta chỉ cần xét một phần tử của ma trận A:

if A[1, 1] = ∞ then 
 <Kết nạp cạnh (u, x), (v, w)> 
else 
 < Kết nạp cạnh (u, w), ( v, x) >;

     Bây giờ tất cả các node có cận dưới lớn hơn 104 có thể bị loại bỏ vì chúng không chứa hành trình rẻ hơn 104. Trên hình 6 chúng ta thấy chỉ có node có cận dưới là 101 < 104 là cần phải xét tiếp. Node này chứa các cạnh (6, 3), (4, 6) và không chứa cạnh (2, 1). Ma trận chi phí tương ứng với đỉnh này có dạng:

	1	2	4	5
1	∞	0	2	30
2	∞	∞	13	0
3	26	1	∞	0
5	0	21	0	∞

Việc phân nhánh sẽ dựa vào cạnh (5, 1) với tổng số rút gọn là 26. Quá trình rẽ nhánh tiếp theo được chỉ ra như trong hình

Phân nhánh hành trình ngắn nhất

 Hành trình 1, 4, 6, 3, 2, 5, 1 ; Độ dài 104.
     Như vậy chúng ta thu được hai hành trình tối ưu với chi phí là 104. Ví dụ trên cho thấy bài toán người du lịch có thể có nhiều phương án tối ưu. Trong ví dụ này hành trình đầu tiên nhận được đã là tối ưu, tuy nhiên điều này không thể mong đợi đối với những trường hợp tổng quát. Trong ví dụ trên chúng ta chỉ cần xét tới 13 node, trong khi tổng số hành trình của người du lịch là 120.
3. Thuật toán nhánh cận giải bài toán người du lịch.
     Các bước chính của thuật toán nhánh cận giải bài toán người du lịch được thể hiện trong thủ tục TSP. Thủ tục TSP xét hành trình bộ phận với Edges là cạnh đã được chọn và tiến hành tìm kiếm tiếp theo. Các biến được sử dụng trong thủ tục này là:
Edges - Số cạnh trong hành trình bộ phận;
A  - Ma trận chi phí tương ứng với kích thước (n-edges, n-edges)
cost  - Chi phí của hành trình bộ phận.
Mincost  - Chi phí của hành trình tốt nhất đã tìm được.
Hàm Reduce(A, k), BestEgde(A, k, r, c,beta) đã được xây dựng ở trên.

void TSP(Edges, cost, A) {
 cost = cost + Reduce(A, n - Edges);
 if (cost < MinCost){
  if (edges == n - 2){
   <bổxung nốt hai cạnh còn lại>;
  MinCost: = Cost;
  }
  else {
   BestEdge(A, n - eges, r, c, beta);
   LowerBound = Cost + beta;
   <Ngăn cấm tạo thành hành trình con>;
   NewA = < A loại bỏ dòng r cột c>;
   TSP(edges + 1, cost, NewA);/*đi theo nhánh trái*/
   <Khôi phục A bằng cách bổxung dòng r cột c>;
   if (LowerBound < MinCost){
    /* đi theo nhánh phải*/
    A[r, c] = ∞;
    TSP(edges, cost, A);
    A[r, c]: = 0;
   }
  }
  < Khôi phục ma trận A>;/* thêm lại các hằng sốrút gọn vào
          các dòng và cột tương ứng*/
 }
}/* end of TSP*/;

[Thuật Toán] Kiếm tra tính chất nguyên tố của một số.

Số nguyên tố là số tự nhiên lớn hơn 1 chia hết cho 1 và chính nó.
* Phương pháp đơn giản nhất để kiểm tra một số n có là số nguyên tố không là kiểm tra xem nó có chia hết cho một số m nằm trong khoảng từ 2 đến n-1 hay không. Nếu n chia hết cho m thì n không là số nguyên tố, ngược lại n là số nguyên tố.
* Ngoài ra do tính chất của Hợp số thì nó chắc chắn có ước số không vượt quá , vì vậy ta chỉ cần kiểm tra từ 2 đến .
* Chúng ta cũng có thể bỏ qua việc kiểm tra các trường hợp là bội số của 2 và 3 bằng cách kiểm tra các số lẻ. Các số lẻ này có dạng 6k-1 và 6k+1 và k = 0, 1, 2, 3...
Chương trình cài đặt.

#include<iostream>
#include<conio.h>
using namespace std;
bool isPrime(int n){
  if(n == 2 || n== 3) return true;
  if(n == 1 || n%2 == 0 || n%3 == 0) return false;
  int k = -1;
  do{
   k+=6;
   if(n%k == 0 || n%(k+2)==0) break;
  }while(k*k < n);// k < sqrt(n);
  return k*k>n;// return k > sqrt(n).
}
int main(){
 int n;
 cout<<"Input number:";
 cin>>n;
 if(isPrime(n)){
  cout<<n<<" is prime";
 }else{
  cout<<n<<" is not prime";
 }
 _getch();
 return 0;
}

[Thuật toán] Tìm đường đi giữa hai đỉnh của đồ thị.

Bài toán: Cho đồ thị G=(V, E). Trong đó V là tập đỉnh, E là tập cạnh của đồ thị. Hãy tìm đường đi từ đỉnh s ∈ Vtới đỉnh t ∈ V.
Thủ tục BFS(s) hoặc DFS(s) cho phép ta duyệt các đỉnh cùng một thành phần liên thông với s. Như vậy, nếu trong số các đỉnh liên thông với s chứa t thì chắc chắn có đường đi từ s đến t. Nếu trong số các đỉnh liên thông với s không chứa t thì không tồn tại đường đi từ s đến t. Do vậy, chúng ta chỉ cần gọi tới thủ tục DFS(s) hoặc BFS(s) và kiểm tra xem đỉnh t có thuộc thành phần liên thông với s hay không. Điều này được thực hiện đơn giản thông qua mảng trạng thái chuaxet[]. Nếu chuaxet[t] =False thì có nghĩa t cùng thành phần liên thông với s. Ngược lại chuaxet[t] = True thì t không cùng thành phần liên thông với s.
Để ghi nhận đường đi từ s đến t, ta sử dụng một mảng truoc[] thiết lập giá trị ban đầu là 0.Trong quá trình duyệt, ta thay thế giá trị của truoc[v] để ghi nhận đỉnh đi trước đỉnh v trong đường đi tìm kiếm từ s đến v. Khi đó, trong thủ tục DFS(v) ta chỉ cần thay đổi lại như sau:

void DFS( int v){ 
 chuaxet[v]:= FALSE; 
 for ( u ∈ke(v) ) { 
  if (chuaxet[u] ) { 
   truoc[u]=v; 
   DFS(u); 
  } 
 } 
}

Đối với thủ tục BFS(v) được thay đổi lại như sau:

void BFS(int u){ 
 queue = φ; 
 u <= queue; /*nạp u vào hàng đợi*/
 chuaxet[u] = false;/* đổi trạng thái của u*/
 while (queue ≠ φ) { /* duyệt tới khi nào hàng đợi rỗng*/
  queue<=p; /*lấy p ra từkhỏi hàng đợi*/
  for (v ∈ke(p) ) {/* đưa các đỉnh v kềvới p nhưng chưa được xét vào hàng đợi*/
   if (chuaxet[v] ) { 
    v<= queue; /*đưa v vào hàng đợi*/
    chuaxet[v] = false;/* đổi trạng thái của v*/
    truoc[v]=p; 
   } 
  } 
 } /* end while*/
}/* end BFS*/

Kết quả đường đi được đọc ngược lại thông qua thủ tục Result() như sau:

void Result(void){ 
 if(truoc[t]==0){ 
  <Không có đường đi từs đến t>; 
  return; 
 } 
 j = t; 
 while(truoc[j]!=s){ 
  <thăm đỉnh j>; 
  j=truoc[j]; 
 } 
 <thăm đỉnh s>; 
} 

Ví dụ. Tìm đường đi từ đỉnh 1 đến đỉnh 7 bằng thuật toán tìm kiếm theo chiều rộng với đồ thị dưới đây:

Tìm đường đi giữa đỉnh 1 đến đỉnh 7 của đồ thị

Ta có, BFS(1) = 1,2,3,11,4,6,12,13,7,8,9,10,5. Rõ ràng chuaxet[7] = True nên có đường đi từ đỉnh 1 đến đỉnh 7. Bây giờ ta xác định giá trị trong mảng truoc[] để có kết quả đường đi đọc theo chiều ngược lại. Truoc[7] = 6; truoc[6] = 2; truoc[2] =1=> đường đi từ đỉnh 1 đến đỉnh 7 là 1 =>2=>6=>7.
Chương trình cài đặt.

#include<iostream>
#include<conio.h>
using namespace std;
#define MAX  100 
#define TRUE  1 
#define FALSE  0
int n;//số đỉnh của đồ thị.
int truoc[MAX], chuaxet[MAX], queue[MAX];//mảng đánh dấu.
int A[MAX][MAX];// ma trận kề của đồ thị.
int s;//đỉnh đầu.
int t;//đỉnh cuối. 

void Init(void){ 
 freopen("lienth.IN", "r",stdin); 
 cin>>n; 
 cout<<"So dinh do thi: "<<n<<endl; 
 cin>>s>>t;
 cout<<"Dinh dau:"<<s<<endl;
 cout<<"Dinh cuoi:"<<t<<endl;
 for(int i=1; i<=n;i++){ 
  for(int j=1; j<=n;j++){ 
   cin>>A[i][j]; 
  }
 } 
 for(int i=1; i<=n;i++){ 
  chuaxet[i]=TRUE; 
  truoc[i]=0; 
 }
 fclose(stdin);
} 
void Result(void){ 
 if(truoc[t]==0){ 
  cout<<"Khong co duong di tu "<<s<< " den "<<t; 
  return; 
 } 
 cout<<"Duong di tu "<<s<<" den "<<t<<" la: "; 
 int j = t;
 cout<<t<<"<="; 
 while(truoc[j]!=s){ 
  cout<<truoc[j]<<"<="; 
  j=truoc[j]; 
 } 
 cout<<s; 
} 
/* Breadth First Search */
void BFS(int s) { 
 int dauQ, cuoiQ, u;
 dauQ=1;cuoiQ=1;//khởi tạo queue.
 queue[dauQ]=s;chuaxet[s]=FALSE; //thêm đỉnh đầu vào queue.
 while (dauQ<=cuoiQ){//queue chưa rỗng.
  u=queue[dauQ];//lấy đỉnh u trong queue.
  dauQ=dauQ+1; 
  for (int p=1; p<=n;p++){ 
   if(A[u][p] && chuaxet[p]){ 
    cuoiQ=cuoiQ+1;
    queue[cuoiQ]=p; 
    chuaxet[p]=FALSE;
    truoc[p]=u; 
   } 
  } 
 } 
} 

void main(void){ 
 Init();
 BFS(s); 
 Result();
 getch(); 
}

Ma trận liền kề được tải về tại đây.
Output của chương trình.

So dinh cua do thi: 13
Dinh dau: 1
Dinh Cuoi: 7
Duong di tu 1 den 7 la: 7<=6<=2<=1

Thuật toán

Dưới đây là danh sách thuật toán của blog.

1. Liệt kê hoán vị theo thứ tự từ điển.
2. Duyệt đồ thị theo chiều sâu.
3. Duyệt đồ thị theo chiều rộng.
4. Duyệt các thành phần liên thông của đồ thị. 
5. Tìm đường đi giữa hai đỉnh của đồ thị. 
6. Tìm đường đi và chu trình Euler. 
7. Tìm đường đi và chu trình Hamilton. 
8. Kiểm tra tính chất nguyên tố của một số.
9. Người du lịch.
10. Thuật toán quay lui - Back track.  
11. Tìm cây bao trùm.
12. Thuật toán Kruskal - Tìm cây khung nhỏ nhất của đồ thị 
13. Tìm đường đi ngắn nhất Dijkstra.
14. Tìm đường đi ngắn nhất Floyd.
15. Thuật toán Kruskal - Tìm cây khung nhỏ nhất.
16. Thuật toán Prim - Tìm cây khung nhỏ nhất. 

[Thuật toán] Duyệt các thành phần liên thông của đồ thị

Một đồ thị có thể liên thông hoặc không liên thông. Nếu đồ thị liên thông thì số thành phần liên thông của nó là 1. Điều này tương đương với phép duyệt theo thủ tục DFS() hoặc BFS() được gọi đến đúng một lần. Nếu đồ thị không liên thông (số thành phần liên thông lớn hơn 1) chúng ta có thể tách chúng thành những đồ thị con liên thông. Điều này cũng có nghĩa là trong phép duyệt đồ thị, số thành phần liên thông của nó bằng số lần gọi tới thủ tục DFS() hoặc BFS().
Để xác định số các thành phần liên thông của đồ thị, chúng ta sử dụng biến mới solt để nghi nhận các đỉnh cùng một thành phần liên thông trong mảng chuaxet[] như sau:
- Nếu đỉnh i chưa được duyệt, chuaxet[i]có giá trị 0;
- Nếu đỉnh i được duyệt thuộc thành phần liên thông thứ j=solt, ta ghi nhận chuaxet[i]=solt;
- Các đỉnh cùng thành phần liên thông nếu chúng có cùng giá trị trong mảng chuaxet[].
Với cách làm như trên, thủ tục BFS() có thể được sửa lại như sau:

void BFS(int u){ 
 queue = φ; 
 u <= queue; /*nạp u vào hàng đợi*/
 solt = solt+1; chuaxet[u] = solt; /*solt là biến toàn cục thiết lập giá trị0*/
 while (queue ≠ φ) { 
  queue<=p; /* lấy p ra từstack*/
  for v ∈ke(p) { 
   if (chuaxet[v] ) { 
    v<= queue; /*nạp v vào hàng đợi*/
    chuaxet[v] = solt; /* v có cùng thành phần liên thông với p*/
   } 
  } 
 } 
} 

Để duyệt hết tất cả các thành phần liên thông của đồ thị, ta chỉ cần gọi tới thủ tục liên thông như dưới đây:

void Lien_Thong(void){ 
 for (i=1; i≤n; i++) 
  chuaxet[i] =0; 
 for(i=1; i<=n; i++) 
  if(chuaxet[i]==0){ 
   solt=solt+1; 
   BFS(i); 
  } 
} 

Để ghi nhận từng đỉnh của đồ thị thuộc thành phần liên thông nào, ta chỉ cần duyệt các đỉnh có cùng chung giá trị trong mảng chuaxet[] như dưới đây:

void Result( int solt){ 
 if (solt==1){ 
  < Do thi la lien thong>; 
 } 
 for( i=1; i<=solt;i++){ 
  /* Đưa ra thành phần liên thông thứi*/
  for( j=1; j<=n;j++){ 
   if( chuaxet[j]==i) 
    <đưa ra đỉnh j>; 
  } 
 } 
}

Số thành phần liên thông	Kết quả duyệt BFS	Giá trị trong mảng chuaxet[]
0	Chưa thực hiện	Chuaxet[]={0,0,0,0,0,0,0,0,0}
1	BFS(1): 1,2,4,5	Chuaxet[]={1,1,0,1,1,0,0,0,0}
2	BFS(3): 3,6,7	Chuaxet[]={1,1,2,1,1,2,2,0,0}
3	BFS(8): 8,9	Chuaxet[]={1,1,2,1,1,2,2,3,3}

*Đỉnh 1,2,4,5 có giá trị 1trong mảng chuaxet[] thuộc thành phần liên thông thứ 1;
*Đỉnh 3, 6,7 cùng có giá trị 2 trong mảng chuaxet[] thuộc thành phần liên thông thứ 2;
*Đỉnh 8, 9 cùng có giá trị 3 trong mảng chuaxet[] thuộc thành phần liên thông thứ 3.
Chương trình cài đặt như sau:

#include<iostream>
#include <conio.h> 
#define MAX  100 
#define TRUE 1 
#define FALSE 0 
using namespace std;
int G[MAX][MAX], n, chuaxet[MAX], QUEUE[MAX], solt,i; 

void Init(){ 
 freopen("lienth.IN", "r", stdin); 
 cin>>n;
 cout<<" so dinh cua do thi n = "<<n;
 //nhập ma trận kề của đồ thị.
 for(int i=1; i<=n;i++){ 
  for(int j=1; j<=n;j++){ 
   cin>>G[i][j];
  } 
 } 
 //Khởi tạo giá trị ban đầu cho mảng chuaxet.
 for(int i=1; i<=n;i++) 
  chuaxet[i]=0; 
 solt=0; 
} 
void Result(int *chuaxet, int n, int solt){ 
 if(solt==1){ 
  printf("\n Do thi la lien thong"); 
  getch(); return; 
 } 
 for(int i=1; i<=solt;i++){ 
  printf("\n Thanh phan lien thong thu %d:",i); 
  for(int j=1; j<=n;j++){ 
   if( chuaxet[j]==i) 
    printf("%3d", j); 
  } 
 } 
} 
/* Breadth First Search */
void BFS(int G[][MAX], int n, int i, int *solt, int chuaxet[], int QUEUE[MAX]){ 
 int u, dauQ, cuoiQ, j; 
 dauQ=1; cuoiQ=1;
 QUEUE[cuoiQ]=i;chuaxet[i]=*solt; 
 while(dauQ<=cuoiQ){ 
  u=QUEUE[dauQ];
  dauQ=dauQ+1; 
  for(j=1; j<=n;j++){ 
   if(G[u][j]==1 && chuaxet[j]==0){ 
    cuoiQ=cuoiQ+1; 
    QUEUE[cuoiQ]=j; 
    chuaxet[j]=*solt; 
   } 
  } 
 } 
} 
void Lien_Thong(void){ 
 Init(); 
 for(i=1; i<=n; i++) 
  if(chuaxet[i]==0){ 
   solt=solt+1; 
   BFS(G, n, i, &solt, chuaxet, QUEUE); 
  } 
  Result(chuaxet, n, solt); 
  _getch();
} 
int main(void){ 
 Lien_Thong(); 
 return 0;
}

Dữ liệu file input lienth.IN như sau:

9
0 1 0 1 0 0 0 0 0
1 0 0 0 1 0 0 0 0
0 0 0 0 0 1 1 0 0
1 0 0 0 1 0 0 0 0
0 1 0 1 0 0 0 0 0
0 0 1 0 0 0 1 0 0
0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0

Trong đó: n = 9 là số đỉnh của đồ thị, tiếp theo đó là ma trận kề của đồ thị

Két quả khi chạy trương trình.

So dinh của do thi n = 9
Thanh phan lien thong thu 1: 1 2 4 5
Thanh phan lien thong thu 2: 3 6 7
Thanh phan lien thong thu 3: 8 9