Giáo trình Cấu trúc dữ liệu

 nút còn lại trong đồ thị. 
* ải thuật
 dà gắ hấ ừ v ến t cả
Gi : 
D g t t S ch c nú ã xác đ h được khoảng cách ngắn nhất 
từ nút ến các nút đ
D g t m g ist c ị c oả cách ngắn nhất này. Nếu 
nút u ở on t Di u] gi rị khoả cá ng nhất từ v cho đến u. Nếu 
u chưa t g thì ist ] a dài từ đế ột nút w nào đó trong S 
ng với khoảng cách từ w đến u. Mảng Dist sẽ được khởi tạo bằng giá trị trọng 
lượn nút còn lại nếu có cạnh trực tiếp, và bằng vô cùng 
(MA cạnh trực tiếp. 
ùn mộ ập để ứa ác t đ ịn
v đ ó. 
ùn mộ ản D để hứa giá tr cá kh ng
 tr g S hì st [ là á t ng ch ắn
 có ron S D [u chứ độ v n m
cộ
g từ nút v đến các
XINT) nếu không có
182 
a0
4 1
3 2
2 5
3 d=5
d=3
d=2
d=∞
S={0}
b
0
4 1
3 2
2 5
4
3
d=5
d=3
d=2
d=6
10
6
S={0,4}
c
0
4 1
3 2
2
2
1
3
d=4
d=3
d=2
d=5
6
S={0,4,2,1}
e
0
4 1
3 2
2
2
1
3 d=4
d=3
d=2
d=5
S={0,4,2,1,3}
f
0
4 1
3 2
2 5
2
4 1
3 d=4
d=3
d=2
d=5
d
S={0,4,2}
0
4 1
3 2
2 5
2
4 1
6 3
10
6
2
Hình 6.9 Mi đường đi ngắn nhất 
từ i trong đồ thị hình 6.8 
* Giải t
nh họa các bước áp dụng giải thuật Dijkstra tìm 
c nút còn lạ nút 0 cho đến tất cả cá
huật 
void Shortest_path(BYTE v, const long G[][MAX]) 
{ 
 neu G[i][j]=-1 thi Cost[i][j] = MAXINT */ 
][MAX] ; 
ien do dai cua duong di ngan nhat tu nut v den nut j 
hi dinh huong G co MAX nut; G duoc bieu dien boi 
long int Dist [MAX]
/* Cost chua do dai cac cung cua do thi G, voi qui uoc 
long Cost[MAX
/* Dist[j] : the h
 trong do t
 ma tran ke huu huong co trong so kich thuoc MAX x MAX */ 
 ; 
183 
/* S : Tap cac dinh (ke ca v) theo do cac duong di ngan nhat da xac lap */ 
) 
 for (j=0;j<MAX;j++) 
[j]= (G[i][j]==-1? MAXINT : G[i][j]); 
 Khoi tao S va Dist 
][i],i++ ); 
ist[v]=0 ; k=1; //dua v vao S 
hile (k < MAX) // xac dinh n-1 duong di tu dinh v 
n u sao cho: Dist[u] = min (Dist[j]), S[j]=0 
 while (j<MAX && S[j]!=0) j++; // Tim S[j] = 0 dau tien 
<MAX; j++) 
 u=j; 
 *) 
 S[u]=1 ; k++; 
0; w< MAX; w++) 
 if (S[w] == 0) 
if (Dist[u]+Cost[u][w] < Dist [w]) 
 Dist[w]= Dist[u]+Cost[u][w]; 
