Duyệt đồ thị

Giới thiệu

Khi giải quyết nhiều bài toán lý thuyết đồ thị, ta luôn phải duyệt qua tất cả các đỉnh của đồ thị đó. Cho nên, cần có thuật toán duyệt toàn bộ các đỉnh của đồ thị này. Gọi chung là thuật toán duyệt đồ thị. Trong đó có thuật toán duyệt theo chiều sâu và duyệt theo chiều rộng.

Thuật toán duyệt theo chiều sâu(Deep-First Search-DFS)

Nội dung thuật toán

Cho G = (V,E) là đồ thị có tập các đỉnh V và tập các cạnh E. v là một đỉnh trong V va u là đỉnh kề của v, sao cho u cũng thuộc V. Khi đó ta dán nhãn cho tất cả các đỉnh của đồ thị là 0. Chọn một đỉnh v thuộc tập V để bắt đầu duyệt. Gán nhãn đỉnh v này la 1-v đã được duyệt. Chọn đỉnh u trong tập V kề với đỉnh v mà nhãn là 0. Duyệt qua đỉnh u và gán nhãn u là 1. Tiếp tục quá trình duyệt đến khi tất cả các đỉnh đồ thị có nhãn là 1.

Ví dụ áp dụng

=(V,E) có V={1,2,3,4,5} được lưu vào bảng như sau:

do thi goc
Đỉnh Các đỉnh kề
1 2,3,4,5
2 1,3,4,5
3 1,2
4 1,2,5
5 1,2,4
Trước tiên, ta gán nhãn tất cả các đỉnh là 0 (chưa duyệt). Khi đỉnh nào được duyệt qua thì ta cập nhật lại nhãn cho đỉnh đó là 1.
  • Các bước duyệt theo chiều sâu:
Chọn một đỉnh từ danh sách các đỉnh của G. Ở đây ta chọn đỉnh 2 làm đỉnh đầu tiên để bắt đầu duyệt.

Thực hiện DFS(2):pro

dothi2
Đỉnh Các đỉnh kề Nhãn
1 2,3,4,5 0
2 1, 3,4,5 1
3 1,2 0
4 1,2,5 0
5 1,2,4 0
Gán nhãn cho đỉnh 2 là 1 khi duyệt qua nó, tìm thấy các đỉnh kề của đỉnh 2 có đỉnh 3 có nhãn là 0(chưa được duyệt).Lặp lại quá trình với đỉnh 3.

Thực hiện DFS(3):

Duyet_dinh3
Đỉnh Các đỉnh kề Nhãn
1 2,3,4,5 0
2 3,4,5 1
3 1,2 1
4 1,2,5 0
5 1,2,4 0
Gán nhãn cho đỉnh 3 là 1 khi duyệt qua nó, tìm thấy các đỉnh kề của đỉnh 3 có đỉnh 1 có nhãn là 0(chưa được duyệt).Lặp lại quá trình với đỉnh 1.

Thực hiện DFS(1):

Duyet_dinh1
Đỉnh Các đỉnh kề Nhãn
1 2,3,4,5 1
2 3,4,5 1
3 1,2 1
4 1,2,5 0
5 1,2,4 0
Gán nhãn cho đỉnh 1 là 1 khi duyệt qua nó, tìm thấy các đỉnh kề của đỉnh 1 có đỉnh 4 có nhãn là 0(chưa được duyệt).Lặp lại quá trình với đỉnh 4.

Thực hiện DFS(4):

Duyet_dinh4
Đỉnh Các đỉnh kề Nhãn
1 2,3,4,5 1
2 3,4,5 1
3 1,2 1
4 1,2,5 1
5 1,2,4 0
Gán nhãn cho đỉnh 4 là 1 khi duyệt qua nó, tìm thấy các đỉnh kề của đỉnh 4 có đỉnh 5 có nhãn là 0(chưa được duyệt).Lặp lại quá trình với đỉnh 5.
Đến đây, tất cả các đỉnh đã duyệt qua nên ta dừng thuật toán. Xuất ra dãy các đỉnh đã duyệt như sau: 2,3,1,4,5.

