tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Đồ thị - Phan Mạnh Hiển (2020)

Bài giảng "Cấu trúc dữ liệu và giải thuật: Đồ thị" cung cấp cho người học các kiến thức: Đồ thị và biểu diễn đồ thị, duyệt đồ thị, sắp xếp topo, tìm đường đi ngắn nhất. | Bài giảng Cấu trúc dữ liệu và giải thuật Đồ thị - Phan Mạnh Hiển 2020 Đồ thị Graphs Nguyễn Mạnh Hiển hiennm@ Nội dung Đồ thị và biểu diễn đồ thị Duyệt đồ thị Sắp xếp topo Tìm đường đi ngắn nhất Đồ thị và biểu diễn đồ thị Đồ thị v1 v2 v3 Đồ thị G V E bao gồm một tập đỉnh V và một tập cạnh E Mỗi cạnh là một cặp v w v4 v5 v6 trong đó v w V Đồ thị không có hướng v7 Các cạnh không có thứ tự v8 Cạnh v w giống như cạnh w v Đồ thị không có hướng được vẽ bằng các nút cho các đỉnh và các đoạn thẳng cho các cạnh Đồ thị có hướng v1 v2 v3 Trong đồ thị có hướng E là một tập các cặp có thứ tự nhưng không nhất thiết là v4 v5 v6 tập đối xứng tức là nếu cạnh v w có mặt thì cạnh w v v7 có thể vắng mặt v8 Đồ thị có hướng được vẽ bằng các nút cho các đỉnh và các mũi tên cho các cạnh Đường đi và trọng số Đường đi là một dãy đỉnh w1 w2 v2 v3 v1 wn trong đó có một cạnh giữa hai -2 3 5 2 đỉnh liên tiếp wi và wi 1 Chiều dài của đường đi có n đỉnh v4 v5 v6 bằng n 1 số cạnh -1 Đường đi là đơn giản nếu tất cả các v7 1 4 đỉnh trên đường đi khác nhau ngoại trừ đỉnh đầu và đỉnh cuối có thể trùng v8 nhau Các cạnh có thể có trọng số hay chi phí kèm theo Chi phí của đường đi bằng tổng trọng số của các cạnh trên đường đi đó Chu trình v2 v3 v1 v2 v3 v1 v4 v4 v5 v6 v5 v6 v7 v7 v8 v8 Chu trình là đường đi w1 w2 wn w1 trong đó đỉnh đầu và đỉnh cuối trùng nhau Chu trình đơn giản nếu đường đi đó đơn giản Trong hình vẽ bên trên v2 v8 v6 v3 v5 v2 là một chu trình đơn giản trong đồ thị không có hướng nhưng không phải như vậy trong đồ thị có hướng Đồ thị liên thông v1 v2 v3 Đồ thị không có hướng là liên thông nếu tồn tại đường đi giữa v4 v5 v6 mọi cặp đỉnh trong đồ thị đó Đồ thị có hướng thỏa mãn điều v7 liên thông kiện trên được gọi là liên thông v8 yếu mạnh Nếu một đồ thị có hướng không v1 v2 v3 liên thông mạnh nhưng đồ thị không có hướng tương ứng liên v4 v5 v6 thông thì được gọi là liên thông yếu v7 liên thông v8 mạnh Biểu diễn đồ thị Đánh số các đỉnh trong đồ thị từ 0 đến n-1 Có thể dùng mảng