Ứng Dụng Thuật Toán Tìm Kiếm trong Mê Cung | Thực hành tính toán | Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội
Trong trường hợp lý tưởng, khi duyệt qua toàn bộ các đỉnh và cạnh của đồ thị, độ phức tạp thời gian của thuật toán DFS là O(V + E), trong đó V là số lượng đỉnh và E là số lượng cạnh của đồ thị. Tuy nhiên, nếu đồ thị không liên thông, DFS chỉ có thể duyệt qua các đỉnh thuộc thành phần liên thông chứa đỉnh bắt đầu. Vì vậy, khi đó độ phức tạp thời gian sẽ là O(V + E’), với E’ là số cạnh trong thành phần liên thông chứa đỉnh xuất phát. Tài liệu được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem!
Môn: Thực hành tính toán (HUS) 10 tài liệu
Trường: Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Hà Nội 687 tài liệu
Tác giả:
Preview text:
TRƯỜNGĐẠIHỌCKHOAHỌCTỰNHIÊN
CHUYÊNNGHÀNHKHOAHỌCMÁYTÍNH VÀTHÔNGTIN
BÁOCÁOSƠBỘĐỀTÀICUỐI KỲ CẤUTRÚCDỮLIỆUVÀ GIẢI THUẬT ĐỀTÀI:
ỨNG DỤNGCỦATHUẬTTOÁN TÌM
KIẾMĐỂ GIẢIQUYẾTBÀI TOÁN ĐƯỜNG ĐITRONGMÊCUNG Nhóm:16
Sinhviênthựchiện:NguyễnTuấnAnh ĐinhTrườngAn Lớp:K67A3 HàNội, tháng12,năm 2023
LỜINÓIĐẦU .................................................................. 4
NHẬNXÉT CỦAGIẢNGVIÊN ....................................5
PHẦNI:CƠSỞLÝTHUYẾT ........................................6
1.Cácthuật toántìmkiếm .........................................6
1.1ThuậttoántìmkiếmDFS(Tìmkiếmtheo
chiều sâu) ............................................................6
1.1.1 Khái niệm ...........................................6
1.1.2Ýtưởng ...............................................6
1.1.3 Ví dụ ...................................................7
1.1.4KếtluậnvềthuậttoánDFS ..............10
1.2ThuậttoántìmkiếmBFS(Tìmkiếmtheo
chiềurộng) ........................................................ 12
1.2.1 Khái niệm .........................................12
1.2.2Ýtưởng .............................................13
1.2.3Vídụ ................................................. 14
1.2.4KếtluậnvềthuậttoánBFS ..............17
1.3ThuậttoánDijkstra .....................................19
1.3.1 Khái niệm .........................................19
1.3.2Ýtưởng .............................................20
1.3.3Vídụ ................................................. 20
1.3.4KếtluậnvềthuậttoánDijkstra ........25
PHẦN2:PHÂNTÍCHTHIẾTKẾSƠBỘ ................... 26
1.Biểuđồlớp ...........................................................26
2.Phântíchchươngtrình ........................................ 26 DANHMỤCCÁCHÌNH ẢNH
Hình1.VídụDFS .............................................................. 7
Hình2 . Bước 1 ví dụ DFS.....................................................8
Hình3.Bước2ví dụDFS .................................................. 8
Hình4.Bước3ví dụDFS .................................................. 9
Hình5.Bước4ví dụDFS .................................................. 9
Hình6.Bước5ví dụDFS ................................................ 10
Hình7.VídụBFS ............................................................ 14
Hình8.Bước1ví dụBFS .................................................15
Hình9.Bước2ví dụBFS .................................................15
Hình10.Bước3vídụBFS ..............................................16
Hình11.Bước4vídụBFS ..............................................16
Hình12.Bước5vídụBFS ..............................................17 LỜINÓIĐẦU
Chúngemxintrântrọnggiớithiệubáocáo“Ứngdụngthuật
toántìmkiếmtronggiảiquyếtbàitoánđườngđitrongmêcung”.
Báocáonàytậptrungvàoviệckhámphávàứngdụngcácthuật
toántìm kiếmtrongviệc giảiquyết bàitoán tìmđườngđitrong
mêcung,mộtchủđềquantrọngtrong họcphần“Cấutrúcdữ liệuvàthuậttoán”.
Bàitoánđườngđi trongmêcunglàmộtbàitoánthúvị vàcó
ứngdụngrộngtrongnhiềulĩnhvực,từrobotdichuyểntựđộng
đến lập kế hoạch đường đi trong hệ thống định tuyến mạng.
Mụctiêucủabàitoánlà tìmmộtđườngđitừmộtđiểmxuấtphát
đếnmộtđiểmđíchtrongmộtmêcungphứctạp.Để giảiquyết
bàitoánnày,các thuậttoántìmkiếmđượcsửdụngđểtạoracác
chiếnlượcđiềuhướngthôngminhvàtìmra đườngđitốiưu.
Báocáonàynhằmmụcđíchkhámphávàgiớithiệuvềcácthuật
toántìm kiếmphổbiến tronggiảiquyếtbàitoán đườngđitrong
mêcung.Chúngemsẽgiớithiệucácthuậttoánnhưtìmkiếm
theo chiều rộng (BFS), tìm kiếm theo chiều sâu (DFS), thuật
toánA*vàthuậttoánDijkstra.Mỗithuậttoánsẽđượctrìnhbày
chitiết,baogồm nguyênlýhoạtđộngvàưuđiểm, nhượcđiểm củachúng.
Chúngem hyvọngrằngbáocáonàysẽ giúpcácbạn hiểurõhơn
vềứngdụngvàlợiíchcủaviệcápdụngcácthuậttoántìmkiếm
tronggiảiquyếtbàitoánđườngđitrongmêcung.Bạncũngsẽ
tìmthấythôngtinchitiếtvềcácthuậttoántìmkiếmvànhững
ứngdụngcụthểcủachúngtrongthựctế. NHẬNXÉTCỦAGIẢNGVIÊN
….……………………………………………………….….……
………………………………………………….….……………
………………………………………….….……………………
………………………………….….……………………………
………………………….….……………………………………
………………….….……………………………………………
………….….……………………………………………………
….….……………………………………………………….….
……………………………………………………….….………
……………………………………………….….………………
……………………………………….….………………………
……………………………….….………………………………
……………………….….………………………………………
……………….….………………………………………………
……….….……………………………………………………….
….……………………………………………………….….……
………………………………………………….….……………
………………………………………….….……………………
………………………………….….……………………………
………………………….….……………………………………
………………….….……………………………………………
………….….……………………………………………………
………………………….….……………………………………
………………….….……………………………………………
………….….……………………………………………………
………………………….….……………………………………
………………….….……………………………………………
………….….……………………………………………………
………………………….….……………………………………
………………….….……………………………………………
………….….…………………………………………………… PHẦN I:CƠ SỞ LÝTHUYẾT 1.Cácthuậttoántìmkiếm
1.1ThuậttoántìmkiếmDFS(Tìmkiếmtheochiều sâu) 1.1.1Kháiniệm
-Tìmkiếmtheochiềusâu(DFS) làmộtthuậttoánđểduyệtqua
hoặctìmkiếmcấutrúcdữliệudạngcâyhoặcđồthị.Thuật toán
bắtđầutạinútgốc(chọnmột sốnúttùy ýlàmnútgốctrong
trường hợpđồ thị)và kiểmtratừngnhánhcàngxacàngtốt trướckhiquaylui.
-KếtquảcủamộtDFS là mộtcây baotrùm (spanningtree).Cây
khung(spanningtree)là mộtđồ thịkhôngcóvònglặp.Đểthực
hiệnduyệttheoDFS,chúngtacầnsửdụngcấutrúcdữliệungăn
xếpcókíchthướctốiđabằngtổngsốđỉnhtrongbiểuđồ. 1.1.2Ýtưởng
Đểcàiđặt DFS,tacầnthựchiệncác bướcsau:
1. Lấymộtđỉnhbấtkỳtrongđồthìđưavàongănxếp.
2. Lấytopvaluecủangănxếpđểduyệtvàthêmvàovisited list.
3. Tạomộtlist baogồmcác đỉnhliềnkềcủađỉnhđangxét,
4. thêmnhữngđỉnhkhôngcótrongvisitedlistvàongănxếp.
5. Tiếptụclặplạibước2vàbước3đếnkhingănxếprỗng. 1.1.3Vídụ
Hãyxemthuậttoántìmkiếm DFShoạt độngthếnàovới1vídụ.
Chúngtacó1đồthịvôhướng5đỉnh: Visited Stack 0 3 1 2 4 Hình1.VídụDFS
1. Chúngtabắt đầutừđỉnh0,thuậttoánDFS bắtđầubằng
cáchđưanóvàoVisitedvàđưatấtcảcác cạnhliềnkềđỉnh đangxétvàoStack: Visited 0 Stack 1 2 3 0 3 1 2 4 Hình2.Bước1vídụDFS
2. Tiếptheochúngtatruycậpphầntừởđầungănxếp,tứclà1
vàđiđếncácnútliềnkềcủanó.Vì0đãđượctruycậpnên tiếptheo2sẽđượcxét: Visited 0 1 Stack 2 3 0 3 1 2 4 Hình3.Bước2vídụDFS
3. Chúngtađangxéttớiđỉnh2,đỉnh2có1nútliềnkề chưa
đượcxétlà4,vìvậytathêmđỉnhđóvào vịtríđầucủaStack vàduyệtnó: Visited 0 1 2 Stack 4 3 0 3 1 2 4 Hình4.Bước3vídụDFS
4. Vìđỉnh4khôngcòncácđỉnhnàoliềnkềchưaxét, vìvậyta
sẽduyệtnóvàđưavàoStack Visited 0 1 2 4 Stack 3 0 3 1 2 4 Hình5.Bước4vídụDFS
5. Vàcuốicùnglàduyệtđỉnh3trongStack,nó cũngkhôngcó
bấtkỳđỉnhliềnkềnàochưađượcduyệt,vìthếtađãhoàn
thànhtìmkiếmtheochiềusâutrongđồthịvídụ: Visited 0 1 2 4 3 Stack 0 3 1 2 4 Hình6.Bước5vídụDFS
VìStacktrống,vậynênchúngtađãhoànthànhviệctìm
kiếmtheochiềusâu(DFS) củađồthịtrên
1.1.4KếtluậnvềthuậttoánDFS 1. Độphứctạp
Trongtrườnghợptốtnhất,khiduyệtqua tấtcảcácđỉnhvà cạnh
trongđồthị, độphức tạp thờigian củaDFS là O(V+ E),trong
đóVlàsốlượng đỉnh và Elà sốlượngcạnhtrong đồthị.Tuy
nhiên,nếuđồthịkhôngliênthông,thuậttoánDFS chỉduyệtqua
cácđỉnhthuộcthànhphầnliênthôngchứa đỉnhbắtđầu,dođó
độphứctạpthờigiancóthểlàO(V +E')với E'làsốlượngcạnh
trongthànhphầnliênthôngchứađỉnhbắtđầu.
2. ƯuđiểmcủathuậttoánDFS
-Đơngiảnvàdễhiểu:ThuậttoánDFSdễdàngtriểnkhaivà
hiểu,khôngyêucầunhiềukiếnthứcphứctạp.
-Hiệuquảtrongtìmkiếmđườngđi:DFScóthểtìmkiếmđường
đitừmộtđỉnhđến mộtđỉnhkháctrongđồthị.Nếu cómột
đườngđitồntại,DFSsẽtìmrađườngđiđầutiênmànógặp được.
-Sửdụngít bộnhớ:ThuậttoánDFSchỉsửdụng mộtngăn xếp
đểlưutrữcácđỉnhtrongquátrìnhduyệt,dođótiêuthụítbộ
nhớhơnsovớithuậttoánBFS(Breadth-FirstSearch).
3. NhượcđiểmcủathuậttoánDFS
-Khôngtìmkiếmtốiưu:DFSkhôngđảmbảotìmkiếmđường
đingắnnhấttrongđồthị.NếucónhiềuđườngđitừđỉnhAđến
đỉnhB,DFS cóthểtìmramộtđườngđidàihơnsovớiđườngđi ngắnnhất.
-Dễrơivàovònglặpvôhạn:Nếuđồthịcóchutrình,vàkhông
cócơchếđểkiểmtravàtránhviệclặplạicácđỉnh,DFScóthể
rơivàovònglặpvôhạn,khôngbaogiờkếtthúc.
-Phụthuộcvàothứ tựduyệt:KếtquảcủathuậttoánDFScóthể
thayđổidựatrênthứtựduyệtquacácđỉnh.Nếuthứtự duyệt
đượcthayđổi,kếtquảcũngsẽthayđổi.
-Khôngphùhợpchođồthịlớnvàsâu:Nếuđồthịrấtlớnvàcó
độsâulớn,DFScóthểgặpkhókhăntrongviệcduyệtquatoàn
bộđồthịvàtiêutốnnhiềuthờigianvàbộnhớ. 4. Kếtluận
-MặcdùDFScónhữngưuđiểmnhưđơngiản,hiệuquảtrong
tìmkiếmđườngđivàsửdụngítbộnhớ,nhưngnócũngcó
nhượcđiểm.DFSkhôngđảmbảotìmkiếmđườngđingắnnhất,
cóthểrơivàovònglặpvôhạntrongtrườnghợpđồthịcóchu
trình,phụthuộcvàothứtựduyệtvàkhókhănkhiápdụngcho đồthịlớn vàsâu.
-Tuynhiên,thuậttoánDFSvẫncógiátrịvàứngdụngrộngrãi
trongviệcgiảiquyếtcácbàitoánliênquanđếntìmkiếm, đường
đi,cấutrúcdữliệuđồthịvànhiềulĩnhvựckhác.Nócungcấp
mộtcáchtiếpcậnđơngiảnvà linhhoạtđể khámphávàtìmhiểu
vềcác thành phầntrongđồthị.
-Tómlại,DFSlàmộtthuậttoánquantrọngvàhữuíchtrong
lĩnhvựcđồthị,tuy cónhượcđiểmnhấtđịnh,nhưngvẫnđáng
xemxétvàápdụngtrongcácbàitoántươngứng.
1.2ThuậttoántìmkiếmBFS(Tìmkiếmtheochiều rộng) 1.2.1Kháiniệm
-Tìmkiếm theochiềurộng (BFS)là mộtthuậttoánđểduyệtđồ
thịhoặccây.BFSápdụngchocâyvàđồthịgầnnhưgiốngnhau.
Sựkhácbiệtduynhấtlàđồthịcóthểchứacácchutrình,vìvậy
chúngtacóthểduyệtlạicùngmộtnút.Để tránhxửlýlạicùng
mộtnút,chúngtasửdụngmảngbooleanđãtruycập,mảngnày
sẽđánhdấucácđỉnhđãtruycập.BFSsửdụngcấutrúcdữliệu
hàngđợi(queue)để tìmđườngđingắnnhấttrongbiểuđồ.
-ThuậttoánBFSduyệtquacácđỉnhtheocấpđộ,bắtđầutừ
đỉnhgốcvàđisâuvàocácđỉnhkềtrướckhiđisâuvàocácđỉnh
khác.Dođó,BFStìmkiếmtheochiềurộngtrongđồthịvà
thườngđượcsửdụngđểtìmkiếmđườngđingắnnhấtgiữahai
đỉnhtrongđồthị khôngcótrọngsốhoặccótrọngsốbằngnhau trêncáccạnh. 1.2.2Ýtưởng
-TriểnkhaiBFS tiêuchuẩnsẽđặtmỗi đỉnhcủađồthị vàomột
tronghailoại:visited,notvisited.Mụcđích củathuậttoán là
đánhdấu mỗi đỉnhlà đãthămđể tránh cácchu trình.
Cáchthuậttoánhoạt độngnhưsau:
1. Lấymộtđỉnhbấtkỳtrongđồthịthêmvàocuốihàngđợi.
2. Lấyphântửđầutiêncủahàngđợivàthêmnóvàodanhsách đãduyệt.
3. Tạomộtdanhsáchcácđỉnhliềnkềcủađỉnhđangxét.Thêm
nhữngđỉnhkhôngcótrongdanhsáchđãduyệt vàocuốihàng đợi.
4. Tiếptụclặplạibước2và3chođếnkhihàngđợitrống.
Lưuý:Đồthịcóthểchứahaithànhphầnkhôngliênkếtkhác
nhau,vìvậyđểđảmbảorằngmọiđỉnhđềuđãđược thăm,
chúngtacũngcóthểchạythuậttoánBFStrênmọiđỉnh. 1.2.3Vídụ
Hãyxemthuậttoán tìmkiếm BFShoạtđộngthế nàovới1vídụ.
Chúngtacó1đồthịvôhướng5đỉnh: Visited Queue 0 3 1 2 4 Hình7.VídụBFS
1. Chúngtabắt đầutừđỉnh0,thuậttoánBFSbắtđầubằngcách
đặtnóvàoVisited vàđặt tấtcảcác đỉnhliềnkềcủanóvào Queue: Visited 0 Queue 1 2 3 0 3 1 2 4 Hình8.Bước1vídụBFS
2. Tiếptheo,chúngtatruycậpvàophầntửđầucủahàng đợi
là1vàđiđến cácnút liềnkềcủa nó,vì0đã đượctruy cập nêntathăm2: Visited 0 1 Queue 2 3 0 3 1 2 4 Hình9.Bước2vídụBFS
3. Lầnnày,đỉnh2sẽđượcduyệtvàoVisited,đỉnh2có đỉnh
liềnkềchưađượcthămlà4, vìvậychúngtathêmđỉnh đó vàocuốiQueue: Visited 0 1 2 Queue 3 4 0 3 1 2 4 Hình10.Bước3 vídụBFS
4. Lầnnàytasẽtiếptụcduyệtđếnđỉnh3ởQueuevàcho vào
Visited,vìđỉnh3khôngcònđỉnhliềnkềnàochưaduyệtnên Queuesẽgiữnguyên: Visited 0 1 2 3 Queue 4 0 3 1 2 4 Hình11.Bước4 vídụBFS
5. Cuốicùngchỉcònđỉnh4chưađượcduyệttrongQueue,
đỉnhliềnkềduynhấtcủanólà2đãđược truycậpnên Queuevẫngiữnguyên: Visited 0 1 2 3 4 Queue 0 3 1 2 4 Hình12.Bước5 vídụBFS
VìQueue trống,vậynênchúng tađãhoànthành việctìm
kiếmtheochiềurộng(BFS) củađồthị trên
1.2.4KếtluậnvềthuậttoánBFS 1.Độ phứctạp:
LàO(V+E),trongđóVlàsốlượngđỉnhvàElàsốlượngcạnh
trongđồthị.Thuậttoánduyệtquatấtcảcácđỉnhvàcạnhmột
lần,dođóđộphứctạplàtuyếntínhtheotổngsốđỉnhvàcạnh.
2.ƯuđiểmcủathuậttoánBFS:
-Tìmkiếmtheochiềurộng(BFS)đảmbảotìmkiếmtừđỉnhgốc
đếncácđỉnhxanhấttrướckhitìmđếncácđỉnhgầnhơn.Điều
nàyđảmbảothuậttoántìmkiếmBFStìmkiếmtheocấpđộvà
tìmrađườngđingắnnhấttừđỉnhgốcđếncácđỉnhkhác.
-BFS đượcsửdụngrộngrãitrong các bàitoán tìm kiếmđường
đingắn nhất,kiểmtra tínhliênthôngcủađồthị,tìm kiếm các
thànhphầnliênthông,tìmkiếmtrongcáccây, vànhiềubàitoán khác.
3.Nhược điểmcủathuậttoánBFS:
-Thuậttoán BFSsử dụng mộthàngđợi đểlưu trữcác đỉnhchờ
duyệt.Điềunàycóthểdẫnđếnsử dụngkhônggianlớnnếuđồ
thịcósốlượngđỉnhlớn.
-Trongtrườnghợpđồthịcóchutrình,nếukhôngcócơchếđể
xácđịnhđỉnhđãđược duyệt quahaychưa,thuậttoáncó thểrơi
vàovònglặpvôhạn.Đểkhắcphụcvấnđềnày,cầnsửdụngmột
mảngvisitedđểđánhdấucác đỉnhđãđượcduyệtqua. 4.Kết luận:
-BFSđảmbảotìmkiếmtheocấpđộvàtìmrađườngđingắn
nhấttừđỉnhgốc đếncácđỉnhkháctrongđồthị.Điềunàylàm
choBFShữuíchtrongviệctìmkiếmđườngđingắnnhấthoặc
kiểmtratínhliênthôngcủađồthị.
-Tuynhiên,BFScũngcónhược điểm.Thuậttoánsửdụng
khônggianlớnđểlưu trữhàngđợivà mảngvisitedđểđánhdấu
cácđỉnhđãđượcduyệtqua.Điềunàycóthểgâyrasựlãngphí
khônggiankhiđồthịcósốlượngđỉnhlớn.
-Tómlại,BFSlàmộtthuậttoánquantrọngvàhữuíchtrong
việctìmkiếmđườngđingắnnhấtvàkiểmtratínhliênthông
củađồthị.Mặcdùnócónhượcđiểmnhưsửdụngkhônggian
lớnvàcóthểrơivàovònglặpvôhạn,nhưngvớiưuđiểmcủa
mình,BFSvẫnlàmộtcôngcụmạnhmẽtrongviệcgiảiquyết
cácbàitoánliênquanđếnđồthị. 1.3ThuậttoánDijkstra 1.3.1Kháiniệm
-TheoWikipedia,thuậttoánDijkstra,mangtêncủanhàkhoa
họcmáytínhngườiHàLanEdsgerDijkstravàonăm1956vàấn
bảnnăm1959,làmộtthuậttoángiảiquyếtbàitoánđườngđi
ngắnnhấtnguồnđơntrongmột đồthịcóhướngkhôngcócạnh mangtrọngsốâm.
- Trọng sốkhôngâm làcáccạnhmangtínhtổngthểhơnlà
khoảngcáchhìnhhọcgiữa2định,vìvậythuậttoánsẽcótính chínhxáccaohơn.
-Vídụ,đểbiểudiễnđườngđingắnnhấttừthànhphốAđến
thànhphố B,chúngta dùng cácđỉnhcủa đồthị đểthịphạm các
thànhphốvàcác cạnhđểbiểudiễncác đườngnốigiữachúng.
Trọngsốcáccạnh sẽđượcxemnhư độdàicủacácconđường,
vìvậymà chúngkhôngâm,nhờ đóthuậttoánsẽchỉracon đườngngắnnhất.
-Thuậttoán thường đượcsửdụngtrongđịnhtuyếnvới một
chương trìnhcon trong cácthuậttoánđồthịhay trong công
nghệHệthốngđịnhvị toàncầu (GPS). 1.3.2Ýtưởng
Ýtưởngcơbảncủathuậttoánnhưsau:
Bước1:Từ đỉnhgốc,khởitạokhoảngcáchtới chínhnó là00,
khởitạokhoảngcáchnhỏnhấtbanđầutớicácđỉnhkháclà+∞.
Tađượcdanhsáchcáckhoảngcáchtớicácđỉnh.
Bước2:Chọnđỉnhacókhoảngcáchnhỏnhấttrongdanhsách
nàyvàghinhận.Cáclầnsausẽkhôngxéttớiđỉnhnàynữa.
Bước3:Lầnlượtxétcácđỉnhkềbcủađỉnha. Nếu khoảngcách
từđỉnhgốctới đỉnhbnhỏhơnkhoảngcáchhiệntạiđangđược
ghinhậnthìcậpnhậtgiátrịvà đỉnhkềavàokhoảngcáchhiện tạicủab.
Bước4:Saukhixéttấtcảđỉnhkềbcủađỉnh a.Lúcnàytađược
danhsáchkhoảngcáchtớicácđiểmđãđượccậpnhật.Quay
lạiBước2vớidanhsáchnày.Thuậttoánkết thúckhichọnđược
khoảngcách nhỏ nhấttừtất cảcácđiểm. 1.3.3Vídụ
Đểdễdànghiểuýtưởngcủathuậttoán.Chúngtacùngxemví
dụvớiđồ thịvôhướngG.ThuậttoánDijkstrasẽtìmkhoảng
cáchtừđỉnhgốc0 tớitất cảcácđỉnhcònlạitrongđồthị G:
1. Đầutiên,khởitạokhoảngcáchnhỏnhấtbanđầutớicácđỉnh
kháclà +∞vàkhoảngcáchtớiđỉnh gốclà0.Tađượcdanh
sáchcáckhoảngcách tớicác đỉnh: 0 1 2 3 4 5 0 (∞,-) (∞,-) (∞,-) (∞,-) (∞,-)