Mã giả

Void DFS (int v)
{
Gắn nhãn v đã duyệt;
For (u = 1; u <= n; u++)
If(u tồn tại trong danh sách kề V)
If(u có nhãn là 0)
{
Xử lý đỉnh u; //Gắn nhãn 1
DFS (u);
}
}

Xem thêm

  1. Tìm kiếm theo chiều sâu

Tham khảo

  1. Nguyễn Tuấn Anh, Lý thuyết đồ thị và ứng dụng. Nhà xuất bản Giáo dục Việt Nam 2012
  2. Dương Anh Đức, Nhập môn Cấu Trúc Dữ Liệu và Giải Thuật, Đại Học Khoa Học Tự Nhiên

Tham khảo

Liên kết ngoài

Video demo thuật toán DFS

Wikimedia Commons có thêm hình ảnh và phương tiện truyền tải về Duyệt đồ thị.

Read other articles:

إدارة الغذاء والدواء (الولايات المتحدة)

  إدارة الغذاء والدواء (الولايات المتحدة) (بالإنجليزية: Food and Drug Administration)‏  إدارة الغذاء والدواء (الولايات المتحدة)   تفاصيل الوكالة الحكومية البلد الولايات المتحدة  مؤسس هارفي واشنطن ويلي  تأسست 1906[1] المركز الحكومة الفيدرالية للولايات المتحدة الإحداثيات 3...

 

Dulce dari Aragon

Dulcía dari Aragon[1]Permaisuri PortugalDulce dari AragonWangsaWangsa AragonAyahRamón Berenguer IVIbuPetronila dari AragonPasanganSancho I dari PortugalAnakTeresa, Ratu León Sancha dari Portugal Sancho I Infante Afonso (kemudian Afonso II) Pedro I dari Urgell Fernando dari Flandria Infanta Branca, Nyonya Guadalajara Bengjerd, Ratu Denmark Mafalda, Ratu Kastilia Dulce dari Aragon[a][b][4] (atau dari Barcelona) [5](1160–1198) merupakan istri dan Perm...

 

صحراء قره قوم

صحراء قره قوممعلومات عامةالبلد تركمانستان[1]الإمبراطورية الروسيةالاتحاد السوفيتي تقع في التقسيم الإداري ولاية أهالتركمانستان[1] الإحداثيات 39°N 60°E / 39°N 60°E / 39; 60[1] المساحة 400٬000 كيلومتر مربع تعديل - تعديل مصدري - تعديل ويكي بيانات 40°15′08.40″N 58°26′23.10�...

Stiletto

Slender knife For the shoe design, see Stiletto heel. For other uses, see Stiletto (disambiguation). Stiletto A stiletto (plural stilettos[1]) is a specialized dagger with a long slender blade and needle-like point, primarily intended as a thrusting and stabbing weapon.[2][3] The stiletto blade's narrow cross-section and acuminated tip (that is, a tip which tapers to a sharp point) reduce friction upon entry, allowing the blade to penetrate deeply.[2][4]...

 

Happy End of the World

1997 studio album by Pizzicato FiveHappy End of the WorldMatador issueStudio album by Pizzicato FiveReleasedJune 21, 1997 (1997-06-21)GenreShibuya-keiLength62:40LabelReadymadeMatadorProducerYasuharu KonishiYukihiro FukutomiPizzicato Five chronology Great White Wonder: Rare Masters 1990–1996(1996) Happy End of the World(1997) Porno 3003(1997) Pizzicato Five US chronology The Sound of Music by Pizzicato Five(1995) Happy End of the World(1997) Happy End of You(1998) Sing...

 

Maria Sole Ferrieri Caputi

