Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Đồ thị - Trường Đại học Công nghiệp Thực phẩm Tp. Hồ Chí Minh
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (199.73 KB, 7 trang )
<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>
<b>Ch</b>
<b>ươ</b>
<b>ng 5: </b>
<b>Đồ</b>
<b> th</b>
<b>ị</b>
<b>1. Các khái ni</b>
<b>ệ</b>
<b>m </b>
<b>1.1. </b>
<b>Đị</b>
<b>nh ngh</b>
<b>ĩ</b>
<b>a </b>
<b>đồ</b>
<b> th</b>
<b>ị</b>
Đồ
th
ị
G(V,E) bao g
ồ
m m
ộ
t t
ậ
p h
ữ
u h
ạ
n V các
đỉ
nh
(hay nút) và m
ộ
t t
ậ
p h
ữ
u h
ạ
n E các c
ặ
p
đỉ
nh mà ta
g
ọ
i là cung ( hay c
ạ
nh).
Ví d
ụ
1: M
ộ
t m
ạ
ng g
ồ
m các máy tính và các kênh
đ
i
ệ
n
tho
ạ
i n
ố
i các máy tính này là m
ộ
t
đồ
th
ị
.
Ví d
ụ
2: M
ộ
t m
ạ
ng g
ồ
m các thành ph
ố
, th
ị
xã và các
đườ
ng b
ộ
n
ố
i các thành ph
ố
, th
ị
xã là m
ộ
t
đồ
th
ị
.
1.2.
Đị
nh ngh
ĩ
a
đồ
th
ị
vô h
ướ
ng
</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>
* N
ế
u (v1, v2) là m
ộ
t cung trong t
ậ
p E(G) thì v1 và v2 g
ọ
i là lân
c
ậ
n c
ủ
a nhau.
Ví d
ụ
trên 1,2 là lân cân, 1,3 là lân c
ậ
n.
* M
ộ
t
đườ
ng
đ
i t
ừ
đỉ
nh u
đế
n
đỉ
nh v trong
đồ
th
ị
là m
ộ
t dãy các
đỉ
nh
u=x0, x1, ..., xn-1, xn=v mà dãy các c
ạ
nh (x0, x1), (x1, x2), ...,
(xn-1, xn) là các cung thu
ộ
c E(G) .
* S
ố
l
ượ
ng cung trên
đườ
ng
đ
i g
ọ
i là
độ
dài c
ủ
a
đườ
ng
đ
i.
Ví d
ụ
đườ
ng
đ
i t
ừ
1
đế
n 4 có
độ
dài là 2.
*
Đườ
ng
đ
i
đơ
n: Là
đườ
ng
đ
i mà m
ọ
i
đỉ
nh trên
đ
ó, tr
ừ
đỉ
nh
đầ
u và
đỉ
nh cu
ố
i
đề
u khác nhau.
* M
ộ
t chu trình là m
ộ
t
đườ
ng
đ
i
đơ
n mà
đỉ
nh
đầ
u và
đỉ
nh cu
ố
i
trùng nhau.
</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3></div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4></div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5></div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6></div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>
<b>3. Phép duyệt đồ thị</b>
* Xét đồ thị vô hướng G(V,E) và một đỉnh v∈V. Ta cần thăm tất cả các
đỉnh của G mà có thể “ với tới” từ đỉnh v ( nghĩa là đồ thị liên thơng).
Có 2 cách duyệt đồ thị:
- Phép tìm kiếm theo chiều sâu ( Depth first search )
- Phép tìm kiếm theo chiều rộng (Breadth first search )
<b>3.1. Phép tìm kiếm theo chiều sâu ( Depth first search )</b>
Xét đồ thị vô hướng. Phép tìm kiếm theo chiều sâu thể hiện như sau:
- Đỉnh xuất phát v được thăm.
- Tiếp theo đó ta thăm đỉnh w là đỉnh chưa được thăm và là lân cận của
v. Phép tìm kiếm theo chiều sâu xuất phát từ w lại được thực hiện.
Trong trường hợp đỉnh u đã được thăm mà mọi đỉnh lân cận của nó đã
được thăm rồi thì ta quay lại đỉnh cuối cùng vừa được thăm ( mà
</div>
<!--links-->
