intTypePromotion=1

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

Chia sẻ: N N | Ngày: | Loại File: PDF | Số trang:22

0
24
lượt xem
2
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Thiết kế và đánh giá thuật toán: Đồ thị" cung cấp cho người học các kiến thức: Định nghĩa, biểu diễn đồ thị, tìm kiếm, sắp xếp topo. Đây là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn này và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu.

Chủ đề:
Lưu

Nội dung Text: 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 />
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2