Maria Sole Ferrieri Caputi Ferrieri Caputi nel 2022 Informazioni personali Arbitro di Calcio Sezione Livorno Professione Ricercatrice universitaria Altezza 172 cm Attività nazionale Anni Campionato Ruolo 2015-20202020-20222022- Serie DSerie CSerie A e B ArbitroArbitroArbitro Attività internazionale 2019- UEFA Arbitro Esordio Scozia – Cipro30 agosto 2019 Maria Sole Ferrieri Caputi (Livorno, 20 novembre 1990) è un arbitro di calcio italiano. Indice 1 Biografia 2 Carriera 3 Note 4 Voci cor...

Cagayan

This article is about the province in the Philippines. For other uses, see Cagayan (disambiguation). This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Cagayan – news · newspapers · books · scholar · JSTOR (January 2014) (Learn how and when to remove this message) Province in Cagayan Valley, PhilippinesCagayanP...

 

Ariel Borysiuk

Ariel Borysiuk Nazionalità  Polonia Altezza 178 cm Peso 70 kg Calcio Ruolo Centrocampista Squadra  Hutnik Varsavia CarrieraGiovanili 2004-2007 TOP 54 Biała PodlaskaSquadre di club1 2007-2012 Legia Varsavia90 (4)2012-2014 Kaiserslautern44 (0)[1]2014→  Volga Nižnij Novgorod4 (0)2014-2016 Lechia Danzica54 (2)2016 Legia Varsavia13 (0)2016 QPR11 (0)2017→  Lechia Danzica14 (1)2017 QPR0 (0)2018-2019 Lechia Danzica17 (0)2019→ &#...

 

Telegrafía

Esquema simplificado de una instalación telegráfica. 1 Estación transmisora 2 Estación receptora 3 Manipulador 4 Batería 5 Tierra 6 Línea 7 Electroimán 8 Punzón 9 Bobina de papel 10 Rodillo entintado 11 Rodillos de arrastre 12 Cinta de papel Samuel Morse, inventor del código que lleva su nombre Telegrafía (del griego tēle (τῆλε), lejos y graphein (γραφεῖν), escribir) es la transmisión a larga distancia de mensajes escritos sin el transporte físico de cartas, original...

Njalla

Anonymous domain registrar, hosting and VPN provider NjallaFounded2018; 6 years ago (2018)FounderPeter SundeServicesDomain and Internet HostingWebsitenjal.la Njalla is an anonymous domain name registrar, hosting provider and VPN provider, established by The Pirate Bay founder Peter Sunde.[1] History Peter Sunde started the company in 2017 as a middle man between domain registration and registrants in order to provide anonymity.[2] In 2020, RIAA and MPA flagge...

 

Sloane Stephens

American tennis player (born 1993) Sloane StephensStephens at the 2017 Washington OpenCountry (sports) United StatesResidenceFort Lauderdale, Florida, U.S.[1]Born (1993-03-20) March 20, 1993 (age 31)[2]Plantation, Florida, U.S.Height5 ft 7 in (1.70 m)Turned pro2009[3]PlaysRight-handed (two-handed backhand)CoachKamau Murray, Omar El KheshenPrize moneyUS$18,580,642[4] 26th in all-time rankings Official websitesloanestephens...

 

Urine

Liquid by-product of metabolism in the bodies of many animals, including humans Sample of human urine Urine is a liquid by-product of metabolism in humans and in many other animals. In placental mammals, urine flows from the kidneys through the ureters to the urinary bladder and is released from the bladder through the urethra during urination. In other vertebrates, urine is excreted through the cloaca.[1] Urine contains water-soluble by-products of cellular metabolism that are rich i...

العلاقات الأردنية اليابانية

العلاقات الأردنية اليابانية الأردن اليابان   الأردن   اليابان تعديل مصدري - تعديل   العلاقات الأردنية اليابانية هي العلاقات الثنائية التي تجمع بين الأردن واليابان.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارن...

 

Leslie Hunter

