Cấu trúc dữ liệu và giải thuật - Chương 9,10
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 (213.15 KB, 7 trang )
<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>
CH
ƯƠ
NG IX: Đ TH
Ồ
Ị
<b>1.</b> Đ nh nghĩaị
2. Các khái ni mệ
3. Bi u di n đ th trong máy tínhể ễ ồ ị
4. Các thu t tốn tìm ki m trên đ thậ ế ồ ị
5. Bài tốn tìm đường đi ng n nh tắ ấ
6. Bài toán cây khung
</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>
<i>1. Đ nh nghĩaị</i>
La môt câu truc r i rac G=< V, E>̀ ̣ ́ ́ ờ ̣
V la tâp cac đinh ( vertices) ̀ ̣ ́ ̉
E la tâp cac canh ( Edges) - tâp cac căp ̀ ̣ ́ ̣ ̣ ́ ̣
</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>
<i>1. Đ nh nghĩa</i>
<i>ị</i>
D a vao đăc tinh cua tâp E:ự ̀ ̣ ́ ̉ ̣
G la đ n đô thi nêu gi hai đinh u va v bât ̀ ơ ̀ ̣ ́ ữ ̉ ̀ ́
ki co nhiêu nhât môt canh̀ ́ ̀ ́ ̣ ̣
G la đa đô thi nêu gi hai đinh u va v bât ̀ ̀ ̣ ́ ữ ̉ ̀ ́
</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4>
<i>1. Đ nh nghĩa</i>
<i>ị</i>
G-undirected graph nêu (u,v)=(v,u).́
G-directed graph nêu (u,v)<>(v,u), goi la ́ ̣ ̀
</div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>
<i>1. Đ nh nghĩaị</i>
Hình A Hình B Hình C Hình D
Hinh A: Đ n đô thi, vô h̀ ơ ̀ ̣ ướng
Hinh B: Đ n đô thi, co h̀ ơ ̀ ̣ ́ ướng
Hinh C: Đa đô thi, vô h̀ ̀ ̣ ướng
</div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6>
QHĐ
<b>(iV) Truy vêt ́</b>
-Môi lân khi gan L[i] = L[jmax] +1ta đăt T[i] =jmax ̃ ̀ ́ ̣
đê chi răng day con dai nhât băt đâu t a[i] co ̉ ̉ ̀ ̃ ̀ ́ ́ ̀ ừ ́
phân t th 2 la a[jmax].̀ ử ứ ̀
- Sau khi tinh xong bang ph́ ̉ ương an L va bang ́ ̀ ̉
ghi vêt T, day se băt đâu t T[0] – la phân t đâu ́ ̃ ̃ ́ ̀ ừ ̀ ̀ ử ̀
tiên được chon.̣
</div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>
Vi du
́
̣
I 0 1 2 3 4 5 6 7 8 9 10 11
A[i] <b>- ∞</b> 5 2 3 4 9 10 5 6 7 8 <b>+∞</b>
<b>L[i]</b> <b>9</b> <b>5</b> <b>8</b> <b>7</b> <b>6</b> <b>3</b> <b>2</b> <b>5</b> <b>4</b> <b>3</b> <b>2</b> <b>1</b>
</div>
<!--links-->