0; w<MAX; w++) 
AXINT) 
" " <<w <<": " << Dist[w]; 
 cout " <<w << ": Khong co duong di"; 
} 
V. ẮP THỨ TỰ TOPO
int S[MAX] ; 
 int w,i,j,u,k ; 
 for (i=0; i<MAX; i++
 Cost[i]
 //
 for (i=0; i< MAX; S[i]=0, Dist[i]=Cost[v
 S[v]=1; D
 w
 { 
 // cho
 j=0; 
 u=j; 
 for (j=u; j
 if (S[j] == 0 && Dist[u] > Dist[j]) 
 //Dua u vao tap S
 for (w=
 } 
 for (w=
 if (Dist[w] < M
 cout << "\n
 else 
 S : 
V.1. Khái niệm: 
Sắp thứ tự Topo là một quá trình sắp thứ tự các phần tử mà trong đó có 
định nghĩa một thứ tự bộ phận, nghĩa là một thứ tự cho trước trên một vài cặp 
các phần tử mà không phải trên tất cả các phần tử. 
Một thứ tự bộ phận của một tập hợp S là một quan hệ giữa các phần tử của 
S. Nó được ký hiệu bởi <, đọc là "đứng trước", và thỏa mãn ba tính chất sau đây 
đối với mọi phần tử phân biệt x, y, z của S: 
184 
(1) Nếu x < y và y < z thì x < z (tính bắc cầu) 
(3 ông phản xạ) 
Th ắp xếp các phần việc trong một 
công việ đó cho logic, nghĩa là khi ta thực hiện đến phần việc thứ i thì phải 
đảm bảo ần việc chuẩn bị cho nó trước rồi. Chẳng hạn như 
sắp xếp các tín ch ôn học sao cho khi đăng ký đến môn học i thì ta phải học 
qua các môn chuẩn bị trước cho nó. 
V.2 ậ
(2) Nếu x < y thì không có thể có y < x (tính phản xứng) 
) Không thể có x < x (tính kh
ông thường, bài toán Topo nhằm để s
c nào 
đã thực hiện các ph
ỉ m
. t toánThu : Để đơn giản, ta lấy ví dụ sau để minh họa: 
Gi ôn học sau: đại số 
tuyến t ăn bản (LTCB), Kỹ 
thuật lậ T), Cấu trúc dữ liệu (CTDL), Cấu trúc máy tính (CTMT), 
Cơ sở d uản trị giao tác (QTGT), Phân tích & thiết kế hệ thống 
thông
Yê
ả sử khoa công nghệ thông tin có giảng dạy các m
 Tin học cơ bản (THCB), Lập trình cính (ĐSTT),
p trình (KTL
ữ liệu (CSDL), Q
 tin (PTTK), Hệ quản trị cơ sở dữ liệu (HQT). 
u cầu: Hãy sắp xếp các môn học trên sao cho khi sinh viên đăng ký tín 
chỉ môn học thì phải đảm bảo các điều kiện sau: 
Môn học Các môn phải học trước 
Đại số tuyến tính 
Tin học cơ bản 
Lập trìn học cơ bản h căn bản Tin
Kỹ thuật lập trình Lập trình căn bản, Đại số tuyến tính 
Cấu trúc dữ liệu Kỹ thuật lập trình 
Cấu trúc máy tính 
Cơ sở dữ liệu Tin học cơ bản 
Quản trị giao tác Cơ sở dữ liệu 
Phân tích & thiết kế hệ thống thông tin 
Hệ quản trị cơ sở dữ liệu Cơ sở dữ liệu, Phân tích & thiết kế hệ thống thông tin 
Ta có đồ thị minh họa bài toán trên với qui ước: 
Cung với u là môn phải học trước môn v 
185 
§STT KTLT
THCB LTCB CTDL
CTMT CSD QTGTL
PTTK HQT
Hình 6.10 Đồ thị minh họa bài toán sắp thứ tự các môn học thỏa ràng buộc đã cho 
Giải thuật: 
(i) Ta tìm nút nào không có cung đến nó thì chọn, sau đó hủy tất cả các 
khi không còn nút nào trên đồ thị 
Lưu ý
cung từ nút đó đi ra. 
(ii) Lặp lại bước i cho đến 
: Nếu trong quá trình chọn mà không tìm được 1 nút không có cung 
hể thực hiện sắp 
được
Nút chọn Đồ thị còn lại 
ĐSTT 
tới nó thì có nghĩa là đồ thị có chu trình. Do đó, không t Topo 
. 
Áp dụng giải thuật trên với đồ thị hình 6.10 
THCB
CTMT CSDL QTGT
HQTPTTK
LTCB CTDL
KTLT
THCB 
CTMT CSDL QTGT
HQTPTTK
LTCB CTDL
KTLT
186 
187 
CTMT 
CSDL QTGT
HQTPTTK
LTCB
CTDL
KTLT
LTCB 
CSDL QTGT
HQTPTTK
CTDLKTLT
KTLT 
CSDL QTGT
HQTPTTK
CTDL
CTDL 
CSDL QTGT
HQTPTTK
CSDL 
QTGT
HQTPTTK
PTTK 
QTGT
HQT
QTGT HQT 
HQT 
V.3. Cài đặt: Do số nút trên đồ thị thường nhiều và số cung trên đồ thị 
tương đối ít nên để tiết kiệm bộ nhớ, ta chọn cấu trúc dữ liệu để lưu trữ là danh 
sách kề; trong đó mảng 1 chiều chứa danh sách các nút của đồ thị, còn danh sách 
liên kết sẽ chứa các cung trên đồ thị. Chẳng hạn như danh sách kề của đồ thị 
hình 6.10 như sau: 
188 
ÑSTT
THCB
CTMT
LTCB
KTLT
CTDL
CSDL
PTTK
QTGT
HQT
0
0
0
1
2
1
0
2
KTLT
1
1
LTCB CSDL
KTLT
CTDL
QTGT HQT
HQT
Hình 6.11 Danh sách kề của đồ thị hình 6.10 
Để biết được có bao nhiêu cung đi tới nút i, ta thêm trường count vào mảng 
chứa danh sách các nút. 
Dưới đây là chương trình sắp Topo với giả thiết của bài toán được chứa 
trong 1 file văn bản. File văn bản có dạng sau: 
Số n : số nút của đồ thị 
Ma trận số biểu diễn đồ thị 
UVí dụ U: File văn bản biểu diễn đồ thị hình 6.10 có dạng: 
10 
0 0 0 0 1 0 0 0 0 0 
0 0 0 1 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 1 1 
0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
#include 
#include 
#include 
#include 
#include 
struct node 
189 
 { 
 int dinh_ke; 
 struct node *next; 
 }; 
typedef struct node *NODEPTR; 
 struct phantu_ke 
 { 
 int count; 
 NODEPTR pF; 
 NODEPTR pL ; 
 }; 
 typedef struct phantu_ke Dothi[100]; 
 Dothi G; 
 int MAX; 
void Init_graph(Dothi G) 
{ 
 for(int i=0; i< MAX; G[i++].pF=NULL); 
} 
void Create_graph() 
{ 
 int i,j ; 
 NODEPTR p; 
 unsigned B[100][100]; 
 FILE *fptr; 
 if ( (fptr = fopen ("dt.txt", "rt")) == NULL ) 
 { printf("\nKhong the mo file dt.txt"); 
 getch(); 
 exit(0); 
 } 
 fscanf(fptr,"%d", &MAX); 
 for (i=0; i< MAX ; i++) 
 for (j=0; j<MAX; j++) 
 fscanf(fptr,"%d", &B[i][j]); 
 /// Khoi tao rong do thi 
 Init_graph(G); 
 //Tao count : so cung toi dinh j 
 for (j=0; j<MAX; j++) 
 { 
 G[j].count=0; 
 for (i=0; i< MAX; i++) 
190 
 if (B[i][j] ==1) G[j].count++; 
 } 
 for (i=0; i< MAX; i++) 
 for (j=0;j<MAX; j++) 
 if (B[i][j] == 1) 
 { 
p = (NODEPTR)malloc(sizeof(struct node)); 
p->next=NULL; 
p->dinh_ke=j; 
if( G[i].pF == NULL) G[i].pF=p; 
else G[i].pL->next=p; 
G[i].pL=p; 
 } 
} 
void Topo_Sort(Dothi G) 
{ 
 int Stack[100]; 
 int i,j,k, Sp=-1 ; 
 NODEPTR p; 
 for(i=0;i<MAX; i++) // Dua vao Stack tat cac cac nut khong co cung di 
 // toi no 
 if (G[i].count==0) { // day la cac task co the lam doc lap 
 Stack[++ Sp]=i; 
 } 
 for( i=0; i<MAX; i++) 
 { 
 if (Sp ==-1) 
 { 
 printf("\nCo chu trinh trong do thi!!!"); 
 exit(0); 
 } 
 j=Stack[Sp--]; printf("%5d",j); // Lay 1 nut trong Stack ra 
 p=G[j].pF; 
 while (p !=NULL) 
 { 
 k=p->dinh_ke; // k la ngon cua cung j --> k 
 G[k].count --; 
 if (G[k].count == 0) // khong co dinh nao toi nut k 
 { 
 Stack[++Sp]=k; 
191 
 } 
 p=p->next; 
 } 
 } 
} 
void main() 
{ clrscr(); 
 Create_graph(); 
 Topo_Sort(G); 
 getch(); 
} 
192 
UBÀI TẬP : 
1. Viết thủ tục ReadGraph để nhập vào các đỉnh và các cạnh của đồ thị G 
từ 1 file văn bản, biết rằng: 
- Nội dung của file văn bản là như sau: 
n 
u v trọngsố 
..... 
với : n : số nút của đồ thị G 
 u v trọngsố : chiều dài đường đi từ nút u đến nút v 
- Cấu trúc dữ liệu của đồ thị G được sử dụng là : 
a. Bảng kề 
b. Danh sách kề 
2. Cho một đồ thị G, viết thủ tục WriteGraph để in các đỉnh của đồ thị, và 
các cạnh của đồ thị ra màn hình. 
3. Cho một đồ thị G. Hãy xác định xem giữa 2 nút u và v có đường đi hay 
không? Nếu có, hãy xác định lộ trình từ nút u đến nút v. 
4. Cho một đồ thị G. Hãy xác định xem đồ thị G có liên thông hay không ? 
5. Cài đặt và kiểm tra thủ tục tìm đường đi ngắn nhất từ nút u cho đến nút v 
trong một đồ thị có hướng. Hãy xác định rõ lộ trình đó và cho biết chiều 
dài đường đi ngắn nhất là bao nhiêu? 
Minh họa các bước của giải thuật Dijkstra tìm đường đi ngắn nhất từ nút 0 
đến nút 5 trên đồ thị sau: 
0
1
2
5
4
3
12
25
30
20
30
24
80
80
50
30
40
193 
TÀI LIỆU THAM KHẢO 
[1] Cấu trúc dữ liệu - Ứng dụng Nguyễn Hồng Chương 1999 
 và cài đặt bằng C 
[2] Cấu trúc dữ liệu + Giải thuật Niklaus Wirth - 
 = Chương trình Người dịch Nguyễn Quốc Cường 
[3] Cấu trúc dữ liệu Đỗ Xuân Lôi 
[4] Cấu trúc dữ liệu Nguyễn Trung Trực 1992 
[5] Phân tích và thiết kế giải thuật Đinh Nghiệp 1992 
 ĐH BK Tp. Hồ Chí Minh 
[6] Course 12.2AB2 Data Structures Alison Cousey 1999 
and Algorithms II -