Bài giảng Cấu trúc dữ liệu - Chương 6: Đồ thị

Nhằm giúp các bạn có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu về Công nghệ thông tin, mời các bạn cùng tham khảo nội dung "Bài giảng Cấu trúc dữ liệu - Chương 6: Đồ thị" dưới đây. Nội dung bài giảng cung cấp cho các bạn những kiến thức về đồ thị, khái niệm về đồ thị, biểu diễn đồ thị, phép duyệt đồ thị và tìm đường đi ngắn nhất. Hy vọng đây là tài liệu tham khảo hữu ích cho các bạn.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu - Chương 6: Đồ thịCHƯƠNG6ĐỒ THỊ 1 Chương6:Đồthị6.1Địnhnghĩavàcáckháiniệm6.2Biểudiễnđồthị6.3Phépduyệtđồthị6.4Tìmđườngđingắnnhất 26.1ĐịnhnghĩavàkháiniệmĐồthịlàmộtcấutrúcrờirạcgồmcácđỉnhvà cáccạnh(vôhướnghoặccóhướng)nốicác đỉnhđó.Nhiềubàitoánthuộcnhữnglĩnhvựcrấtkhác nhaucóthểgiảiđượcbằngmôhìnhđồthị: biểudiễnsựcạnhtranhcácloàitrongmột môitrườngsinhthái,haimáytínhcóđược nốivớinhaubằngmộtđườngtruyềnthông haykhông.tìmđườngđingắnnhấtgiữahai thànhphố,lậplịchthi,phânchiakênhcho cácđàitruyềnhình… 3 6.1ĐịnhnghĩavàkháiniệmKhimôhìnhhoábằngđồthị:đỉnhbiểuthị cácđốitượngđượcxemxét(người,tổ chức,địadanh,...),cạnhđồthịlànhững đoạnthẳng(hoặccong)haynhữngmũitên nốimộtsốđiểmvớinhau,tượngtrưng chomộtquanhệnàođógiữacácđối tượng.Cácloạiđồthị:MộtđơnđồthịG=(V,E)gồmmộttập khácrỗngVmàcácphầntửcủanógọilà cácđỉnhvàmộttậpElàcáccạnhgồmcác cặpkhôngcóthứtựcủacácđỉnhphân biệt. 4 6.1ĐịnhnghĩavàkháiniệmMộtđơnđồthịcóhướngG=(V,E)gồm mộttậpkhácrỗngVmàcácphầntửcủa nógọilàcácđỉnhvàmộttậpEcáccặpcó thứtựgồm2phầntửkhácnhaucủaV gọilàcáccung.MộtđađồthịG=(V,E)giốngnhưđơnđồ thị,cóthểcócạnhbội(cónhiềuhơnhai cạnhtươngứngvớimộtcặpđỉnh)và khuyên(cạnhnốiđỉnhvớichínhnó). 56.1Địnhnghĩavàkháiniệmv1 v2 v3v4 v5 v6 6 6.1ĐịnhnghĩavàkháiniệmCácthuậtngữvềđồthị:Haiđỉnhuvàvtrongđồthị(vôhướng)G=(V,E)được gọilàliềnkềnếu(u,v) E.Nếue=(u,v)thìegọilà cạnhliênthuộcvớicácđỉnhuvàv.Cạnhecũngđược gọilàcạnhnốicácđỉnhuvàv.Cácđỉnhuvàvgọilà cácđiểmđầumútcủacạnhe.BậccủađỉnhvtrongđồthịG=(V,E),kýhiệudeg(v),là sốcáccạnhliênthuộcvớinó.Khuyêntạimộtđỉnh đượctínhhailầnchobậccủanó.Đỉnhvgọilàđỉnhtreonếudeg(v)=1vàgọilàđỉnhcô lậpnếudeg(v)=0 76.1Địnhnghĩavàkháiniệmv1 v2 v3 v4v5 v6 v7 8 6.1ĐịnhnghĩavàkháiniệmBậcvào(t.ư.bậcra)củađỉnhvtrongđồthịcóhướng G,kýhiệudegt(v)(t.ư.dego(v)),làsốcáccungcóđỉnh cuối(đỉnhđầu)làv.Đỉnhcóbậcvàovàbậcracùngbằng0gọilàđỉnhcô lập.Đỉnhcóbậcvàobằng1vàbậcrabằng0gọilà đỉnhtreo,cungcóđỉnhcuốilàđỉnhtreogọilàcung treoChoG=(V,E)làmộtđồthịcóhướng.Khiđó deg t (v) deg o (v) | E | v V v V 9 6.2Biểudiễnđồthị621.Matrậnkề:Chođồthịvôhướng G=(V,E),v1,v2,...,vnlàcácđỉnhvàe1,e2,...,emlà cáccạnhcủaG.MatrậnkềcủaGlàmatrận A {( aij ) : i, j 1,2,..., n }aijbằng1nếucạnh(i,j) Evàbằng0nếungược lại.Rõràngmatrậnkềcủađồthịvôhướnglà đốixứng.Ngoàira,aijcóthểgánmộtsốnàođógọilàtrọng số.Lúcđó,tacómatrậntrọngsố.Nhượcđiểmlàluônphảidùngn2đơnvịbộnhớđể lưutrữmatrậnkề. 10 6.2Biểudiễnđồthị e6 v1 v2 v3 e3 e4 e1 e5 e20 0 0 1 1 v4 v50 0 1 1 10 1 0 0 11 1 0 0 01 1 0 1 0 Vídụ:Matrậnkềcủađồthị 11 6.2Biểudiễnđồthị622.Danhsáchkề:Mỗiđỉnhvcủađồthịcó danhsáchlưutrữcácđỉnhkềvớinó,kýhiệu Ke(v): Ke(v)={u V:(v,u) E}Ngườitacóthểdùngmảnghoặcdanhsáchliên kếtchoKe(v).Chúngtaphảidùngm+nđơnvị bộnhớđểlưutrữdanhsáchk e ề. 6 v1 v2 v3 e3 e4 e1 e5 e2 v4 v5 12 6.3DuyệtđồthịTìmkiếmtheochiềusâu:voidmain(){ forv Vdochuaxet[v]:=true;forv ...