Hướng dẫn về cấu trúc dữ liệu biểu đồ

Một lập trình viên hiệu quả cần có hiểu biết vững chắc về cấu trúc dữ liệu và thuật toán. Các cuộc phỏng vấn kỹ thuật thường sẽ kiểm tra kỹ năng giải quyết vấn đề và tư duy phản biện của bạn.

Đồ thị là một trong nhiều cấu trúc dữ liệu quan trọng trong lập trình. Trong hầu hết các trường hợp, việc hiểu đồ thị và giải các bài toán dựa trên đồ thị không hề dễ dàng.

mở khóa điện thoại di động của tôi miễn phí

LÀM VIDEO TRONG NGÀY

Biểu đồ là gì và bạn cần biết gì về nó?

Đồ thị là gì?

Đồ thị là một cấu trúc dữ liệu phi tuyến tính có các nút (hoặc đỉnh) với các cạnh kết nối chúng. Tất cả các cây đều là các kiểu con của đồ thị, nhưng không phải tất cả các đồ thị đều là cây và biểu đồ là cấu trúc dữ liệu mà cây bắt nguồn từ đó.

Mặc dù bạn có thể xây dựng cấu trúc dữ liệu trong JavaScript và các ngôn ngữ khác, bạn có thể triển khai biểu đồ theo nhiều cách khác nhau. Các cách tiếp cận phổ biến nhất là danh sách cạnh , danh sách gần kề , và ma trận kề .

Các Học viện Khan hướng dẫn biểu diễn đồ thị là một nguồn tài nguyên tuyệt vời để tìm hiểu về cách biểu diễn một biểu đồ.

android 7 chuyển ứng dụng sang thẻ sd

Có nhiều dạng đồ thị khác nhau. Một sự khác biệt phổ biến là giữa Chỉ đạo và vô hướng đồ thị; chúng xuất hiện rất nhiều trong các thách thức mã hóa và sử dụng trong đời thực.

Các loại đồ thị

Đồ thị có hướng: Một đồ thị trong đó tất cả các cạnh đều có hướng, còn được gọi là đồ thị.
Biểu đồ vô hướng: Đồ thị vô hướng còn được gọi là đồ thị hai chiều. Trong đồ thị vô hướng, hướng của các cạnh không quan trọng và đường truyền có thể đi theo bất kỳ hướng nào.
Đồ thị có trọng số: Đồ thị có trọng số là đồ thị mà các nút và cạnh của nó có giá trị liên quan. Trong hầu hết các trường hợp, giá trị này đại diện cho chi phí khám phá nút hoặc cạnh đó.
Đồ thị hữu hạn: Một đồ thị có số nút và số cạnh hữu hạn.
Đồ thị vô hạn: Một đồ thị có vô số nút và số cạnh.
Biểu đồ tầm thường: Một đồ thị chỉ có một nút và không có cạnh.
Đồ thị đơn giản: Khi chỉ có một cạnh nối từng cặp nút của đồ thị, nó được gọi là đồ thị đơn giản.
Đồ thị rỗng: Đồ thị rỗng là đồ thị không có cạnh nối các nút của nó.
Nhiều đồ thị: Trong một đồ thị, ít nhất một cặp nút có nhiều hơn một cạnh nối chúng. Trong nhiều đồ thị, không có vòng lặp tự.
Hoàn thành đồ thị: Một biểu đồ hoàn chỉnh là một biểu đồ trong đó mọi nút kết nối với mọi nút khác trong biểu đồ. Nó còn được gọi là đồ thị đầy đủ .
Đồ thị giả: Một đồ thị có một vòng tự ngoài các cạnh đồ thị khác được gọi là đồ thị giả.
Biểu đồ thông thường: Đồ thị thông thường là đồ thị trong đó tất cả các nút đều có hoành độ bằng nhau; tức là mọi nút đều có cùng số lượng lân cận.
Biểu đồ được kết nối: Một đồ thị được kết nối đơn giản là bất kỳ đồ thị nào trong đó hai nút bất kỳ kết nối với nhau; tức là một đồ thị có ít nhất một đường đi giữa mỗi hai nút của đồ thị.
Biểu đồ bị ngắt kết nối: Một đồ thị không kết nối là đối lập trực tiếp với một đồ thị được liên thông. Trong một biểu đồ bị ngắt kết nối, không có cạnh nào liên kết các nút của biểu đồ, chẳng hạn như trong vô giá trị đồ thị.
Đồ thị tuần hoàn: Đồ thị tuần hoàn là đồ thị có chứa ít nhất một chu trình đồ thị (đường dẫn kết thúc tại nơi nó bắt đầu).
Đồ thị acyclic: Đồ thị mạch hở là đồ thị không có chu trình nào cả. Nó có thể được định hướng hoặc vô hướng.
Đoạn con: Một đồ thị con là một đồ thị dẫn xuất. Nó là một đồ thị được hình thành từ các nút và các cạnh là các tập con của một đồ thị khác.