Bài giảng Thiết kế và đánh giá thuật toán: Đồ thị - TS. Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán<br /> Đồ Thị<br /> TS. Lê Nguyên Khôi<br /> Trường Đại Học Công Nghệ - ĐHQGHN<br /> <br /> Nội Dung<br /> Định nghĩa<br />
Biểu diễn<br />
Tìm kiếm<br />
Sắp xếp topo<br />
<br /> <br /> 1<br /> <br /> Định Nghĩa<br /> Đồ thị
= (, ) bao gồm<br />
<br />
<br />
<br /> <br />
<br /> <br /> Tập  các đỉnh<br /> Tập  ⊆  ×  cạnh<br /> Đồ thị vô hướng<br />
Cặp cạnh không có thứ tự <br /> ,  = (, <br /> )<br /> Đồ thị định hướng<br />
Cặp cạnh có thứ tự <br /> ,  ≠ , <br /> <br /> <br /> Cả hai trường hợp,  ∈ (   )<br /> Nếu
liên thông,  ≥  − 1<br /> ⟹ log  =  log <br /> 2<br /> <br /> Biểu Diễn<br />
<br /> <br />
<br /> <br /> Danh sách liền kề<br />
Mảng 1 chiều  danh sách<br />
Mỗi danh sách cho một đỉnh <br /> bao gồm<br />
Các đỉnh  sao cho <br /> ,  ∈ <br /> Ma trận liền kề<br />
Mảng 2 chiều  × <br />
Đỉnh được đánh số 1, 2, … , <br />
Giá trị 1 thể hiện có cạnh ,  ∈ <br /> <br /> 3<br /> <br /> Biểu Diễn – Danh Sách<br />
<br /> <br /> Danh sách liền kề<br />
Mảng 1 chiều  danh sách<br />
Mỗi danh sách cho một đỉnh <br /> bao gồm<br />
Các đỉnh  sao cho <br /> ,  ∈ <br /> <br /> <br /> <br /> <br /> <br /> <br /> 1  2, 3<br /> 2!  "3#<br /> 3!  "#<br /> 4!  "3#<br /> 4<br /> <br />