Tìmkiếmtrênđồthị(Version0.5)TrầnVĩnhĐứcHUSTNgày16tháng9năm20191/58CuuDuongThanCong.com https://fb.com/tailieudientucntt
Tàiliệuthamkhảo▶S.Dasgupta,C.H.Papadimitriou,andU.V.Vazirani,Algorithms,July18,2016.▶Chúý:Nhiềuhìnhvẽtrongtàiliệuđượclấytùytiệnmàchưaxinphép.2/58CuuDuongThanCong.com https://fb.com/tailieudientucntt
NộidungBiểudiễnđồthịTìmkiếmtheochiềusâutrênđồthịvôhướngTìmkiếmtheochiềusâutrênđồthịcóhướngThànhphầnliênthôngmạnhCuuDuongThanCong.com https://fb.com/tailieudientucntt
Đồthị▶Mộtđồthịxácđịnhbởimộttậpđỉnh(còngọilànút)VvàbởicáccạnhEgiữacáccặpđỉnhđượcchọn.▶Đồthịcóthểvôhướng:cạnhe={u,v}
▶hoặccóhướnge= (u,v).4/58CuuDuongThanCong.com https://fb.com/tailieudientucntt
BiểudiễnđồthịdùngMatrậnkềNếuđồthịcón=|V|đỉnhv1,v2, . . . , vn,thìmatrậnkềlàmộtmảngn×nvớiphầntử(i,j)củanólàaij={1nếucócạnhtừvitớivj0ngượclại.
Vídụv1v2
v3A=
111001010
5/58CuuDuongThanCong.com https://fb.com/tailieudientucntt