Cấu trúc dữ liệu đồ thị (Graph)
Cấu trúc dữ liệu đồ thị là gì?
Một đồ thị (đồ thị) là một dạng biểu diễn hình ảnh của một tập các đối tượng, trong đó các cặp đối tượng được kết nối bởi các link. Các đối tượng được nối liền nhau được biểu diễn bởi các điểm được gọi là các đỉnh (vertices), và các link mà kết nối các đỉnh với nhau được gọi là các cạnh (edges).
Nói chung, một đồ thị là một cặp các tập hợp (V, E), trong đó V là tập các đỉnh và E là tập các cạnh mà kết nối các cặp điểm. Bạn theo dõi đồ thị sau:
Trong đồ thị trên:
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Cấu trúc dữ liệu đồ thị (Graph)
Các hình toán học có thể được biểu diễn trong cấu trúc dữ liệu. Chúng ta có thể biểu diễn một hình bởi sử dụng một mảng các đỉnh và một mảng hai chiều của các cạnh. Trước khi tiếp tục, chúng ta tìm hiểu một vài khái niệm quan trọng sau:
Đỉnh (Vertex): Mỗi nút của hình được biểu diễn như là một đỉnh. Trong ví dụ dưới đây, các hình tròn biểu diễn các đỉnh. Do đó, các điểm từ A tới G là các đỉnh. Chúng ta có thể biểu diễn các đỉnh này bởi sử dụng một mảng, trong đó đỉnh A có thể được nhận diện bởi chỉ mục 0, điểm B là chỉ mục 1… như hình dưới.
Cạnh (Edge): Cạnh biểu diễn một đường nối hai đỉnh. Trong hình dưới, các đường nối A và B, B và C, … là các cạnh. Chúng ta có thể sử dụng một mảng hai chiều để biểu diễn các cạnh này. Trong ví dụ dưới, AB có thể được biểu diễn như là 1 tại hàng 0; BC là 1 tại hàng 1, cột 2, …
Kề nhau: Hai đỉnh là kề nhau nếu chúng được kết nối với nhau thông qua một cạnh. Trong hình dưới, B là kề với A; C là kề với B, …
Đường: Đường biểu diễn một dãy các cạnh giữa hai đỉnh. Trong hình dưới, ABCD biểu diễn một đường từ A tới D.
Các thao tác cơ bản trên cấu trúc dữ liệu đồ thị
Following are basic primary operations of a Graph which are following.
Thêm đỉnh: Thêm một đỉnh vào trong đồ thị.
Thêm cạnh: Thêm một cạnh vào giữa hai đỉnh của một đồ thị.
Hiển thị đỉnh: Hiển thị một đỉnh của một đồ thị.
Chương này chỉ mang tính chất giới thiệu Cấu trúc dữ liệu Đồ thị, để tham khảo thêm về cấu trúc dữ liệu này, bạn có thể tham khảo thêm một số tài liệu trên Tutorialspoint hoặc từ bất cứ nguồn nào khác.
Theo Tutorialspoint
Bài trước: Giải thuật sắp xếp nhanh (Quick Sort)
Bài tiếp: Giải thuật tìm kiếm theo chiều sâu
Bạn nên đọc
-
Công thức tính tỉ số thể tích các khối đa diện
-
Công thức tính diện tích hình quạt tròn
-
Cách tính diện tích hình tròn và chu vi hình tròn
-
Công thức tính đường cao trong tam giác thường, cân, đều, vuông
-
Trọng tâm là gì? Công thức tính trọng tâm của tam giác
-
Công thức tính đường chéo hình vuông, đường chéo hình chữ nhật
Theo Nghị định 147/2024/ND-CP, bạn cần xác thực tài khoản trước khi sử dụng tính năng này. Chúng tôi sẽ gửi mã xác thực qua SMS hoặc Zalo tới số điện thoại mà bạn nhập dưới đây:


Cũ vẫn chất
-
Khai báo biến trong SQL Server
Hôm qua -
Pick me là gì? Pick me girl, Pick me boy là gì?
Hôm qua -
Những bài thơ đám cưới, thơ chúc mừng đám cưới cực hay và hài hước
Hôm qua -
Điều kiện BETWEEN trong SQL Server
Hôm qua -
Cách xóa khoảng trắng và lỗi xuống dòng trong Word
Hôm qua 3 -
Mệnh đề GROUP BY trong SQL Server
Hôm qua -
Hướng dẫn tạo một website cho người mới bắt đầu
Hôm qua -
Cách sửa lỗi VCRUNTIME140_1.dll not found, is missing trong Windows
Hôm qua 28 -
3 cách hiển thị mật khẩu *** trên trình duyệt vô cùng đơn giản
Hôm qua -
Kí tự khoảng trống Liên Quân, ký tự khoảng trống Liên Quân
Hôm qua 19