Scottish painter (1877–1931) For the Church of England bishop, see Leslie Hunter (bishop). For other people, see Les Hunter (disambiguation). George Leslie HunterThe Beach, Largo, at Low Tide, date unknown, Aberdeen Art Gallery & MuseumsBorn(1877-08-07)7 August 1877Rothesay, Isle of ButeDied(1931-12-07)7 December 1931Glasgow, ScotlandNationalityScottishKnown forGraphic artist; Artist in paper media & OilsMovementPost-ImpressionismAwardsArtist Member of Glasgow Art ClubPatron(s)...

 

Triphenylchloroethylene

Synthetic form of estrogen TriphenylchloroethyleneClinical dataTrade namesGynosone, OestrogylOther namesTPCE; Triphenylchlorethylene; Chlorotriphenylethylene; Phenylstilbene chlorideDrug classNonsteroidal estrogenIdentifiers IUPAC name (1-chloro-2,2-diphenylethenyl)benzene CAS Number18084-97-4 YPubChem CID87450ChemSpider78884UNIIAV6NM693EGCompTox Dashboard (EPA)DTXSID80171020 Chemical and physical dataFormulaC20H15ClMolar mass290.79 g·mol−13D model (JSmol)Interactive image SMILES...

Leduc No. 1

Crude oil discovery in Alberta, Canada in Alberta, CanadaLeduc No. 1Leduc #1 wellTypecrude oil discovery in Alberta, CanadaLocationAlberta, CanadaNearest cityLeduc CountyEstablished1990Built1946Governing bodyParks CanadaWebsitehttp://www.canadianenergymuseum.ca/ National Historic Site of Canada Leduc No. 1 was a major crude oil discovery made near Leduc, Alberta, Canada, on February 13, 1947. It provided the geological key to Alberta's most prolific conventional oil reserves and resulted in ...

 

Banu Kalb

Former Arabian tribe This article is about the medieval Arab tribe. For the Alawite tribe of modern Syria, sometimes also known as Banu Kalb, see Kalbiyya. For other uses, see KALB. Banu KalbQuda'aNisbaKalbīLocationThe northern Hejaz, Al-Jawf, Wadi Sirhan, the southern Syrian Desert, Palmyra, the Damascus area, Homs, the Golan Heights and the northern Jordan ValleyDescended fromKalb ibn WabaraBranches Abdallah ibn Kinana Janab Haritha ibn Janab Ulaym Ullays Hisn ibn Damdam Asbagh Amir al-Ak...

 

49th Reserve Division (German Empire)

49th Reserve Division (49. Reserve-Division)Active1914-1919CountryGermanyBranchArmyTypeInfantryEngagementsWorld War I: Battle of Łódź (1914), Battle of Warsaw (1915), Battle of Arras (1917), Passchendaele, Battle of Cambrai (1917)Military unit The 49th Reserve Division (49. Reserve-Division) was a unit of the Imperial German Army in World War I. The division was formed in September 1914 and organized over the next month, arriving in the line in mid-October.[1] It was part of the fi...

George Varnell

American hurdler Varnell, circa 1919 George Marshall Varnell (August 10, 1882 – February 4, 1967) was an American track and field athlete, Gonzaga University's first basketball coach, a college football player, coach, and official, who refereed a record-setting eight Rose Bowl games, and sports editor of two major Pacific Northwest newspapers. He competed in the 1904 Summer Olympics, finishing fourth in the 200 meter hurdles event as well as fourth in the 400 meter hurdles competition. Varn...

 

Championnat du monde de hockey sur glace 2017

Allemagne et France 2017 Généralités Sport Hockey sur glace Organisateur(s) Fédération internationale de hockey sur glace Édition 81e Lieu(x) Paris (France) etCologne (Allemagne) Date du 5 mai 2017au 21 mai 2017 Nations 16 (pour le groupe Élite) Participants 16 (division Élite) Matchs joués 64 Affluence 686 391 spectateurs(10 725 par match) Site(s) Lanxess Arena etAccorHotels Arena Site web officiel iihfworlds2017.com (fr + de + en) Hiérarchie Hi�...