Đồ thị và cây

Cấu trúc dữ liệu và giải thuật

0.0 (0 đánh giá)
Tạo bởi Katsu Cập nhật lần cuối 22:51 25-04-2022 139 lượt xem 0 bình luận
Tác giả/Dịch giả: huulam3011 K9
Học nhanh

Danh sách bài học

Đồ thị và cây

Dẫn nhập

Trong những bài học trước, mình đã giới thiệu cho các bạn khá nhiều các cấu trúc dữ liệu như stack, queue, deque, … Bắt đầu từ bài học này, chúng ta sẽ tiếp cận với một lớp các cấu trúc dữ liệu và thuật toán có liên quan đến đồ thị và cây. Vậy thì chính xác đồ thị là gì, cây là gì? Hãy cùng nhau tìm hiểu trong bài học ngày hôm nay nhé.


Nội dung

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:

  • Tổng quan về đồ thị
  • Tổng quan về cây
  • Tầm quan trọng của đồ thị và cây trong Tin học

Tổng quan về đồ thị

Khái niệm

Theo một cách không chính thức, đồ thị là một tập các đỉnh được liên kết với nhau bởi các cạnh.

Ví dụ như những ngôi nhà được kết nối với nhau bởi các con đường sẽ tạo thành một đồ thị hay các sân bay được kết nối bởi các đường bay cũng sẽ tạo thành một đồ thị.

Ta sẽ có một số các khái niệm trong đồ thị như sau:

  • Đỉnh: Biểu diễn một đối tượng trong đồ thị

  • Cạnh: Là một liên kết giữa hai đỉnh, thường biểu diễn bởi một đoạn thẳng

  • Đường đi: Là một tập các cạnh liên kết hai hay nhiều đỉnh với nhau. Lưu ý: định nghĩa đường đi với từng bài toán có thể hơi khác nhau nên các bạn cần chú ý.

  • Chu trình: Một đường đi được gọi là chu trình khi đỉnh xuất phát và đỉnh kết thúc đường đi là giống nhau

  • Khuyên: Là một cạnh nối một đỉnh với chính nó

  • Cạnh song song: Các cạnh được gọi là song song khi chúng cùng nối hai đỉnh với nhau

  • Liên thông: Một đồ thị được gọi là đồ thị liên thông khi từ một đỉnh luôn tồn tại đường đi đến đỉnh khác


Một số dạng đồ thị

Đồ thị vô hướng

Một đồ thị được gọi là đồ thị vô hướng khi các cạnh của đồ thị không phân biệt chiều di chuyển giữa hai đỉnh trên đồ thị.

Các cạnh trên đồ thị vô hướng giống như các con đường hai chiều có thể tự do đi theo bất cứ chiều nào mong muốn.


Đồ thị có hướng

Một đồ thị được gọi là đồ thị có hướng khi các cạnh của đồ thị quy định chiều di chuyển giữa hai đỉnh của đồ thị. Khi biểu diễn, các cạnh của đồ thị có hướng thường sẽ gắn thêm mũi tên để chỉ hướng của cạnh đó.

Các cạnh trên đồ thị có hướng giống như các con đường một chiều chỉ có thể đi theo một chiều duy nhất.

Các cạnh khi này sẽ được gọi là cạnh có hướng hay cung.


Đơn đồ thị và đa đồ thị

Một đồ thị được gọi là đơn đồ thị có hướng khi không chứa khuyên và cạnh song song.

Đa đồ thị là các đồ thị không phải đơn đồ thị.


Tổng quan về cây

Cây là một đơn đồ thị liên thông không chu trình gồm n đỉnh và n-1 cạnh. Với cây, ta sẽ gọi một đỉnh thuộc cây là một “node”. Mình sẽ dùng song song cả hai cách gọi là đỉnh và node.

Dưới đây là một minh hoạ cho cây có 6 đỉnh và 5 cạnh.

Có thể các bạn không chú ý nhưng thực chất, có rất nhiều mô hình dạng cây trong thực tế.

Ví dụ như cách phân cấp trong một công ty như mô hình dưới đây

Hoặc chính là mô hình của một post trên Facebook

Chi tiết hơn về cây sẽ được mình đề cập đến sau khi chúng ta biết về các thuật toán duyệt cây.


Tầm quan trọng của đồ thị và cây trong Tin học

Các bài toán về cây và đồ thị trong lập trình được coi là những bài toán khó. Nếu các bạn đã từng đọc qua bất cứ một đề thi trong các cuộc thi lập trình nào thì sẽ luôn thấy sự xuất hiện của các bài toán liên quan đến chủ đề này.

Trong thực tế, các bài toán về đồ thị đóng một vai trò quan trọng dù có thể các bạn không thể thực sự nhìn thấy nó. Các bạn đã bao giờ thắc mắc làm sao mà có thể xếp được thời khoá biểu của cả một trường với vài trăm giáo viên và hàng nghìn học sinh mà không bị trùng lặp chưa? Các bạn đã bao giờ thắc mắc làm sao mà Google Maps có thể chỉ ra đường đi giữa hai điểm bạn muốn chưa? Các bạn đã bao giờ thắc mắc các hệ thống quét sinh trác học như nhận diện vân tay, khuôn mặt hoạt động ra sao chưa? Tất cả chúng đều là các bài toán liên quan đến đồ thị đã được giải quyết và còn vô vàn các ứng dụng khác mà mình không thể kể hết ở đây được.

Nói như vậy để các bạn thấy rằng, hiểu về đồ thị và cây là một điều quan trọng trong lập trình, đặc biệt là trong giải quyết các vấn đề phức tạp.


Kết luận

  • Qua bài này chúng ta đã nắm được về Đồ thị và cây
  • Bài sau chúng ta sẽ tìm hiểu về BFS và DFS
  • Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.

Nội dung bài viết

Tác giả/Dịch giả

Mình là Nguyễn Hữu Lâm, một người có niềm đam mê rất lớn đối với lập trình. Hiện tại, mình đang là sinh viên Khoa học máy tính của Đại học Bách Khoa Hà Nội. Mong muốn của mình là có thể chia sẻ những kiến thức mà bản thân có cho mọi người, học hỏi, kết bạn với tất cả những người có cùng đam mê với mình.


K9

Nhà sáng lập Howkteam.com, KQuiz.vn & tác giả các khóa học C#, Auto, Unity3D, Python....

Với mong muốn mang đến kiến thức chất lượng, miễn phí cho mọi người, với tâm huyết phá bỏ rào cản kiến thức từ việc giáo dục thu phí. Tôi đã cùng đội ngũ Kteam đã lập nên trang website này để thế giới phẳng hơn.
Hãy cùng chúng tôi lan tỏa kiến thức đến cộng đồng! 

Khóa học

Cấu trúc dữ liệu và giải thuật

Bạn đã từng đau đầu với các cấu trúc stack, queue,.. hoặc cảm thấy cực kỳ khó khăn với các thuật toán sắp xếp, tìm kiếm được sử dụng trong lập trình. Đừng lo lắng! Trong khoá học này, chúng ta sẽ cùng nhau tìm hiểu một cách đơn giản nhất về cấu trúc dữ liệu và giải thuật, cũng như giúp bạn nắm rõ hơn về các kiến thức này.

Hãy cùng xem cấu trúc dữ liệu và giải thuật có gì đáng sợ không nhé!

Đánh giá

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập
Không có video.