Bài giảng Phân tích thiết kế giải thuật - Chương 8: Giải thuật tìm kiếm trong đồ thị

Dưới đây là bài giảng Phân tích thiết kế giải thuật - Chương 8: Giải thuật tìm kiếm trong đồ thị. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về những cách biểu diễn của một đồ thị, biểu diễn một đồ thị vô hướng, biểu diễn một đồ thị có hướng, tìm kiếm theo chiều rộng.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật - Chương 8: Giải thuật tìm kiếm trong đồ thịGiảithuậttìmkiếmtrongđồthị Biểudiễncácđồthịª HaicáchbiểudiễnmộtđồthịG=(V,E): – Biểudiễndanhsáchkề(adjacencylist) ° mảngAdjgồm V danhsách,1danhsáchchomỗiđỉnhtrongV. u V,Adj[u]chứatấtcảcácđỉnhv(hoặccáccontrỏđến chúng)saocho(u,v) E. – Nhậnxét ° Biểudiễndanhsáchkềcần (V+E)memory.(Đểđơngiản, kýhiệuVvàEthayvì V và E .)7.11.2004 Ch.8:ElementaryGraphAlgorithms 2 Biểudiễncácđồthị (tiếp) – Biểudiễnmatrậnkề(adjacencymatrix) ° Đánhsốđỉnh1,2,..., V ° A =(aij ,matrận |V V aij=1 nếu(i,j) E 0 trongcáctrườnghợpcònlại. – Nhậnxét ° Biểudiễnmatrậnkềcần (V2)memory. ° Đồthịthưa(sparse), E BiểudiễnmộtđồthịvôhướngMộtđồthịvôhướng Biểudiễn Biểudiễn bằngmộtdanhsáchkề bằngmộtmatrậnkề7.11.2004 Ch.8:ElementaryGraphAlgorithms 4 Biểudiễnmộtđồthịcóhướng Biểudiễnbằng BiểudiễnbằngmộtMộtđồthịcóhướng mộtdanhsáchkề matrậnkề7.11.2004 Ch.8:ElementaryGraphAlgorithms 5 Tìmkiếmtheochiềurộng Tìmkiếmtheochiềurộng(breadthfirstsearch,BFS)ª MộtđồthịG=(V,E) – mộtđỉnhnguồns – biểudiễnbằngdanhsáchkềª Mỗiđỉnhu V – color[u]:WHITE,GREY,BLACK – [u]:contrỏchỉđếnđỉnhchamẹ(predecessorhayparent)củau nếucó. – d[u]:khoảngcáchtừsđếnumàgiảithuậttínhđược.ª firstinfirstoutqueueQ – head[Q] – thaotácENQUEUE(Q,v) – thaotácDEQUEUE(Q).7.11.2004 Ch.8:ElementaryGraphAlgorithms 6 Tìmkiếmtheochiềurộng (tiếp) BFS(G,s) 1 foreachvertexu V[G] {s} 2 docolor[u] WHITE 3 d[u] 4 [u] NIL 5 color[s] GRAY 6 d[s] 0 7 [s] NIL7.11.2004 Ch.8:ElementaryGraphAlgorithms 7 Tìmkiếmtheochiềurộng (tiếp) 8 Q {s} 9 whileQ 10 dou head[Q] 11 foreachv Adj[u] 12 doifcolor[v]=WHITE 13 thencolor[v] GRAY 14 d[v] d[u]+1 15 [v] u 16 ENQUEUE(Q,v) 17 DEQUEUE(Q) 18 color[u] BLACK7.11.2004 Ch.8:ElementaryGraphAlgorithms 8 ThaotáccủaBFSlênmộtđồthịvôhướngVídụ r s t u 0 (a) Q s 0 v w x y r s t u 1 0 (b) Q w r 1 1 1 v w x y r s t u 1 0 2 (c) Q r t x 1 2 1 2 2 v w x y7.11.2004 Ch.8:ElementaryGraphAlgorithms 9 ThaotáccủaBFSlênmộtđồthịvôhướngVídụ(tiếp) r s t u 1 0 2 (d) Q t x v 2 1 2 2 2 2 v w x y r s t u 1 0 2 3 (e) Q x v u 2 1 2 2 2 3 v w x y r s t u 1 ...