Giáo trình nghiên cứu các kiểu dữ liệu có cấu trúc

m lµ : - Ph­¬ng ph¸ p tèt nhÊ t trong mét sè tr­êng hîp cô thÓ . - Mang ®­îc nÐ t tiª u biÓ u cho tÊ t c¶ c¸ c ph­¬ng ph¸ p kh¸ c. - Gi¶ i thuË t dÔ hiÓ u vµ dÔ viÕ t. Cã thÓ ph© n c¸ c ph­¬ng ph¸ p s¾ p thø tù chÝ nh nh­ sau : - S¾ p thø tù néi (Internal Sorting) : Toµ n bé d÷ liÖ u sÏ ®­îc ®­a vµ o bé nhí trong ®Ó thùc hiÖ n viÖ c s¾ p xÕ p. Do toµ n bé d÷ liÖ u ®­îc ®­a vµ o bé nhí trong nª n kÝ ch th­íc d÷ liÖ u cÇ n s¾ p kh«ng lín, tuy nhiª n ­u ®iÓ m cña ph­¬ng ph¸ p nµ y lµ gi¶ i thuË t dÔ hiÓ u vµ thêi gian s¾ p xÕ p nhanh. - S¾ p thø tù ngo¹ i (External Sorting) : D÷ liÖ u nhiÒ u ph¶ i chøa trong tË p tin hoÆ c dÜ a, mçi lÇ n s¾ p thø tù ta chØ ®­a mét phÇ n cña d÷ liÖ u vµ o bé nhí ®Ó thùc hiÖ n. Do ®ã, thêi gian s¾ p xÕ p chË m. Trong ch­¬ng nµ y ta chØ ph© n tÝ ch c¸ c ph­¬ng ph¸ p s¾ p thø tù néi trª n danh s¸ ch kÒ . Khi s¾ p xÕ p ta ph¶ i chó ý ®Õ n mét sè kh¸ i niÖ m sau: - Khãa (Key) : Lµ d÷ liÖ u cña mçi phÇ n tö mµ ta c¨ n cø vµ o nã ®Ó s¾ p thø tù; khãa nµ y cã thÓ lµ ch÷ hoÆ c sè. - Thêi gian thùc hiÖ n : C¸ c gi¶ i thuË t s¾ p xÕ p néi th­êng ®­îc thùc hiÖ n b» ng c¸ ch so s¸ nh vµ ®æi chç hai phÇ n tö víi nhau. Do ®ã thêi gian thùc hiÖ n cña 1 gi¶ i thuË t s¾ p xÕ p phô thuéc vµ o hai yÕ u tè : + Sè lÇ n ®æi chç c¸ c phÇ n tö (®èi víi danh s¸ ch ®Æ c), hoÆ c sè lÇ n thay ®æi con trá (®èi víi danh s¸ ch liª n kÕ t). §© y lµ yÕ u tè chiÕ m nhiÒ u thêi gian nhÊ t. Ký hiÖ u : M(n) + Sè lÇ n so s¸ nh khãa. Ký hiÖ u : C(n), víi n lµ sè phÇ n tö trong danh s¸ ch. I. Mét sè ph­¬ng ph p¸ s¾p xÕp ®¬n gi¶n : I.1. S¾p xÕ p theo ph­¬ng ph¸p Bubble_Sort (ph­¬ng ph¸p næi bät) - Néi dung : Cho d∙ y A cã n phÇ n tö. Ta cho i duyÖ t d∙ y a[0],...,a[n-1]; nÕ u a[i-1] lín h¬n a[i] th× ta ho¸ n ®æi (a[i-1],a[i]). LÆ p l¹ i qu¸ tr× nh duyÖ t d∙ y nµ y cho ®Õ n khi kh«ng cã x¶ y ra viÖ c ®æi chç cña hai phÇ n tö. 157 VÝ dô: Ta s¾ p thø tù d∙ y sè sau : 26 33 35 29 19 12 32 B­íc 0 1 2 3 4 5 6 26 12 12 12 12 12 12 33 26 19 19 19 19 19 35 33 26 26 26 26 26 29 35 33 29 29 29 29 19 29 35 33 32 32 32 12 19 29 35 33 33 33 32 32 32 32 35 35 35 H× nh 8.1: Minh häa qu¸ tr× nh s¾p xÕ p qua ph­¬ng ph¸p Buble Sort - Ch­¬ng tr× nh: void Bubble_Sort(int A[100], int n) { int i,j,temp; for (i=1; i<n; i++) for (j=n-1;j>=i; j--) if (A[j-1] > A[j]) { temp = A[j-1]; A[j-1] = A[j]; A[j] = temp; } } Ta nhË n thÊ y ph­¬ng ph¸ p nµ y cã thÓ ®­îc c¶ i tiÕ n dÔ dµ ng. NÕ u ë lÇ n duyÖ t d∙y nµ o ®ã mµ kh«ng cã cã sù ®æi chç gi÷a hai phÇ n tö th× d∙y ®∙ cã thø tù vµ gi¶ i thuË t kÕ t thóc. Trong tr­êng hîp nµ y, ta dïng mét cê hiÖ u flag ®Ó ghi nhË n ®iÒ u nµ y, vµ gi¶ i thuË t Bubble Sort ®­îc c¶ i tiÕ n nh­ sau: #define FALSE 0 #define TRUE 1 void Bubble_Sort_Ad(int A[], int n) { int i,temp; unsigned char flag=TRUE; while (flag) { flag = FALSE ; for (i=0; i<n-1; i++) if (A[i] > A[i+1]) { temp = A[i]; 158 A[i] = A[i+1]; A[i+1] = temp; flag=TRUE; } } } * Ph© n tÝ ch: Gi¶ sö d∙ y cã n phÇ n tö. - Ph© n tÝ ch thêi gian thùc hiÖ n cña gi¶ i thuË t Bubble Sort ch­a c¶ i tiÕ n : + Sè lÇ n so s¸ nh C(n): Vßng lÆ p ®Ç u cã n-1 lÇ n duyÖ t Víi mçi i, ta l¹ i cã lÇ n duyÖ t phô thuéc vµ o i, cô thÓ nh­ sau: i Sè lÇ n duyÖ t 1 n-1 2 n-2 3 n-3 ... .... n-1 1 ( C(n) = 1 + 2 + 3 + n-2 + n-1 = (n-1)*n/2 BË c cña C(n) lµ O(n2) + Sè lÇ n ®æi chç M(n): ta kh«ng thÓ x¸ c ®Þ nh chÝ nh x¸ c sè lÇ n ®æi chæ 2 phÇ n tö trong d∙ y v× nã phô thuéc vµ o trË t tù hiÖ n cã trong d∙ y. Tuy nhiª n, ta biÕ t ch¾ c r» ng sè lÇ n ®æi chç tèi ®a sÏ b» ng C(n). Do ®ã, M(n) ≤ C(n) BË c cña M(n) lµ O(n2) VË y thêi gian thùc hiÖ n cña gi¶ i thuË t Bubble Sort ch­a c¶ i tiÕ n cã bË c O(n2). - Ph© n tÝ ch thêi gian thùc hiÖ n cña gi¶ i thuË t Bubble Sort c¶ i tiÕ n : + Sè lÇ n so s¸ nh C(n): Vßng lÆ p while cã k lÇ n duyÖ t ( k<= n-1) Cã n-i lÇ n so s¸ nh trong lÇ n duyÖ t thø i ( C(n) = (n-1) + (n-2) + .... + (n-k) = (n-k)*(n-k+1)/2 BË c cña C(n) lµ O(n2) + Sè lÇ n ®æi chç M(n): T­¬ng tù nh­ trª n, chóng ta cã M(n) ≤ C(n) 159 BË c cña M(n) lµ O(n2) VË y thêi gian thùc hiÖ n cña gi¶ i thuË t Bubble Sort c¶ i tiÕ n còng cã bË c O(n2). * NhËn xÐ t: Gi¶ i thuË t Bubble Sort dÔ hiÓ u nh­ng kh«ng tèi ­u v× thêi gian thùc hiÖ n gi¶ i thuË t chË m (cã bË c O(n2)) Gi¶ i thuË t Bubble Sort cã c¶ i tiÕ n kh«ng lµ m thay ®æi bË c nh­ng cã lµ m gi¶ m hÖ sè nª n chØ nhanh h¬n kh«ng ®¸ ng kÓ . I.2. Insertion Sort (Ph­¬ng ph¸p xen vµo ) a. Néi dung : XÐ t mét danh s¸ ch cã n phÇ n tö a0, a1, a2,..........,an-1, néi dung tæng qu¸ t cña ph­¬ng ph¸ p xen vµ o lµ : nÕ u trong danh s¸ ch ®∙ cã i-1 phÇ n tö tr­íc ®∙ cã thø tù, tiÕ p tôc so s¸ nh phÇ n tö ai víi i-1 phÇ n tö nµ y ®Ó t× m vÞ trÝ thÝ ch hîp cho ai xen vµ o. V× danh s¸ ch cã mét phÇ n tö th× tù nã ®∙ cã thø tù, do ®ã ta chØ cÇ n so s¸ nh tõ phÇ n tö thø 2 cho ®Õ n phÇ n tö thø n. VÝ dô : Cho m∙ ng A cã 5 phÇ n tö : a0 a1 a2 a3 a4 44 55 12 42 94 i= a0 a1 a2 a3 a4 1 44 55 12 42 94 2 44 55 12 42 94 3 12 44 55 42 94 4 12 42 44 55 94 H× nh 8.2: Minh häa qu¸ tr× nh s¾p xÕ p qua ph­¬ng ph¸p Insertion Sort b. Gi¶i thuËt : void Insertion_sort(int A[], int n) { int x; int i,j; for (i=1; i< n; i++) { x = A[i]; for (j=i-1; j>=0 && x<A[j]; j--) A[j+1] = A[j]; A[j+1]=x; } } 160 c. Ph©n tÝ ch - Sè lÇ n so s¸ nh C(n): + Tr­êng hîp tèt nhÊ t : Khi danh s¸ ch ®∙ cã thø tù ban ®Ç u, mçi phÇ n tö chØ cÇ n so s¸ nh mét lÇ n víi phÇ n tö ®øng tr­íc nã Cmin = n-1 + Tr­êng hîp xÊ u nhÊ t: Khi danh s¸ ch cã thø tù ng­îc, mét phÇ n tö A[i] sÏ ph¶ i so s¸ nh i-1 lÇ n Cmax = ∑ − = − = 1 1 2 )1(n i nni ≈ 2 2 n + Tr­êng hîp trung b× nh : Mçi phÇ n tö A[i] sÏ cã sè lÇ n so s¸ nh trung b× nh lµ i 2 lÇ n Caverage = 44 )1( 2 )1(...321 2nnnn ≈ − = −++++ BË c cña C(n) lµ O(n2) - Sè lÇ n ®æi chç M(n) G¸ n x = A[i] ; + Tr­êng hîp tèt nhÊ t : Sau lÇ n so s¸ nh duy nhÊ t ta l¹ i g¸ n x trë l¹ i cho A[i]; do ®ã víi n phÇ n tö sÏ cã n-1 lÇ n g¸ n nµ y, nª n : Mmin = 2* (n-1) + Tr­êng hîp xÊ u nhÊ t : Mçi b­íc sÏ cã i-1 lÇ n so s¸ nh t­¬ng øng víi i-1 lÇ n ®æi chç, céng thª m 2 lÇ n ®Ó g¸ n trÞ nh­ trª n; do ®ã ta cã : Mmax = Cmax + 2* (n-1) )1(*2 2 )1(*2 2 )1( 2 −+≈−+ − = nnnnn + Tr­êng hîp trung b× nh : Ta còng cã sè lÇ n ®æi chç trung b× nh lµ : Maverage= Caverage )1(*24 )1(*2 2 −+≈−+ nnn BË c cña M(n) còng lµ O(n2) I.3. Selection Sort (Ph­¬ng ph¸p lùa chän) : a. Néi dung : XÐ t mét danh s¸ ch cã n phÇ n tö a0, a1, a2,..........,an-1; ®Ó s¾ p thø tù mét danh s¸ ch, ta so s¸ nh tÊ t c¶ c¸ c phÇ n tö cña danh s¸ ch ®Ó chän ra mét phÇ n tö nhá nhÊ t ®­a vÒ ®Ç u danh s¸ ch; sau ®ã tiÕ p tôc chän phÇ n tö nhá nhÊ t 161 trong c¸ c phÇ n tö cßn l¹ i ®Ó t¹ o thµ nh phÇ n tö thø 2 trong danh s¸ ch. Qu¸ tr× nh nµ y ®­îc lÆ p ®i lÆ p l¹ i cho ®Õ n khi chän ra ®­îc phÇ n tö nhá thø (n-1) b. Gi¶i thuËt (®èi víi danh s¸ch ®Æc) void Selection_Sort(int A[], int n) { int min, vitrimin; int i,j; for (i=0; i< n-1; i++) { min = A[i]; vitrimin=i; for (j=i+1; j<n; j++) if (A[j] < min) { min = A[j]; vitrimin=j; } // Doi cho 2 phan tu A[i] va A[vitrimin] A[vitrimin] = A[i]; A[i] = min; } } c. Ph©n tÝ ch : - Sè lÇ n so s¸ nh C(n) : kh«ng phô thuéc vµ o thø tù ban ®Ç u cña danh s¸ ch, mµ phô thuéc vµ o sè lÇ n thùc hiÖ n cña hai vßng For lång nhau. Vßng For ngoµ i sÏ lÆ p n-1 lÇ n, víi mçi lÇ n lÆ p th× nã sÏ thùc hiÖ n vßng For trong. Sè lÇ n so s¸ nh cña vßng For trong tïy thuéc vµ o chØ sè i, tøc lµ vÞ trÝ ®ang xÐ t : i= 0 ' so s¸ nh (n-1) lÇ n (j= 1 ÷ n-1) i= 1 ' so s¸ nh (n-2) lÇ n (j= 2 ÷ n-1) .... i= n-2 ' so s¸ nh 1 lÇ n (j:= n-1 ÷ n-1) Suy ra sè lÇ n so s¸ nh lµ : C = (n-1) + (n-2) + (n-3) + ... + 1 = i n n i n = −∑ = − 1 1 1 2 ( ) ⇒ C(n) ≈ 2 2 n sè lÇ n ®æi chç 162 BË c cña C(n) còng lµ O(n2) Nh­ vË y sè lÇ n so s¸ nh ë ph­¬ng ph¸ p chän lùa lu«n lu«n t­¬ng ®­¬ng víi sè lÇ n so s¸ nh trong tr­êng hîp xÊ u nhÊ t cña ph­¬ng ph¸ p xen vµ o - Sè lÇ n ®æi chç M(n) : Tïy thuéc thø tù ban ®Ç u cña danh s¸ ch, nã sÏ nhá nhÊ t khi c¸ c khãa ban ®Ç u ®∙ cã thø tù vµ lín nhÊ t khi khãa cã thø tù ng­îc. II. Quick_Sort : (S¾p xÕ p theo ph­¬ng ph¸p ph©n ®o¹n) 1. Néi dung: Chän mét phÇ n tö bÊ t kú trong danh s¸ ch lµ m ®iÓ m chèt x, so s¸ nh vµ ®æi chç nh÷ng phÇ n tö trong danh s¸ ch nµ y ®Ó t¹ o ra 3 phÇ n: phÇ n cã gi¸ trÞ nhá h¬n x, phÇ n cã gi¸ trÞ b» ng x, vµ phÇ n cã gi¸ trÞ lín h¬n x. L¹ i tiÕ p tôc chia 2 phÇ n cã gi¸ trÞ nhá h¬n vµ lín h¬n x theo nguyª n t½ c nh­ trª n; qu¸ tr× nh chia phÇ n sÏ kÕ t thóc khi mçi phÇ n chØ cßn l¹ i mét phÇ n tö, lóc nµ y ta ®∙ cã mét danh s¸ ch cã thø tù. VÝ dô: XÐ t d∙ y 26 33 35 29 19 12 32 $ LÇ n chia phÇ n thø nhÊ t : Chän phÇ n tö chèt cã khãa lµ 29, ®Æ t lµ x 26 33 35 29 19 12 32 i ' ) j Dïng hai biÕ n chØ sè i vµ j ®Ó duyÖ t tõ hai ®Ç u danh s¸ ch ®Õ n x. NÕ u i gÆ p phÇ n tö lín h¬n hay b» ng x sÏ dõng l¹ i, j gÆ p phÇ n tö nhá h¬n hay b» ng x sÏ dõng l¹ i, råi ®æi chç hai phÇ n tö nµ y; sau ®ã tiÕ p tôc duyÖ t cho ®Õ n khi i>j th× ngõng l¹ i. Lóc nµ y d∙ y sÏ cã 3 phÇ n kh¸ c nhau nh­ h× nh vÏ sau : 26 33 35 29 19 12 32 i j 26 12 35 29 19 33 32 i j 26 12 19 29 35 33 32 ij 26 12 19 29 35 33 32 j i $ LÇ n chia phÇ n thø hai cho d∙ y con 26 12 19, chän chèt x=12 26 12 19 ' 12 26 19 i j j i KÕ t thóc ta sÏ cã hai phÇ n : 12 ; 26 19 $ LÇ n chia phÇ n thø 3 cho d∙ y con 26 19, chän chèt x=26 26 19 ' 19 26 KÕ t thóc qu¸ tr× nh chia nhá d∙ y con 26 12 19 i j j i 163 - LÇ n chia phÇ n thø 4 cho d∙ y con 35 33 32, chän chèt x= 33 35 33 32 ' 32 33 35 ' 32 33 35 i j ij j i KÕ t thóc ta sÏ cã ba phÇ n : 32 ; 33 ; 35 §Õ n ®© y qu¸ tr× nh chia phÇ n kÕ t thóc v× tÊ t c¶ c¸c phÇ n chØ cã mét phÇ n tö, lóc nµ y ta sÏ cã mét danh s¸ ch cã thø tù lµ : 12 19 26 29 32 33 35 2. Gi¶i thuËt: a. Gi¶i thuËt kh«ng ®Ö quy: - Ta t¹ o mét Stack, mçi phÇ n tö cña Stack cã 2 thµ nh phÇ n lµ q, r chøa chØ sè ®Ç u vµ chØ sè cuèi cña d∙y cÇ n s¾ p. Ban ®Ç u, Stack[0].q = 0 vµ Stack[0].r =n-1 - TiÕ n hµ nh ph© n ho¹ ch d∙y sè gåm c¸ c sè b¾ t ®Ç u tõ chØ sè q ®Õ n chØ sè r - Sau mçi lÇ n chia phÇ n, ta kiÓ m tra xem phÇ n cã gi¸ trÞ nhá h¬n chèt vµ phÇ n cã gi¸ trÞ lín h¬n chèt nÕ u cã tõ 2 phÇ n tö trë lª n th× ®­a vµ o Stack. Sau mçi lÇ n ph© n ho¹ ch, ta l¹ i lÊ y d∙ y sè míi tõ Stack ra ph© n ho¹ ch tiÕ p. - Qu¸ tr× nh cø nh­ thÕ cho tíi khi Stack rçng th× kÕ t thóc. * Ch­¬ng tr× nh: void Quick_Sort(int A[100], int n) { struct Element_Stack // kiÓ u phÇ n tö trong Stack { int q, r; } ; Element_Stack Stack[50]; // Stack cã tèi ®a 50 phÇ n tö int sp=0; // con trá Stack, khëi t¹ o sp=0 int i,j,x,q,r,temp; Stack[0].q =0 ; // chØ sè ®Ç u cña m¶ ng cÇ n s¾ p Stack[0].r =n-1; // chØ sè cuèi cña m¶ ng cÇ n s¾ p do { // LÊ y mét ph© n ho¹ ch ra tõ Stack q = Stack[sp].q ; r =Stack[sp].r ; sp--; // Xãa 1 phÇ n tö khái Stack do { // Ph© n ®o¹ n d∙ y con a[q],..., a[r] x = A[(q+r) / 2] ; // LÊ y phÇ n tö gi÷a cña d∙ y cÇ n s¾ p thø tù lµ m chèt 164 i = q; j =r; do { while (A[i] < x) i++; //T× m phÇ n tö ®Ç u tiª n cã trÞ lín h¬n hay b» ng x while (A[j] > x) j--; //T× m phÇ n tö ®Ç u tiª n cã trÞ nhá h¬n hay b» ng x if (i<=j) // §æi chç A[i] víi A[j] { temp = A[i]; A[i] =A[j]; A[j] = temp; i++ ; j--; } } while (i<=j); if (i<r) // phÇ n thø ba cã tõ 2 phÇ n tö trë lª n { // §­a vµ o Stack chØ sè ®Ç u vµ chØ sè cuèi cña phÇ n thø ba sp++; Stack[sp].q=i; Stack[sp].r=r; } r = j ; // ChuÈ n bÞ vÞ trÝ ®Ó ph© n ho¹ ch phÇ n cã gi¸ trÞ nhá h¬n chèt } while (q< r); } while (sp!=-1); // Ket thuc khi Stack rong } b. Gi¶i thuËt Quick Sort ®Ö qui: vÒ c¬ chÕ thùc hiÖ n th× còng gièng nh­ gi¶ i thuË t kh«ng ®Ö qui, nh­ng ta kh«ng kiÓ m so¸ t Stack mµ ®Ó cho qu¸ tr× nh gäi ®Ö qui tù t¹ o ra Stack. * Ch­¬ng tr× nh: void Sort(int A[], int q,int r) { int temp; int i=q; int j=r; int x = A[(q+r) / 2] ; //LÊ y phÇ n tö gi÷a cña d∙ y cÇ n s¾ p thø tù lµ m chèt do { // Ph© n ®o¹ n d∙ y con a[q],..., a[r] while (A[i] < x) i++; //T× m phÇ n tö ®Ç u tiª n cã trÞ lín h¬n hay b» ng x while (A[j] > x) j--; //T× m phÇ n tö ®Ç u tiª n cã trÞ nhá h¬n hay b» ng x if (i<=j) // Doi cho A[i] voi A[j] { temp = A[i]; A[i] =A[j]; 165 A[j] = temp; i++ ; j--; } } while (i<=j); if (q<j) // phÇ n thø nhÊ t cã tõ 2 phÇ n tö trë lª n Sort(A,q,j); if (i<r) // phÇ n thø ba cã tõ 2 phÇ n tö trë lª n Sort (A,i,r); } void Quick_Sort(int A[], int n) { Sort( A,0,n-1); // Gäi hµ m Sort víi phÇ n tö ®Ç u cã chØ sè 0 ®Õ n // phÇ n tö cuèi cïng cã chØ sè n-1 } 3. Ph©n tÝ ch : Ta nhË n thÊ y nhê chia thµ nh nh÷ng d∙ y con trong mçi lÇ n chia phÇ n sÏ cã kh¶ n¨ ng gi¶ m ®­îc sè lÇ n so s¸ nh. Tuy nhiª n cßn tïy thuéc vµ o viÖ c chän phÇ n tö chèt vµ thø tù ban ®Ç u cña d∙ y. Khi chän vÞ trÝ phÇ n tö chèt lµ ë gi÷a th× nÕ u chia ta sÏ ®­îc c¸c d∙y con cã sè phÇ n tö gÇ n b» ng nhau vµ do ®ã sÏ gi¶ m ®­îc sè lÇ n so s¸ nh. - Tr­êng hîp tèt nhÊ t: §Ó dÔ tÝ nh C(n) vµ M(n), ta gi¶ sö sè nót cña danh s¸ ch cÇ n s¾ p xÕ p lµ n = 2m Víi 1 danh s¸ ch ban ®Ç u : n lÇ n so s¸ nh (trong c¶ 2 h­íng quÐ t) Víi 2 danh s¸ ch con tiÕ p theo: nhá h¬n hoÆ c b» ng n/2 lÇ n so s¸ nh trong mçi danh s¸ ch con Víi 4 danh s¸ ch con tiÕ p theo: nhá h¬n hoÆ c b» ng n/4 lÇ n so s¸ nh trong mçi danh s¸ ch con ..... Víi n danh s¸ ch con cuèi cïng: nhá h¬n hoÆ c b» ng n/n lÇ n so s¸ nh trong mçi danh s¸ ch. + Tæng sè lÇ n so s¸ nh C(n): C(n) ≤ (1*n) + (2* n/2 ) + (4* n/4 ) + ... + (n* n/n ) ≤ n + n + n + ... + n V× ta sÏ cã nhiÒ u nhÊ t lµ m lÇ n chia nª n: C(n) ≤ m * n = n lgn 166 VË y bË c cña C(n) lµ O(nlgn) + Tæng sè lÇ n ®æi chæ M(n): Sè lÇ n ®æi chæ ph¶ i Ý t h¬n hoÆ c b» ng sè lÇ n so s¸ nh: M(n) ≤ C(n) BË c cña M(n) còng lµ O(nlgn) - Tr­êng hîp xÊ u nhÊ t: Víi gi¶ i thuË t Quick Sort, tr­êng hîp xÊ u nhÊ t khi nót lµ m chèt lóc nµ o còng ë ®Ç u hay cuèi danh s¸ ch sau mçi lÇ n chia phÇ n. Hai danh s¸ ch con suy biÕ n thµ nh mét danh s¸ ch con cã sè nót bít ®i 1. Trong tr­êng hîp nµ y: Víi danh s¸ ch ban ®Ç u : n lÇ n so s¸ nh Víi danh s¸ ch con tiÕ p theo : n-1 lÇ n so s¸ nh Víi danh s¸ ch con tiÕ p theo : n-2 lÇ n so s¸ nh .... Víi danh s¸ ch con cuèi cïng : 1 lÇ n so s¸ nh + Tæng sè lÇ n so s¸ nh C(n): C(n) = n + (n-1) + (n-2) + ... + 1 = n(n+1) /2 BË c cña C(n) lµ O(n2) + Tæng sè lÇ n ®æi chæ M(n): Sè lÇ n ®æi chæ ph¶ i Ý t h¬n hoÆ c b» ng sè lÇ n so s¸ nh: M(n) ≤ C(n) BË c cña M(n) còng lµ O(n2) - Tr­êng hîp trung b× nh : Tr­êng hîp trung b× nh th× C(n) vµ M(n) cã bË c ë kho¶ ng gi÷a O(nlgn) vµ O(n2) III. Heap Sort (S¾p xÕ p kiÓ u vun ®èng) III.1. §Þ nh nghÜ a Heap: Heap lµ c© y nhÞ ph© n gÇ n ®Ç y ®­îc cµ i ®Æ t b» ng m¶ ng mét chiÒ u víi c¸ c nót trª n Heap cã néi dung lín h¬n hay b» ng néi dung cña c¸ c nót con cña nã. VÝ dô: Ta cã d∙ y sè sau: 55 24 78 15 37 62 94 41 09 82 (0) (1) (2) (3) (4) (5) (6) (7) (8) (9) th× c© y nhÞ ph© n ban ®Ç u cña d∙ y lµ : 167 55 24 15 37 78 62 94 41 09 82 (0) (1) (2) (3) (4) (5) (6) (7) (8) (9) vµ heap cña d∙ y sau khi vun ®èng sÏ lµ : 94 82 41 37 78 62 55 15 09 24 III.2. ThuËt to¸n Heap Sort: a. Néi dung: - Tr­íc tiª n ta cµ i ®Æ t hµ m Adjust (A, r,n) ®Ó ®iÒ u chØ nh c© y cã gèc ë vÞ trÝ r víi n nót thµ nh ®èng víi gi¶ thiÕ t hai c© y con ®∙ lµ ®èng. L­u ý : Do gi¶ thiÕ t lµ ta ®∙ cã hai c© y con lµ ®èng nª n ta ph¶ i vun ®èng tõ d­íi lª n. Trong c© y chØ cã c¸ c nót víi vÞ trÝ 0,1,..., n/2-1 míi lµ c¸ c nót gèc cã c© y con. Do ®ã, ta chØ cÇ n vun ®èng c¸ c c© y ë vÞ trÝ 0,1,..., n/2-1. - Do sau khi vun ®èng th× nót ë vÞ trÝ 0 sÏ cã néi dung lín nhÊ t nª n ta sÏ ho¸ n ®æi néi dung cña A0 víi An-1. - Ta tiÕ p tôc Adjust(0, n-1) ®Ó vun ®èng c© y víi gèc ë nót cã vÞ trÝ 0 vµ sè nót lµ n-1 nót cßn l¹ i (A0, A1,..., An-2). Sau ®ã, sÏ ho¸ n ®æi néi dung cña A0 víi An-2. - Qu¸ tr× nh trª n tiÕ p tôc cho ®Õ n khi c© y ®­îc vun ®èng chØ cßn 1 nót th× dõng l¹ i. Cuèi cïng, ta ®∙ cã d∙ y ®∙ ®­îc s¾ p theo thø tù t¨ ng dÇ n. * ThuËt to¸n Adjust (A,r,n) - Ta so s¸ nh néi dung cña 2 nót con t× m ra néi dung cña nót con lín h¬n - So s¸ nh tiÕ p néi dung cña nót con lín h¬n víi néi dung cña nót gèc : + NÕ u néi dung cña nót con ®ã mµ nhá h¬n néi dung cña nót gèc th× c© y con ®ã lµ ®èng. 168 + NÕ u néi dung cña nót con ®ã mµ lín h¬n néi dung cña nót gèc th× di chuyÓ n néi dung cña nót con lª n vÞ trÝ cña nót gèc r. Sau ®ã, ®iÒ u chØ nh tiÕ p c© y cã gèc ë vÞ trÝ nót lµ nót con lín h¬n ®ã. b. Cµi ®Æt: void Adjust(int A[], int r, int n) { int j=2*r+1; // vi tri nut con ben trai int x=A[r]; int cont=TRUE; while (j<=n-1 && cont) { if (j<n-1) // luc nay r moi co nut con ben phai. Neu j=n-1 thi r khong // co nut con ben phai thi khong can so sanh if (A[j] < A[j+1]) // tim vi tri nut con lon hon j++; if (A[j] <=x) cont=FALSE; else { // di chuyen nut con j len r A[r]= A[j]; r=j ; // xem lai nut con co phai la dong khong j=2*r+1; } } A[r]=x; } void Heap_sort(int A[], int n) { int i, temp; for (i=n/2-1; i>=0; i--) // Tao heap ban dau Adjust(A, i,n); for (i=n-2; i>=0; i--) { temp= A[0]; // Cho A[0] ve cuoi heap A[0] = A[i+1]; A[i+1] = temp; Adjust(A,0,i+1); // Dieu chinh lai heap tai vi tri 0 // Luc nay, 2 cay con o vi tri 1 va 2 da la heap } } 169 c. VÝ dô: Dïng thuË t to¸n heap sort ®Ó s¾p xÕp d∙y sè sau theo chiÒu t¨ng dÇn: 55 24 78 15 37 62 94 41 09 82 (0) (1) (2) (3) (4) (5) (6) (7) (8) (9) n = 10; * C© y nhÞ ph© n ban ®Ç u cña d∙ y lµ : 55 24 15 37 78 62 94 41 09 82 (0) (1) (2) (3) (4) (5) (6) (7) (8) (9) Vun c© y ban ®Ç u thµ nh ®èng b» ng gi¶ i thuË t Adjust * Vun ®èng : Vun tõ d­íi lª n, Trong c© y chØ cã c¸ c nót 0, 1,2,... n/2-1=4 míi lµ c¸ c nót gèc for (i=n/2-1; i>=0; i--) // Tao heap ban dau Adjust(A, i,n); + Vun c© y cã gèc lµ n/2 -1 = + 55 24 15 82 78 62 94 41 09 37 + Vun c© y cã gèc lµ n/2 -2 = , 55 24 41 82 78 62 94 15 09 37 + Vun c© y cã gèc lµ n/2 -2 = - 170 55 24 41 82 94 62 78 15 09 37 + Vun c© y cã gèc lµ n/2 -2 = . 55 82 41 24 94 62 78 15 09 37 Do sau khi ho¸ n ®æi th× c© y con kh«ng ph¶ i lµ ®èng nª n ta Adjust l¹ i: 55 82 41 37 94 62 78 15 09 24 + Vun c© y cã gèc lµ n/2 -2 = / 94 82 41 37 55 62 78 15 09 24 Do sau khi ho¸ n ®æi th× c© y con kh«ng ph¶ i lµ ®èng nª n ta Adjust l¹ i: 94 82 41 37 78 62 55 15 09 24 171 * Ta ®æi chç A[0] víi A[n-1] vµ sau ®ã Adjust l¹ i c© y ë vÞ trÝ 0 víi sè nót gi¶ m ®i 1, vµ qu¸ tr× nh trª n sÏ dõng l¹ i khi sè nót b» ng 0. for (i=n-2; i>=0; i--) { temp= A[0]; // Cho A[0] ve cuoi heap A[0] = A[i+1]; A[i+1] = temp; Adjust(A,0,i+1); // Dieu chinh lai heap tai vi tri 0 // Luc nay, 2 cay con o vi tri 1 va 2 da la heap } + i = n-2 = 8: §æi chæ A[0] víi A[n-1] th× d∙ y {A[n-1]} ®∙ s¾ p xÕ p. 24 82 41 37 78 62 55 15 09 94 Sau ®ã, ta l¹ i vun c© y cã gèc lµ 0 vµ sè nót lµ n-1 =9 thµ nh ®èng. 82 24 41 37 78 62 55 15 09 0 82 41 24 37 78 62 55 15 09 + i = 7: §æi chæ A[0] víi A[n-2] th× d∙ y {A[n-2], A[n-1]} ®∙ s¾ p xÕ p. 09 41 24 37 78 62 55 15 82 Sau ®ã, ta l¹ i vun c© y cã gèc lµ 0 vµ sè nót lµ n-2=8 thµ nh ®èng. 172 78 41 24 37 09 62 55 15 0 78 41 24 37 62 09 55 15 + i = 6: §æi chæ A[0] víi A[n-3] th× d∙ y {A[n-3], A[n-2], A[n-1]} ®∙ s¾ p xÕ p. 15 41 24 37 62 09 55 78 Sau ®ã, ta l¹ i vun c© y cã gèc lµ 0 vµ sè nót lµ n-3=7 thµ nh ®èng. 62 41 24 37 15 09 55 0 62 41 24 37 55 09 15 + i = 5: §æi chæ A[0] víi A[n-4] th× d∙ y {A[n-4], A[n-3], A[n-2], A[n-1]} ®∙ s¾ p xÕ p. 15 41 24 37 55 09 62 Sau ®ã, ta l¹ i vun c© y cã gèc lµ 0 vµ sè nót lµ n-4=6 thµ nh ®èng. 55 41 24 37 15 09 173 + i = 4: §æi chæ A[0] víi A[n-5] th× d∙ y {A[n-5],A[n-4], A[n-3], A[n-2], A[n-1]} ®∙ s¾ p xÕ p. 09 41 24 37 15 55 Sau ®ã, ta l¹ i vun c© y cã gèc lµ 0 vµ sè nót lµ n-5=5 thµ nh ®èng. 41 09 24 37 15 0 41 37 24 09 15 + i = 3: §æi chæ A[0] víi A[n-6] th× d∙ y {A[n-6], A[n-5],A[n-4], A[n-3], A[n-2], A[n-1]} ®∙ s¾ p xÕ p. 09 37 24 37 15 Sau ®ã, ta l¹ i vun c© y cã gèc lµ 0 vµ sè nót lµ n-6=4 thµ nh ®èng. 37 09 24 15 0 37 24 09 15 + i = 2: §æi chæ A[0] víi A[n-7] th× d∙ y {A[n-7], A[n-6], A[n-5],A[n-4], A[n-3], A[n-2], A[n-1]} ®∙ s¾ p xÕ p. 09 24 37 15 Sau ®ã, ta l¹ i vun c© y cã gèc lµ 0 vµ sè nót lµ n-7=3 thµ nh ®èng. 174 24 09 15 + i = 1: §æi chæ A[0] víi A[n-8] th× d∙ y {A[n-8], A[n-7], A[n-6], A[n- 5],A[n-4], A[n-3], A[n-2], A[n-1]} ®∙ s¾ p xÕ p. 15 09 24 Sau ®ã, ta l¹ i vun c© y cã gèc lµ 0 vµ sè nót lµ n-7=3 thµ nh ®èng. 15 09 + i = 0: §æi chæ A[0] víi A[n-9] th× d∙ y {A[n-9], A[n-8], A[n-7], A[n-6], A[n-5],A[n-4], A[n-3], A[n-2], A[n-1]} ®∙ s¾ p xÕ p. 09 15 Cuèi cïng, d∙ y ®∙ ®­îc s¾ p theo thø tù t¨ ng dÇ n. IV. Merge Sort (S¾p xÕ p kiÓ u trén) a. Néi dung: Merge Sort lµ ph­¬ng ph¸ p s¾ p xÕ p b» ng c¸ ch trén hai danh s¸ ch ®∙ cã thø tù thµ nh mét danh s¸ ch cã thø tù. Ph­¬ng ph¸ p nµ y gåm nhiÒ u b­íc nh­ sau: a.1. Xem danh s¸ ch cÇ n s¾ p xÕ p nh­ n danh s¸ ch con ®∙ cã thø tù, mçi danh s¸ ch con cã 1 phÇ n tö. Trén tõng cÆ p hai danh s¸ ch con kÕ cË n, ta sÏ ®­îc n/2 danh s¸ ch con ®∙ cã thø tù, mçi danh s¸ ch con cã 2 nót. a.2. Ta tiÕ p tôc xem danh s¸ ch cÇ n s¾ p xÕ p nh­ n/2 danh s¸ ch con ®∙ cã thø tù, mçi danh s¸ ch con cã 2 phÇ n tö. Trén tõng cÆ p hai danh s¸ ch con kÕ cË n, ta sÏ ®­îc n/4 danh s¸ ch con ®∙ cã thø tù, mçi danh s¸ ch con cã 4 nót. a.3. Qu¸ tr× nh trª n cø tiÕ p tôc cho ®Õ n khi ®­îc 1 danh s¸ ch con cã n phÇ n tö. VÝ dô: Ta dïng ph­¬ng ph¸ p Merge Sort ®Ó s¾ p xÕ p d∙ y sè sau: 55 24 78 15 37 62 94 41 09 82 175 25 55 25 55 45 40 40 45 10 90 10 90 85 35 35 85 Böôùc 1 Böôùc 2 4025 5545 3510 9085Böôùc 3 Böôùc 4 10 25 35 40 45 55 85 90 H× nh 8.3: C¸c b­íc trén cña gi¶i thuËt Merge Sort. b. Gi¶i thuËt: C¸ c biÕ n sö dông: - A lµ d∙ y sè cÇ n s¾ p cã n phÇ n tö - low1, up1, low2, up2 lµ cË n d­íi vµ cË n trª n cña 2 danh s¸ ch con ®ang trén - size lµ kÝ ch th­íc cña danh s¸ ch con, ë b­íc trén 1 th× size=1, ë b­íc trén 2 th× size=2, ë b­íc trén 3 th× size=4, ë b­íc trén 4 th× size=8,... #define MAXLIST 100 int A[MAXLIST]; void mergesort(int A[], int n) { int i, j, k, low1, up1, low2, up2, size; int dstam[MAXLIST]; size = 1; while(size < n) { low1 = 0; k = 0; while(low1+size < n) { low2 = low1+size; up1 = low2-1; up2 = (low2+size-1 < n) ? low2+size-1 : n-1; for(i = low1, j = low2; i <= up1 && j <= up2; k++) if(A[i] <= A[j]) dstam[k] = A[i++]; else dstam[k] = A[j++]; 176 for(; i <= up1; k++) dstam[k] = A[i++]; for(; j <= up2; k++) dstam[k] = A[j++]; low1 = up2+1; } for(i = low1; k < n; i++) dstam[k++] = A[i]; for(i = 0; i < n; i++) // gan nguoc tra lai cho A A[i] = dstam[i]; size *= 2; } } c. Ph©n tÝ ch Gi¶ i thuË t Merge Sort kh«ng hiÖ u qu¶ vÒ mÆ t bé nhí v× cã dïng thª m danh s¸ ch t¹ m trong qu¸ tr× nh s¾ p xÕ p. - Sè lÇ n so s¸ nh C(n) : Gi¶ i thuË t Merge Sort cã log2n b­íc trén, cã Ý t h¬n n lÇ n so s¸ nh trong tõng b­íc Suy ra C(n) < nlog2n BË c cña C(n) lµ O(nlgn) - Sè lÇ n ®æi chæ M(n) : Gi¶ i thuË t Merge Sort cã log2n b­íc trén, trong tõng b­íc trén cã chÐ p n nót tõ danh s¸ ch A[] sanh dstam[] vµ chÐ p n nót tõ danh s¸ ch dstam[] vÒ danh s¸ ch A[] VË y M(n) cã bË c lµ O(nlgn) V. t× m kiÕm: V.1. Kh¸i niÖ m: Cho danh s¸ ch A cã n phÇ n tö. T× m x trong danh s¸ ch A, nÕ u cã th× tr¶ vÒ vÞ trÝ cña phÇ n tö ®ã trong danh s¸ ch, ng­îc l¹ i nÕ u t× m kh«ng thÊ y th× tr¶ vÒ -1. Th«ng th­êng danh s¸ ch A ch­a cã thø tù hoÆ c ®∙ ®­îc s¾ p theo 1 trË t tù nµ o ®ã. V.2. T× m kiÕ m tuÇn tù: - Néi dung: Ta t× m tõ ®Ç u danh s¸ ch cho ®Õ n khi nµ o gÆ p phÇ n tö ®Ç u tiª n cã trÞ b» ng víi x hoÆ c ®∙ t× m hÕ t danh s¸ ch th× dõng l¹ i. Gi¶ i thuË t nµ y ®­îc dïng trong danh s¸ ch ch­a cã thø tù. 177 - Gi¶ i thuË t: int Search(int A[], int n, int x) { int i=0; while (i x) i++; return (i<n ? i : -1) ; } V.3. T× m kiÕ m nhÞ ph©n: chØ dïng ®­îc ®èi víi danh s¸ch ®∙ cã thø tù. Ta gi¶ sö danh s¸ ch cã thø tù t¨ ng dÇ n. - Néi dung: ! B­íc 1: Ph¹ m vi t× m kiÕ m ban ®Ç u lµ toµ n bé danh s¸ ch. ! B­íc 2: LÊ y phÇ n tö chÝ nh gi÷a cña ph¹ m vi t× m kiÕ m (gäi lµ y) so s¸ nh víi x. - NÕ u x=y th× ta ®∙ t× m thÊ y, tr¶ vÒ chØ sè. Gi¶ i thuË t kÕ t thóc - NÕ u x < y th× ph¹ m vi t× m kiÕ m míi lµ c¸ c phÇ n tö n» m phÝ a tr­íc cña y. - NÕ u x > y th× ph¹ m vi t× m kiÕ m míi lµ c¸ c phÇ n tö n» m phÝ a sau cña y. ! B­íc 3: NÕ u cßn tån t¹ i ph¹ m vi t× m kiÕ m th× lÆ p l¹ i b­íc 2, ng­îc l¹ i gi¶ i thuË t kÕ t thóc víi kÕ t qu¶ lµ kh«ng cã x trong d∙ y sè. - Gi¶ i thuË t: int Binary_Search(int A[], int n, int x) { int found=FALSE; // Gi¶ sö ban ®Ç u ta ch­a t× m thÊ y x trong d∙ y // Ph¹ m vi ban ®Ç u t× m kiÕ m lµ tõ k=0 'm=n-1 int k=0; int m=n-1; int j; while (k<=m && !found) { j=(k+m) /2; //chØ sè phÇ n tö gi÷a if (A[j]==x) found=TRUE; else if (x>A[j]) k=j+1; // Ph¹ m vi t× m míi lµ (j+1, m) else m=j-1; // Ph¹ m vi t× m míi lµ (k, j-1) } return (found ? j : -1) ; } 178 V.4. PhÐ p t× m kiÕ m nhÞ ph©n ®Ö qui: - Néi dung: t­¬ng tù nh­ trª n ! B­íc 1: Ph¹ m vi t× m kiÕ m ban ®Ç u lµ toµ n bé danh s¸ ch (k=0'm=n-1). ! B­íc 2: LÊ y phÇ n tö chÝ nh gi÷a cña ph¹ m vi t× m kiÕ m (gäi lµ y) so s¸ nh víi x. - NÕ u x=y th× ta ®∙ t× m thÊ y, tr¶ vÒ chØ sè. Gi¶ i thuË t kÕ t thóc - NÕ u x < y th× ph¹ m vi t× m kiÕ m míi lµ c¸ c phÇ n tö n» m phÝ a tr­íc cña y, nª n ta gäi ®Ö qui víi ph¹ m vi míi lµ (k, j-1) - NÕ u x > y th× ph¹ m vi t× m kiÕ m míi lµ c¸ c phÇ n tö n» m phÝ a sau cña y, nª n ta gäi ®Ö qui víi ph¹ m vi míi lµ (j+1,m ) ! §iÒ u kiÖ n dõng: x=y hoÆ c k > m. - Gi¶ i thuË t: int Binary_Search2(int A[], int k,int m, int x) { int j=(k+m) /2; if (k>m) return -1 ; else if (A[j]==x) return j ; else Binary_Search2(A, (A[j] x ?j-1:m),x); } 179 Bµi tËp : 1. ViÕ t l¹ i hµ m QuickSort trong tr­êng hîp chän nót chèt lµ nót gi÷a cña danh s¸ ch cÇ n s¾ p. 2. ViÕ t gi¶ i thuË t t× m k nót lín nhÊ t trong danh s¸ ch cã n nót, yª u cÇ u gi¶ i thuË t cã dïng cÊ u tróc heap. 3. Cµ i ®Æ t gi¶ i thuË t Seletion Sort trª n danh s¸ ch liª n kÕ t. 4. ViÕ t ch­¬ng tr× nh minh häa c¸ c ph­¬ng ph¸ p s¾ p xÕ p. Ch­¬ng tr× nh cã c¸ c chøc n¨ ng sau: a. NhË p ngÉ u nhiª n n sè vµ o danh s¸ ch víi n kh¸ lín b. Chän ph­¬ng ph¸ p s¾ p xÕ p, cã b¸ o thêi gian thùc hiÖ n qu¸ tr× nh s¾ p xÕ p: Bubble Sort, Insertion Sort, Selection Sort, Quick Sort, Heap Sort, Merge Sort. c. Xem danh s¸ ch d. KÕ t thóc ch­¬ng tr× nh 180 CH¦¥NG VII §å thÞ (Graph) Mét cÊ u tróc d÷ liÖ u ®­îc ¸ p dông rÊ t nhiÒ u trong kü thuË t lË p tr× nh lµ ®å thÞ . CÊ u tróc d÷ liÖ u ®å thÞ ®­îc sö dông trong c¸c bµ i to¸n cña rÊ t nhiÒ u lÜ nh vùc nh­ ®­êng ®i, s¬ ®å m¹ ng m¸ y tÝ nh, s¬ ®å ®­êng xe löa - ®­êng xe ®iÖ n ngÇ m trong thµ nh phè.... Ch­¬ng nµ y sÏ m« t¶ c¸ c c¸ ch tæ chøc vµ cÊ u tróc d÷ liÖ u kh¸ c nhau cho 2 lo¹ i ®å thÞ : ®å thÞ v« h­íng vµ ®å thÞ cã h­íng. Chóng ta sÏ nghiª n cøu 2 c¸ ch cµ i ®Æ t ®å thÞ nh­ ma trË n kÒ vµ danh s¸ ch kÒ , hai ph­¬ng ph¸ p duyÖ t ®å thÞ (theo chiÒ u s© u vµ theo chiÒ u réng). Ngoµ i ra ta sÏ tham kh¶ o mét gi¶ i thuË t t× m ®­êng ®i ng¾ n nhÊ t (Shortest paths algorithm) trª n mét ®å thÞ cã träng sè. I. CÊU TRóC D÷ LIÖU CHO §å THÞ: I.1. §Þ nh nghÜ a ®å thÞ : - Mét ®å thÞ G (Graph) bao gåm mét tË p V (vertices) chøa c¸ c nót cña ®å thÞ vµ mét tË p E chøa c¸ c cÆ p nót (v,w) sao cho gi÷a v vµ w cã mét c¹ nh. v w t z H× nh 6.1 §å thÞ v« h­íng V = {v, w, z, t} E = { (v,w); (v,t); (t,z); (v,z) } - §å thÞ v« h­íng (Undirected graph): lµ ®å thÞ mµ c¸ c cung kh«ng cã chiÒ u nhÊ t ®Þ nh. - §å thÞ h÷u h­íng (Directed graph): lµ ®å thÞ trong ®ã mçi cung cã mét chiÒ u nhÊ t ®Þ nh. v w t z H× nh 6.2 §å thÞ h÷u h­íng 181 V = {v, w, z, t} E = {); ; ; ; } I.2. C¸c kh¸i niÖ m trª n ®å thÞ : Trong bµ i häc, chóng ta sÏ dïng ®å thÞ h× nh 6.3 ®Ó minh häa c¸ c kh¸ i niÖ m trª n ®å thÞ . A B E D C H× nh 6.3 §å thÞ h÷u h­íng minh häa cho c¸c kh¸i niÖ m cña ®å thÞ . - C¹ nh nèi hai ®Ø nh a vµ b trª n ®å thÞ v« h­íng ®­îc ký hiÖ u (a,b) - C¹ nh nèi hai ®Ø nh a vµ b trª n ®å thÞ h÷u h­íng ®­îc ký hiÖ u . - Nót: §å thÞ h× nh 6.3 cã 5 nót lµ A, B, C, D, E - Cung : Mçi cung trª n ®å thÞ ®­îc x¸ c ®Þ nh bëi 2 nót: nót ®Ø nh (nót tr­íc cña cung) vµ nót ngän (nót sau cña cung) + Khuyª n: C¹ nh (hay cung) nèi tõ 1 ® Ø nh ®Õ n chÝ nh ®Ø nh ®ã gäi lµ khuyª n. Khuyª n lµ chu tr× nh cã chiÒ u dµ i lµ 1. - BË c cña nót: sè cung liª n kÕ t víi nót + BË c vµ o: sè nót ngän liª n kÕ t víi nót + BË c ra: sè nót ®Ø nh liª n kÕ t víi nót. BË c cña nót = bË c vµ o + bË c ra - Nót kÒ : Nót y ®­îc gäi lµ nót kÒ víi nót x nÕ u cã 1 cung ®i tõ nót x ®Õ n nót y. - §­êng ®i: ta nãi tõ nót x ®Õ n nót y cã 1 ®­êng ®i víi chiÒ u dµ i lµ k khi ®i tõ nót x ®Õ n nót y ta qua 1 chuçi k-1 nót x ' n1 ' n2 ' ... ' nk-1 ' y víi nót ni lµ nót kÒ víi nót ni-1. VÝ dô: §­êng ®i tõ nót A ®Õ n nót D qua c¸ c nót A, C, D cã chiÒ u dµ i lµ 2. - Chu tr× nh : Ta nãi qua nót x cã 1 chu tr× nh chiÒ u dµ i k nÕ u xuÊ t ph¸ t tõ nót x chóng ta qua k-1 nót trung gian vµ vÒ l¹ i nót x (x ' n1 ' n2 ' ... ' nk-1 ' x) G ={ 182 VÝ dô: Khuyª n A -> A (chiÒ u dµ i chu tr× nh nµ y b» ng 1) Chu tr× nh A -> C -> D -> E -> A cã chiÒ u dµ i b» ng 4 - §å thÞ cã träng sè: lµ ®å thÞ mµ mçi cung cã liª n kÕ t víi 1 träng sè; th«ng th­êng träng sè nµ y sÏ cã mét ý nghÜ a nµ o ®ã ch¼ ng h¹ n nh­ chiÒ u dµ i cña ®o¹ n ®­êng, chi phÝ vË n chuyÓ n trª n mét qu∙ ng ®­êng, thêi gian vË n chuyÓ n... - §å thÞ liª n th«ng: ®å thÞ ®­îc gäi lµ liª n th«ng nÕ u víi mäi cÆ p nót ph© n biÖ t bao giê còng cã 1 ®­êng ®i tõ nót nµ y ®Õ n nót kia. VÝ dô: §å thÞ h× nh 6.3 lµ ®å thÞ liª n th«ng. I.3 Tæ chøc d÷ liÖ u cho ®å thÞ : Mét ®å thÞ G bao gåm mét tË p c¸ c nót v, mçi nót v ∈ V sÏ cã mét tË p Av chøa c¸ c nót w ∈ V sao cho cã mét cung tõ v ' w ∈ E w ®­îc gäi lµ nót kÒ cña v. Chóng ta cã c¸ c ph­¬ng ph¸ p ®Ó cµ i ®Æ t cÊ u tróc d÷ liÖ u cho tË p c¸ c nót cña mét ®å thÞ : ma trË n kÒ vµ danh s¸ ch kÒ . a. Ma trËn kÒ (m¶ng 2 chiÒ u): - Trong tr­êng hîp G lµ ®å thÞ v« h­íng th× ta quy ­íc : G[v][w] = G[w][v] = 1 nÕ u (v,w) ∈ E - Trong tr­êng hîp G lµ ®å thÞ h÷u h­íng th× ta quy ­íc : G[v][w] = 1 nÕ u ∈ E VÝ dô : Ma trË n kÒ cña ®å thÞ h× nh 6.4 cã d¹ ng: 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 1 2 0 3 4 H× nh 6.4 183 - Khai b¸ o : const MAX = 50; // Sè ®Ø nh tèi ®a cña ®å thÞ typedef int Dothi[MAX][MAX] ; Dothi G ; // G lµ ma trË n kÒ biÓ u diÔ n ®å thÞ b. Danh s¸ch kÒ (m¶ng 1 chiÒ u kÕ t hîp víi danh s¸ch liª n kÕ t): Mét ®å thÞ ®­îc xem lµ bao gåm danh s¸ ch c¸ c nót, mçi nót cã mét danh s¸ ch c¸ c nót kÒ t­¬ng øng. VÝ dô : Danh s¸ ch kÒ cña ®å thÞ h× nh 6.4 cã d¹ ng: • • • • • 2 3 43 4 • • • • 0 1 2 3 4 6 7 • 2 • 3• max H× nh 6.5 Danh s¸ch kÒ cña ®å thÞ 6.4 - Khai b¸ o : typedef int BYTE; const MAX = 6; struct node { int dinh_ke; struct node *next; }; typedef struct node *NODEPTR; struct phantu { NODEPTR pF; NODEPTR pL ; }; typedef struct phantu Dothi[MAX]; Dothi G; 184 II. duyÖt ®å thÞ: Trong ®a sè c¸ c bµ i to¸ n trª n ®å thÞ , viÖ c lÇ n l­ît ®i qua tÊ t c¶ c¸ c nót cña mét ®å thÞ lµ rÊ t cÇ n thiÕ t; viÖ c nµ y gäi lµ duyÖ t mét ®å thÞ . Ta cã nhiÒ u ph­¬ng ph¸ p ®Ó duyÖ t mét ®å thÞ : duyÖ t theo chiÒ u s© u vµ duyÖ t theo ®é réng. §Ó minh häa cho c¸ c gi¶ i thuË t duyÖ t ®å thÞ , ta sö dông ®å thÞ h× nh 6.6 sau: 0 1 4 3 2 H× nh 6.6 §å thÞ minh häa cho c¸c gi¶i thuËt duyÖ t II.1. DuyÖ t theo chiÒ u s©u (Depth-First Travelsal) Nguyª n t¾c : Gi¶ sö ta ®Õ n mét nót v cã c¸ c nót kÒ lÇ n l­ît lµ w1, w2,...wk. Sau khi duyÖ t nót v, ta sÏ ®i qua w1 vµ gi÷ l¹ i c¸ c nót w2,...,wk vµ o Stack. TiÕ p tôc duyÖ t nót w1 vµ tÊ t c¶ c¸ c nót kÒ cña w1, råi míi trë l¹ i duyÖ t w2. LÆ p l¹ i cho ®Õ n khi duyÖ t hÕ t nót wk vµ c¸ c nót kÒ cña nã. L­u ý : - Kh«ng duyÖ t mét nót hai lÇ n. - §Ó tr¸ nh tr­êng hîp duyÖ t sãt mét nót k’ trong ®å thÞ , ta ph¶ i t¹ o mét vßng lÆ p ®Ó cã thÓ ®¶ m b¶ o duyÖ t hÕ t c¸ c nót cña ®å thÞ . Gi¶i thuËt: void Depth_traverse(int i0) // nót b¾ t ®Ç u ®Ó tõ ®ã duyÖ t { int C [MAX] ; // de danh dau cac dinh da di qua int Stack[MAX] ; // Stack de chua cac dinh trong khi duyet int sp ; // sp : con tro dau stack int i,x ; for (i=0; i<MAX; C[i++] =0 ); sp=0; // khoi tao Stack Stack[sp]=i0; C[i0]=1 ; // da duyet qua dinh i0 185 while (sp >-1) // Khi Stack khac rong { x=Stack[sp]; sp-- ; // xoa dinh vua tham ra khoi Stack cout << x << " "; // Tham dinh vua lay ra for (i=0; i<MAX; i++) // dua tat ca cac nót ngon chua duyet tu x vao C if (G[x][i] && C[i]==0) { Stack[++sp]=i; C[i]=1; } } } VÝ dô: ¸ p dông gi¶ i thuË t trª n cho ®å thÞ h× nh 6.6 ta sÏ nhË n ®­îc kÕ t qu¶ t­¬ng øng víi c¸ c ®Ø nh b¾ t ®Ç u : §Ø nh b¾t ®Çu Tr× nh tù duyÖ t 0 0 → 4 → 3 → 1 → 2 1 1 → 2 → 3 → 0 → 4 2 2 → 3 → 0 → 4 → 1 3 3 → 0 → 4 → 1 → 2 4 4 → 3 → 0 → 1 → 2 II.2. DuyÖ t theo ®é réng (Breadth First Travelsal) Nguyª n t¾c : Gi¶ sö ta ®Õ n mét nót v cã c¸ c nót kÒ lÇ n l­ît lµ w1, w2,...wk. Sau khi duyÖ t nót v, ta duyÖ t hÕ t c¸ c nót wi cña v, råi míi tiÕ p tôc xem c¸ c nót kÒ cña tõng wi. DuyÖ t c¸ c nót kÒ ch­a ®­îc duyÖ t cña c¸ c nót wi. Cø tiÕ p tôc nh­ vË y cho ®Õ n khi hÕ t c¸ c nót cña ®å thÞ . * Gi¶i thuËt: // Hang doi phuc vu cho cong viec duyet Width_traverse struct node { int diachi ; struct node *next; }; typedef node *Node_queue; 186 struct Queue { Node_queue Front, Rear; } Q; void Insert_queue(Queue &Q, int x) { Node_queue p; p = (Node_queue)malloc(sizeof(struct node)); p->diachi = x; if (Q.Front==NULL) Q.Front=p; else Q.Rear->next=p; Q.Rear=p; p->next=NULL; } int Delete_queue(Queue &Q) { Node_queue p; int x; if(Q.Front==NULL) { cout <<"\nHang doi rong"; getche(); exit(1); } else { p = Q.Front; // nut can xoa la nut dau x = p->diachi; Q.Front = p->next; free(p); return x; } } void Width_traverse(int i0) // dinh bat dau de tu do duyet { BYTE C [MAX] ; // de danh dau cac dinh da di qua int i,x ; 187 cout << "Cac dinh cua do thi theo giai thuat duyet rong \n"; for (i=0 ; i< MAX; C[i++]=0); Q.Front= NULL; // khoi tao hang doi Insert_queue(Q,i0); C[i0]=1 ; // da duyet qua dinh i0 while (Q.Front !=NULL) { x=Delete_queue(Q); // xoa dinh vua tham ra khoi hang doi cout << x << " "; // Tham dinh Q[l] for (i=0; i<MAX; i++) // dua tat ca cac dinh ngon chua duyet tu x vao Q if (G[x][i] && C[i]==0) { Insert_queue(Q,i); C[i]=1; } } } VÝ dô: ¸ p dông gi¶ i thuË t trª n cho ®å thÞ h× nh 6.6 ta sÏ nhË n ®­îc kÕ t qu¶ t­¬ng øng víi c¸ c ®Ø nh b¾ t ®Ç u : §Ø nh b¾t ®Çu Tr× nh tù duyÖ t 0 0 → 1 → 4 → 2 → 3 1 1 → 2 → 0 → 3 → 4 2 2 → 0 → 3 → 1 → 4 3 3 → 0 → 1 → 4 → 2 4 4 → 3 → 0 → 1 → 2 III. bµi to n¸ bao ®ãng truyÒn øng: III.1. Kh¸i niÖ m: Bao ®ãng truyÒ n øng cña mét ®å thÞ G cã n nót lµ mét ma trË n cho chóng ta biÕ t gi÷a 2 nót x vµ y bÊ t kú trª n ®å thÞ cã tån t¹ i mét ®­êng ®i víi chiÒ u dµ i nhá h¬n hay b» ng n hay kh«ng. Ma trË n h× nh 6.7 lµ bao ®ãng truyÒ n øng cña ®å thÞ h× nh 6.4. C¸ c sè 1 trong ma trË n cho ta biÕ t tõ nót x ®Õ n nót y tån t¹ i ®­êng ®i víi chiÒ u dµ i nhá h¬n hay b» ng 5. 188 0 1 2 3 4 0 0 0 1 1 1 1 0 0 1 1 1 2 0 0 0 1 1 3 0 0 0 1 1 4 0 0 0 1 1 H× nh 6.7: Bao ®ãng truyÒ n øng cña ®å thÞ h× nh 6.4 III.2. ThuËt to¸n WarShall : 1- Cho P1 lµ ma trË n kÒ cña ®å thÞ G cho chóng ta biÕ t gi÷a 2 nót x vµ y bÊ t kú trª n ®å thÞ cã tån t¹ i mét ®­êng ®i víi chiÒ u dµ i nhá h¬n hay b» ng 1. 2. TÝ nh P2 = P1 x P1 : cho chóng ta biÕ t gi÷a 2 nót x vµ y bÊ t kú trª n ®å thÞ cã tån t¹ i mét ®­êng ®i víi chiÒ u dµ i nhá h¬n hay b» ng 2. P1 x P1 chÝ nh lµ phÐ p nh© n 2 ma trË n víi phÐ p nh© n lµ and vµ phÐ p céng lµ or. ( )P*PP 1kj1ikn 1k )2( ij ∪= = 3. T­¬ng tù, ta tÝ nh P3, P4, ..., P n. 4. Bao ®ãng truyÒ n øng = P1 ∪ P2 ∪ P3... ∪ P n. VÝ dô: Víi ®å thÞ G h× nh 6.4, th× lÇ n l­ît c¸ c Pi lµ : 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 P1 = 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 P2 = 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 P3 = 0 0 0 1 0 189 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 P4 = 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 P5 = 0 0 0 1 0 Bao ®ãng truyÒ n øng cña ®å thÞ G : 0 1 2 3 4 0 0 0 1 1 1 1 0 0 1 1 1 2 0 0 0 1 1 3 0 0 0 1 1 4 0 0 0 1 1 * Ch­¬ng tr× nh: #include #include const MAX = 4; int G[MAX][MAX]= { {0,0,1,0}, {0,0,1,0}, {0,0,1,1}, {0,1,0,0} } ; void Xuat(int P[][MAX]) { int i,j; for( i=0; i<MAX;i++) { for( j=0; j< MAX; j++) printf ("%4d", P[i][j] ) ; printf ( "\n"); } 190 getch(); printf("\n"); } void WarShall( int G[][MAX]) { int i,j,k, dem; int C[MAX][MAX], P[MAX][MAX]; int BD[MAX][MAX]; // bao ®ãng truyÒ n øng cña ma trË n G for( i=0; i<MAX;i++) // P1 for (j=0;j<MAX; j++) BD[i][j]= P[i][j]=G[i][j]; for ( dem=1; dem<MAX; dem++) { for ( i=0; i<MAX; i++) for (j=0; j< MAX;j++) { C[i][j]=0; for (k=0; k<MAX; k++) C[i][j]= C[i][j] || (P[i][k] && G[k][j]); } for (i=0;i<MAX;i++) for (j=0 ; j<MAX; j++) { P[i][j]=C[i][j]; BD[i][j]=BD[i][j] || P[i][j]; // OR don ma tran P vua tinh vao bao dong } Xuat(P); // Kiem tra tung Pi } Xuat(BD); } void main() { int P[MAX][MAX] ; int i,j ; clrscr(); WarShall(G); getch(); } 191 IV. GI¶I THUËT T× M §­êNG §I NG¾N NHÊT: §èi víi mét ®å thÞ cã träng sè, mçi c¹ nh sÏ cã mét gi¸ trÞ träng sè t­¬ng øng, t× m ®­êng ®i ng¾ n nhÊ t trª n ®å thÞ G tõ mét nót v ®Õ n mét nót w lµ bµ i to¸n t× m ®­êng ®i cã träng l­îng nhá nhÊ t tõ v ®Õ n w. Träng sè cña mét c¹ nh cã thÓ lµ thêi gian ®Ó ®i qua mét c¹ nh, phÝ tæn, kho¶ ng c¸ ch hoÆ c l­u l­îng. 0 4 1 3 2 2 5 2 4 1 6 3 10 6 2 H× nh 6.8 §å thÞ h÷u h­íng cã träng sè * ThuË t to¸ n Dijkstra: T× m c¸ c ®­êng ®i ng¾ n nhÊ t tõ nót v ®Õ n c¸ c nót cßn l¹ i cña ®å thÞ . Input : - §å thÞ G lµ ma trË n kÒ h÷u h­íng cã träng sè víi qui ­íc sau: + NÕ u u kÒ víi v th× ®é dµ i cung > 0 + NÕ u u kh«ng kÒ víi v th× ®é dµ i cung = -1 - Nót v lµ nót ta b¾ t ®Ç u t× m c¸ c ®­êng ®i ng¾ n nhÊ t tõ v ®Õ n tÊ t c¶ c¸ c nót cßn l¹ i trong ®å thÞ . Output: §é dµ i ng¾ n nhÊ t tõ v ®Õ n tÊ t c¶ c¸ c nót cßn l¹ i trong ®å thÞ . * Gi¶ i thuË t: Dïng mét tË p S ®Ó chøa c¸c nót ®∙ x¸c ®Þ nh ®­îc kho¶ ng c¸ch ng¾ n nhÊ t tõ nót v ®Õ n c¸ c nót ®ã. Dïng mét m¶ ng Dist ®Ó chøa gi¸ trÞ c¸ c kho¶ ng c¸ ch ng¾ n nhÊ t nµ y. NÕ u nót u ë trong S th× Dist [u] lµ gi¸ trÞ kho¶ ng c¸ ch ng¾ n nhÊ t tõ v cho ®Õ n u. NÕ u u ch­a cã trong S th× Dist [u] chøa ®é dµ i tõ v ®Õ n mét nót w nµ o ®ã trong S cé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­îng tõ nót v ®Õ n c¸ c nót cßn l¹ i nÕ u cã c¹ nh trùc tiÕ p, vµ b» ng v« cïng (MAXINT) nÕ u kh«ng cã c¹ nh trùc tiÕ p. 192 a 0 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 Minh häa c¸c b­íc ¸ p dông gi¶i thuËt Dijkstra t× m ®­êng ®i ng¾n nhÊt tõ nót 0 cho ®Õ n tÊt c¶ c¸c nót cßn l¹i trong ®å thÞ h× nh 6.8 * Gi¶ i thuË t void Shortest_path(BYTE v, const long G[][MAX]) { /* Cost chua do dai cac cung cua do thi G, voi qui uoc neu G[i][j]=-1 thi Cost[i][j] = MAXINT */ long Cost[MAX][MAX] ; /* Dist[j] : the hien do dai cua duong di ngan nhat tu nut v den nut j trong do thi dinh huong G co MAX nut; G duoc bieu dien boi ma tran ke huu huong co trong so kich thuoc MAX x MAX */ 193 long int Dist [MAX] ; /* S : Tap cac dinh (ke ca v) theo do cac duong di ngan nhat da xac lap */ int S[MAX] ; int w,i,j,u,k ; for (i=0; i<MAX; i++) for (j=0;j<MAX;j++) Cost[i][j]= (G[i][j]==-1? MAXINT : G[i][j]); // Khoi tao S va Dist for (i=0; i< MAX; S[i]=0, Dist[i]=Cost[v][i],i++ ); S[v]=1; Dist[v]=0 ; k=1; //dua v vao S while (k < MAX) // xac dinh n-1 duong di tu dinh v { // chon u sao cho: Dist[u] = min (Dist[j]), S[j]=0 j=0; while (j<MAX && S[j]!=0) j++; // Tim S[j] = 0 dau tien u=j; for (j=u; j<MAX; j++) if (S[j] == 0 && Dist[u] > Dist[j]) u=j; //Dua u vao tap S *) S[u]=1 ; k++; for (w=0; w< MAX; w++) if (S[w] == 0) if (Dist[u]+Cost[u][w] < Dist [w]) Dist[w]= Dist[u]+Cost[u][w]; } for (w=0; w<MAX; w++) if (Dist[w] < MAXINT) cout " <<w <<": " << Dist[w]; else cout " <<w << ": Khong co duong di"; } V. S¾p thø tù Topo: 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ö. 194 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: (1) NÕ u x < y vµ y < z th× x < z (tÝ nh b¾ c cÇ u) (2) NÕ u x < y th× kh«ng cã thÓ cã y < x (tÝ nh ph¶ n xøng) (3) Kh«ng thÓ cã x < x (tÝ nh kh«ng ph¶ n x¹ ) Th«ng th­êng, bµ i to¸ n Topo nh» m ®Ó s¾ p xÕ p c¸ c phÇ n viÖ c trong mét c«ng viÖ c nµ o ®ã cho logic, nghÜ a lµ khi ta thùc hiÖ n ®Õ n phÇ n viÖ c thø i th× ph¶ i ®¶ m b¶ o ®∙ thùc hiÖ n c¸ c phÇ 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Ø m«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. ThuËt to¸n: §Ó ®¬n gi¶ n, ta lÊ y vÝ dô sau ®Ó minh häa: Gi¶ sö khoa c«ng nghÖ th«ng tin cã gi¶ ng d¹ y c¸ c m«n häc sau: ®¹ i sè tuyÕ n tÝ nh (§STT), Tin häc c¬ b¶ n (THCB), LË p tr× nh c¨ n b¶ n (LTCB), Kü thuË t lË p tr× nh (KTLT), CÊ u tróc d÷ liÖ u (CTDL), CÊ u tróc m¸ y tÝ nh (CTMT), C¬ së d÷ liÖ u (CSDL), Qu¶ n trÞ giao t¸ c (QTGT), Ph© n tÝ ch & thiÕ t kÕ hÖ thèng th«ng tin (PTTK), HÖ qu¶ n trÞ c¬ së d÷ liÖ u (HQT). Yª 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× nh c¨ n b¶ n Tin häc c¬ b¶ n 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 195 §STT THCB CTMT CSDL QTGT HQTPTTK LTCB CTDL KTLT 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 cung tõ nót ®ã ®i ra. (ii) LÆ p l¹ i b­íc i cho ®Õ n khi kh«ng cßn nót nµ o trª n ®å thÞ L­u ý : NÕ u trong qu¸ tr× nh chän mµ kh«ng t× m ®­îc 1 nót kh«ng cã cung tíi nã th× cã nghÜ a lµ ®å thÞ cã chu tr× nh. Do ®ã, kh«ng thÓ thùc hiÖ n s¾ p Topo ®­îc. p¸ dông gi¶ i thuË t trª n víi ®å thÞ h× nh 6.10 Nót chän §å thÞ cßn l¹i §STT THCB CTMT CSDL QTGT HQTPTTK LTCB CTDL KTLT THCB CTMT CSDL QTGT HQTPTTK LTCB CTDL KTLT 196 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: 197 Ñ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Þ VÝ dô: 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 198 struct node { 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 199 for (j=0; j<MAX; j++) { G[j].count=0; for (i=0; i< MAX; i++) 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; 200 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; } p=p->next; } } } void main() { clrscr(); Create_graph(); Topo_Sort(G); getch(); } 201 Bµ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 202 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 -