Các loại biểu đồ trong cấu trúc dữ liệu kèm ví dụ

Đồ thị là một cấu trúc dữ liệu phi tuyến tính bao gồm các đỉnh và các cạnh. Các đỉnh chứa thông tin hoặc dữ liệu và các cạnh hoạt động như một liên kết giữa các cặp đỉnh.

Đồ thị có thể có nhiều loại, tùy thuộc vào vị trí của các nút và cạnh. Dưới đây là một số loại biểu đồ quan trọng:

Đồ thị có hướng

Các cạnh của Đồ thị có hướng chứa các mũi tên chỉ hướng. Mũi tên xác định nơi cạnh được chỉ tới hoặc kết thúc.

Đây là một ví dụ về Đồ thị có hướng.

• Chúng ta có thể đi từ Nút A đến D.
• Tuy nhiên, chúng ta không thể đi từ nút D đến nút A vì các điểm cạnh từ A đến D.
• Vì Đồ thị không có trọng số nên việc di chuyển từ đỉnh A đến D sẽ có chi phí tương đương với việc di chuyển từ D đến F.

Đồ thị vô hướng

Đồ thị vô hướng chứa các cạnh không có con trỏ. Điều đó có nghĩa là chúng ta có thể di chuyển ngược lại giữa hai đỉnh.

Đây là một ví dụ đơn giản về Đồ thị vô hướng.

Trong biểu đồ trên,

• Chúng ta có thể di chuyển từ A đến B
• Chúng ta cũng có thể di chuyển từ B đến A
• Các cạnh không chứa hướng.

Đó là một ví dụ về đồ thị vô hướng có số đỉnh và cạnh hữu hạn không có trọng số.

Biểu đồ có trọng số

Đồ thị chứa trọng số hoặc chi phí trên các cạnh được gọi là Đồ thị có trọng số. Giá trị bằng số thường biểu thị chi phí di chuyển từ đỉnh này sang đỉnh khác. Cả đồ thị có hướng và đồ thị vô hướng đều có thể có trọng số trên các cạnh của chúng.

Đây là ví dụ về biểu đồ có trọng số (Có hướng).

• A đến B, có một cạnh và trọng số là 5, nghĩa là di chuyển từ A đến B chúng ta sẽ tốn 5.
• A điểm đến B, nhưng trong đồ thị này, B không có cạnh trực tiếp trên A. Vì vậy, chúng ta không thể đi từ B đến A.
• Tuy nhiên, nếu chúng ta muốn di chuyển từ A đến F thì có nhiều đường dẫn. Các đường dẫn là ADF, ABF. ADF sẽ có giá (10+11) hoặc 21.
• Ở đây, đường dẫn ABF sẽ có giá trị (5+15) hoặc 20. Ở đây chúng ta cộng trọng số của mỗi cạnh trong đường dẫn.

Dưới đây là ví dụ về Đồ thị vô hướng có trọng số:

Ở đây, cạnh có trọng lượng nhưng không có hướng. Vì vậy, có nghĩa là đi từ đỉnh A đến D sẽ tốn 10 và ngược lại.

Đồ thị hai chiều

Đồ thị hai chiều và đồ thị vô hướng có một đặc tính chung. Đó là

• Nói chung, đồ thị vô hướng có thể có một cạnh giữa hai đỉnh.

Ví dụ:

• Ở đây, di chuyển từ A đến D hoặc D sang A sẽ tốn 10.
• Trong đồ thị hai chiều, chúng ta có thể có hai cạnh giữa hai đỉnh.

Dưới đây là một ví dụ:

Đi từ A đến D sẽ tốn 17, nhưng đi từ D đến A sẽ tốn 12. Vì vậy, chúng ta không thể gán hai trọng số khác nhau nếu đó là đồ thị vô hướng.

Đồ thị vô hạn

Biểu đồ sẽ chứa vô số cạnh và nút. Nếu một đồ thị là vô hạn và nó cũng là một đồ thị liên thông thì nó cũng sẽ chứa vô số cạnh. Ở đây, các cạnh mở rộng có nghĩa là nhiều cạnh hơn có thể được kết nối với các nút này thông qua các cạnh.

Đây là một ví dụ về Đồ thị vô hạn:

Đồ thị rỗng

Đồ thị Null chỉ chứa các nút hoặc đỉnh nhưng không có cạnh. Nếu cho một Đồ thị G = (V, E), trong đó V là đỉnh và E là cạnh, nó sẽ rỗng nếu số cạnh E bằng 0.

Đây là một ví dụ về Đồ thị Null:

Đồ thị tầm thường

Cấu trúc dữ liệu đồ thị được coi là tầm thường nếu chỉ có một đỉnh hoặc nút không có cạnh.

Đây là một ví dụ về đồ thị tầm thường:

Đa đồ thị

Một đồ thị được gọi là đồ thị đa đồ thị khi có nhiều cạnh giữa hai đỉnh hoặc đỉnh có một vòng lặp. Thuật ngữ “Vòng lặp” trong Cấu trúc dữ liệu đồ thị có nghĩa là một cạnh trỏ đến cùng một nút hoặc đỉnh. Multigraph có thể được định hướng hoặc vô hướng.

Đây là một ví dụ về Multi Graph:

