TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Đồ thị

Chương này giới thiệu đến người học về đồ thị. Các nội dung chính trong chương này gồm có: Các khái niệm cơ bản, biểu diễn đồ thị, thuật toán duyệt đồ thị và ứng dụng, một số bài toán trên đồ thị. . | 5 5 2011 Nội dung Các khái niệm cơ bản Biểu diễn đồ thị Thuật toán duyệt đồ thị và ứng dụng Một số bài toán trên đồ thị Đồ thị ĐỒ thị - graph mô tả các mối quan hệ Mạng Internet Mạng lưới đường giao thông Sơ đồ cấu trúc điều khiển Mạng xã hội Mạch điện South Mill deadend Buchak Stuart Woodmere Amherst intersect io n Brain s Way 1 Các khái niệm cơ bản Một đồ thị G bao gồm một tập l G các đỉnh nút và một tập E G các cạnh cung là các cặp đỉnh. v a b c d e Ị g h i j k I 12 đỉnh E a b a e b e b fì c i c g c h d h e i g k g g h i i 13 cạnh Các khái niệm cơ bản Đô thị có trọng sô - weighted graph Đồ thị G V E là có trọng số nếu các cạnh hoặc đỉnh là được gán một giá trị số trọng số Đô thị không trọng sô - unweighted graph Các cạnh đỉnh không được gán trọng số hoặc có trọng số giống nhau 5 5 2011 Các khái niệm cơ bản Đô thị vô hướng - undirected graph Đồ thị G V E là vô hướng nếu các cạnh u v là một bộ không có thứ tự Đô thị có hướng - directed graph Đồ thị G V E là có hướng nếu các cạnh u v là một bộ có thứ tự Các khái niệm cơ bản Đơn đồ thị - Simple graph giữa hai đỉnh chỉ tồn tại một cạnh nếu có Không phải đơn đô thị - non- simple graph trên đồ thị tồn tại một số kiểu cạnh đặc biệt Cạnh vòng - self-loop xuất phát và kết thúc tại cùng một đỉnh Đa cạnh - multiedge một cạnh được lặp lại nhiêu hơn một lần 2 Các khái niệm cơ bản Đồ thị thưa - Sparse số cạnh trên đồ thị ít. Thường là tỉ lệ tuyến tính với số đỉnh Đồ thị dày - Dense số cạnh trên đồ thị lớn Các khái niệm cơ bản Đồ thị tường minh - explicit graph các phần của đồ thị được xây dựng tường minh Đồ thị không tường minh - implicit graph các phần của đồ thị không được xây dựng một cách tường minh nhưng sẽ được xây dựng khi chúng ta sử dụng. Implicit graph 5 5 2011 Các khái niệm cơ bản Đồ thị có chu trình - cyclic graph trong đồ thị có tồn tại chu trình Đồ thị không có chu trình - acyclic graph trong đồ thị có tồn tại chu trình Các khái niệm cơ bản Đồ thị có nhãn - labeled graph các đỉnh được gán nhãn để phân biệt với .

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.