Các thuật toán tìm kiếm trên đồ thị

Thuật toán tìm kiếm theo chiều rộng là sự cải biến về thứ tự duyệt đỉnh trên đồ thị của tìm kiếm theo chiềusâu bằng cách thay vì dùng một STACK thì ta lại dùng một hàng đợi QUEUE để kết nạp đỉnhđược thăm. Như vậy, đỉnh được thăm càng sớm sẽ càng sớm trở thành duyệt xong (cơ chếFirst In First Out Vàotrước ra trước).
Nội dung trích xuất từ tài liệu:
Các thuật toán tìm kiếm trên đồ thị Các thuật toán tìm kiếm trên đồ thịThuậttoántìmkiếmtheochiềusâuTưtưởngchínhcủathuậttoánlà:GiảsửchúngtađangxéttrênđồthịG(V,E).Từmộtđỉnhu Vhiệnthờinàođótasẽthămtớiđỉnhkềvcủauvàquátrìnhđượclặplạiđốivớiđỉnhv.ởbướctổngquát,giảsửhiệntạiđangxétđỉnhu0,chúngtasẽcóhaikhảnăngsẽxảyra:Nếunhưtồntạimộtđỉnhv0kềvớiu0màchưađượcthămthìđỉnhv0đósẽtrởthànhđỉnhđã thămvàquátrìnhtìmkiếmlạibắtđầutừđỉnhv0đó.Ngượclại,nếumọiđỉnhkềvớiu0đềuđãthămthìtasẽquaytrởlạiđỉnhmàtrướcđótađến đỉnhu0đểtiếptụcquátrìnhtìmkiếm.Nhưvậy,trongquátrìnhthămđỉnhbằngthuậttoántìmkiếmtheochiềusâu,đỉnhđượcthămcàngmuộncàngsớmđượcduyệtxong(CơchếLastInFirstOutVàosauratrước).Dođó,tacóthểtổchứcquátrìnhnàybằngmộtthủtụcđệquynhưsau:Procedure DFS(u); Begin Visit(u); Daxet[u]:=True; For v Kề(u do if not Daxet[v] then DFS(v); End;Vàthủtụcduyệthệthốngtoànbộđỉnhcủađồthịsẽlà:Procedure Find; Begin Fillchar(Daxet,SizeOf(Daxet),False); For u V do If not Daxet[u] then DFS(u);End;Dễnhậnthấyrằng,mỗilầngọiDFS(u)thìtoànbộcácđỉnhcùngthànhphầnliênthôngvớiusẽđượcviếngthăm.ThủtụcVisit(u)làthaotáctrênđỉnhutrongtừngbàitoánđặtracụthể.ThuậttoántìmkiếmtheochiềurộngThuậttoánnàythựcralàsựcảibiếnvềthứtựduyệtđỉnhtrênđồthịcủatìmkiếmtheochiềusâubằngcáchthayvìdùngmộtSTACKthìtalạidùngmộthàngđợiQUEUEđểkếtnạpđỉnhđượcthăm.Nhưvậy,đỉnhđượcthămcàngsớmsẽcàngsớmtrởthànhduyệtxong(cơchếFirstInFirstOutVàotrướcratrước).Thủtụcđượcmôtảdướiđây:Procedure BFS(u); Begin Queue:=Empty Kết nạp u vào Queue; Daxet[u]:=True; While QueueEmpty do Begin Lấy v từ Queue; Visit(v); For w Kề(v) do If not Daxet[w] then Begin Kết nạp w vào Queue; Daxet[w]:=True; End; End; End;Tacóthủtụctìmkiếmtheochiềurộnglà:Procedure Find; Begin Fillchar(Daxet,SizeOf(Daxet),False); For u V do If not Daxet[u] then BFS(u); End;Tươngtựnhưthuậttoántìmkiếmtheochiềusâu,ởthuậttoánnàymỗilầngọithủtụcBFS(u)thìmọiđỉnhcùngthànhphầnliênthôngvớiusẽđượcthăm.ThủtụcVisit(u)nhưđãnóiởtrên.Đểhiểurõhơnvềthuậttoán,cácbạncóthểxemthêmbàiviếtThuậttoánLoangcủacùngtácgiảởsốbáo2(7)năm2000.Xinchânthànhcảmơn.Từhaithuậttoántrên,rấtnhiềubàitoáncơbảntrênđồthịđượcgiảiquyếtrấtdễdàng.Vìkhuônkhổbàibáo,xintrìnhbầymộtsốbàitoánkinhđiển.Mộtsốvấnđềkhác,sẽtrìnhbàyởmộtbàibáokhác.1.BàitoántìmthànhphầnliênthôngcủađồthịChomộtđồthịG=(V.E).Hãychobiếtsốthànhphầnliênthôngcủađồthịvàmỗithànhphầnliênthônggồmnhữngđỉnhnào.Nhưtađãbiết,cácthủtụcDFS(u)vàBFS(u)chophépviếngthămtấtcảcácđỉnhcócùngthànhphầnliênthôngvớiunênsốthànhphầnliênthôngcủađồthịchínhlàsốlầngọithủtụctrên.TasẽdùngthêmbiếnđếmConnectđểđếmsốthànhphầnliênthông.Vàvònglặpchínhtrongcácthủtụctìmkiếmtheochiềusâuhaychiềurộngchỉcầnsửalạinhưsau:Procedure Find; Begin Fillchar(Daxet,SizeOf(Daxet),False); Connect:=0; For u V do If not Daxet[u] then Begin Inc(Connect); DFS(u); (*BFS(u)*) End; End;ThủtụcVisit(u)sẽlàmcôngviệcđánhsốthànhphầnliênthôngcủađỉnhu:LienThong[u]:=Connect;2.BàitoántìmđườngđigiữahaiđỉnhcủađồthịChođồthịG=(V,E).Vớihaiđỉnhsvàtlàhaiđỉnhnàođócủađồthị.Hãytìmđườngđitừsđếnt.DothủtụcDFS(s)vàBFS(s)sẽthămlầnlượtcácđỉnhliênthôngvớiunênsaukhithựchiệnxongthủtụcthìcóhaikhảnăng:NếuDaxet[t]=Truethìcónghĩa:tồntạimộtđườngđitừđỉnhstớiđỉnht.Ngượclại,thìkhôngcóđườngđinốigiữasvàt.Vấnđềcònlạicủabàitoánlà:Nếutồntạiđườngđinốiđỉnhsvàđỉnhtthìlàmcáchnàođể viếtđượchànhtrình(gồmthứtựcácđỉnh)từsđếnt.VềkỹthuậtlấyđườngđinàycũngđãđượctrìnhbầytrongbàiviếtThuậttoánLoang!.Xinnhắclạicụthểlà:DùngmộtmảngTruocvới:Truoc[v]làđỉnhtrướccủavtrongđườngđi.Khiđó,câulệnhIftrongthủtụcDFS(u)đượcsửalạinhưsau:If not Daxet[v] then Begin DFS(v); Truoc[v]:=u; End;CònvớithủtụcBFStacũngsửalạitronglệnhIfnhưsau:If not Daxet[w] then Begin Kết nạp w vào Queue; Daxet[w]:=True; Truoc[w]:=v; End;Việcviếtđườngđilênmànhình(hoặcrafile)cóthểcó3cách:ViếttrựctiếpdựatrênmảngTruoc:Hiểnnhiênđườngđihiểnthịsẽngượctừđỉnhttrờvềsnhưsau:DùngthêmmộtmảngphụP:cáchnàydùngđểđảođườngđitừmảngTruocđểcóđườngđithuậntừđỉnhsđếnđỉnht.Cáchthứ3:làdùngchươngtrìnhđệquyđểviếtđườngđi.Procedure Print_Way(i:Byte); If is then Begin Print_Way(Truoc[i]); Write(đ,i); End;Lờigọithủtụcđệquynhưsau:Write(s);Print_Way(s); ...