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ạnh. Các đỉnh chứa thông tin hoặc dữ liệu, và các cạnh đóng vai trò liên kết giữa một cặp đỉnh.

Đồ thị có thể có nhiều loại khác nhau, 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 đồ thị 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 biểu thị hướng. Mũi tên xác định cạnh đó hướng đến đâu hoặc kết thúc ở đâu. Dưới đây là một ví dụ về đồ thị có hướng.

Đồ 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ạnh này hướng 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 này có nghĩa là ta có thể di chuyển ngược chiều giữa hai đỉnh. Dưới đây là một ví dụ đơn giản về đồ thị vô hướng.

Đồ thị vô hướng

Trong biểu đồ trên,

• Chúng ta có thể di chuyển từ điểm A đến điểm 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.

Đây 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ị có 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ị 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. Dưới đây là một ví dụ về đồ thị có trọng số (có hướng).

Đồ thị có hướng có trọng số

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

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

Đồ 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à:

• Nhìn 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.

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

Đồ thị hai chiều

Di chuyển từ A đến D sẽ tốn 17, nhưng di chuyển 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

Đồ thị sẽ chứa vô số cạnh và nút. Nếu một đồ thị là vô hạn và 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 khác. Dưới đây là một ví dụ về đồ thị vô hạn:

Đồ thị vô hạn

Đồ thị rỗng

Đồ thị rỗng 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à các đỉnh và E là các cạnh, thì đồ thị đó sẽ là đồ thị rỗng nếu số cạnh của E bằng không. Sau đây là một ví dụ về đồ thị rỗng:

Đồ thị rỗng

Đồ thị tầm thường

Một 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 duy nhất mà không có cạnh nào. Dưới đây là một ví dụ về Đồ thị tầm thường:

Đa đồ thị

Một đồ thị được gọi là đa đồ thị khi có nhiều cạnh nối 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. Đa đồ thị có thể là có hướng hoặc không có hướng. Sau đây là một ví dụ về Đa đồ thị:

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

Đồ thị hoàn chỉnh

Một đồ thị được gọi là đồ thị đầy đủ nếu mỗi đỉnh có các cạnh có hướng hoặc không hướng nối với tất cả các đỉnh khác. Giả sử có tổng cộng V đỉnh và mỗi đỉnh có chính xác V-1 cạnh. Khi đó, đồ thị này được gọi là đồ thị đầy đủ. 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à một ví dụ về đồ thị đầy đủ với năm đỉnh:

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

Một đồ thị được gọi là đồ thị liên thông nếu ta bắt đầu từ một nút hoặc đỉnh và có thể di chuyển đến tất cả các nút từ nút xuất phát. Để điều này xảy ra, 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à một ví dụ về đồ thị liên thông:

Dưới đây là một số giải thích về Đồ thị liên thông ở trên:

• Giả sử không có cạnh nối giữa C và F, ta không thể di chuyển từ A đến G. Tuy nhiên, cạnh nối C đến F cho phép ta di chuyển đến bất kỳ nút nào từ một nút cho trước.
• 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 gọi là đồ thị có chu trình nếu nó chứa một hoặc nhiều chu trình. Dưới đây là một ví dụ về đồ thị có chu trình:

Ở đây, các đỉnh A, B và 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)

Một đồ thị được gọi là Đồ thị có hướng không chu trình (DAG) nếu không có chu trình nào bên trong đồ thị đó. DAG rất quan trọng khi thực hiện việc tính toán. Sắp xếp theo cấu trúc liên kết hoặc tìm thứ tự thực thi. DAG cũng rất quan trọng để tạo ra các hệ thống lập lịch hoặc quét sự phụ thuộc của các tài nguyên, v.v. Tuy nhiên, đồ thị trên không chứa bất kỳ chu trình nào bên trong. Dưới đây là một ví dụ đơn giản về Đồ thị có hướng không chu trình (DAG):

Đồ thị chu kỳ

Đồ thị chu trình không giống với đồ thị có chu trình. Trong đồ thị chu trình, 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 bậc. Dưới đây là một ví dụ về đồ thị chu trình:

Đồ thị hai bên

Những loại Đồ thị Đồ thị hai phía là một loại đồ thị đặc biệt trong đó các đỉnh được gán cho hai tập hợp. Đồ thị hai phía phải tuân theo quy tắc:

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

Đồ thị Euler

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

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

Đồ thị Hamilton

Đồ thị Hamilton là một đồ thị liên thông, trong đó bạn có thể đi qua tất cả các đỉnh từ một đỉnh cho trước mà không cần đi qua cùng một nút hoặc sử dụng cùng một cạnh. Loại đồ thị liên thông này được gọi là "đồ thị Hamilton". Đường đi bạn thực hiện để kiểm tra xem đồ thị đã cho có phải là đồ thị Hamilton hay không được gọi là đường đi Hamilton. Dưới đây là một ví dụ đơn giản về đồ thị 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à ADCHBECũng có thể tìm được một chu trình Hamilton. Chu trình Hamilton bắt đầu và kết thúc tại cùng một đỉnh. Vì vậy, chu trình Hamilton sẽ là... ADCHBEA.

Câu Hỏi Thường Gặp