Có hai cạnh từ B đến A. Hơn nữa, đỉnh E có một vòng tự lặp. Đồ thị trên là đồ thị có hướng không có trọng số trên các cạnh.

Đồ thị hoàn chỉnh

Một đồ thị hoàn chỉnh nếu mỗi đỉnh có các cạnh có hướng hoặc không có hướng với tất cả các đỉnh khác.

Giả sử có tổng số V đỉnh và mỗi đỉnh có chính xác các cạnh V-1. Khi đó, Biểu đồ này sẽ được gọi là Biểu đồ hoàn chỉnh. Trong loại đồ thị này, mỗi đỉnh được kết nối với tất cả các đỉnh khác thông qua các cạnh.

Dưới đây là ví dụ về Đồ thị hoàn chỉnh có năm đỉnh:

Bạn có thể thấy trong hình tổng số nút là năm và tất cả các nút đều có chính xác bốn cạnh.

Đồ thị được kết nối

Biểu đồ được gọi là Biểu đồ được kết nối nếu chúng ta bắt đầu từ một nút hoặc đỉnh và di chuyển tất cả các nút từ nút bắt đầu. Để làm được điều này, phải có ít nhất một cạnh giữa mỗi cặp nút hoặc đỉnh.

Dưới đây là ví dụ về Biểu đồ được kết nối:

Dưới đây là một số giải thích về biểu đồ “ví dụ biểu đồ hoàn chỉnh” ở trên:

• Giả sử không có cạnh nào giữa C và F, chúng ta không thể di chuyển từ A đến G. Tuy nhiên, cạnh C đến F cho phép chúng ta di chuyển đến bất kỳ nút nào từ một nút nhất định.
• Biểu đồ hoàn chỉnh là Biểu đồ được kết nối vì chúng ta có thể di chuyển từ nút này sang bất kỳ nút nào khác trong Biểu đồ đã cho.

Đồ thị tuần hoàn

Một đồ thị được cho là có tính tuần hoàn nếu có một hoặc nhiều chu trình xuất hiện trong đồ thị.

Đây là một ví dụ về Đồ thị tuần hoàn:

Ở đây các đỉnh A, B, C tạo thành một chu trình.

Một đồ thị có thể có nhiều chu trình bên trong nó.

Đồ thị vòng có hướng (DAG)

Biểu đồ được gọi là Biểu đồ tuần hoàn có hướng hoặc DAG nếu không có chu trình nào bên trong biểu đồ. DAG rất quan trọng khi thực hiện Sắp xếp theo cấu trúc liên kết hoặc tìm thứ tự thực hiện. DAG cũng rất quan trọng trong việc tạo các hệ thống lập kế hoạch hoặc quét sự phụ thuộc của các nguồn lực, v.v. Tuy nhiên, Biểu đồ trên không chứa bất kỳ chu trình nào bên trong.

Đây là một ví dụ đơn giản về Đồ thị chu kỳ có hướng (DAG):

Đồ thị chu kỳ

Biểu đồ chu kỳ không giống với Biểu đồ tuần hoàn. Trong Biểu đồ chu kỳ, mỗi nút sẽ có chính xác hai cạnh được kết nối, nghĩa là mỗi nút sẽ có chính xác hai độ.

Dưới đây là ví dụ về Biểu đồ chu kỳ:

Đồ thị hai bên

Những loại Đồ thị là các loại đồ thị đặc biệt trong đó các đỉnh được gán cho hai tập hợp.

Đồ thị lưỡng cực phải tuân theo quy tắc:

• Hai tập hợp đỉnh phải khác nhau, có nghĩa là tất cả các đỉnh phải được chia thành hai nhóm hoặc hai tập hợp.
• Các đỉnh giống nhau không được tạo thành bất kỳ cạnh nào.

Đồ thị Euler

Cấu trúc dữ liệu đồ thị được coi là Đồ thị Euler nếu tất cả các đỉnh có bậc chẵn. Thuật ngữ bậc của các đỉnh có nghĩa là số cạnh trỏ tới hoặc chỉ ra từ một đỉnh cụ thể.

Đây là một ví dụ về biểu đồ Euler:

Tất cả các đỉnh đều có bậc chẵn. Các đỉnh A, D, E, H có hai độ. Ở đây, nút C có bốn độ, là số chẵn.

Đồ thị Hamilton

Đồ thị Hamilton là Đồ thị kết nối, trong đó bạn có thể truy cập tất cả các đỉnh từ một đỉnh nhất định mà không cần xem lại cùng một nút hoặc sử dụng cùng một cạnh. Loại Biểu đồ được kết nối này được gọi là “Biểu đồ Hamilton”. Đường dẫn bạn truy cập để xác minh xem Đồ thị đã cho có phải là Đồ thị Hamilton hay không được gọi là Đường dẫn Hamilton.

Đây là một ví dụ biểu đồ đơn giản của Hamilton:

Trong hình ảnh này, chúng ta có thể truy cập tất cả các đỉnh từ bất kỳ nút nào trong Biểu đồ trên. Một trong những con đường có thể là ADCHBE. Cũng có thể tìm thấy Chu trình Hamilton. Chu trình Hamilton bắt đầu và kết thúc ở cùng một đỉnh. Vì vậy, chu trình Hamilton sẽ là ADCHBEA.