Xin chào tất cả mọi người.
Trong ghi chú này, tôi quyết định liệt kê các cấu trúc dữ liệu chính được sử dụng để lưu trữ biểu đồ trong khoa học máy tính và tôi cũng sẽ nói về một số cấu trúc khác mà bằng cách nào đó đã “kết tinh” đối với tôi.
Vì vậy, hãy bắt đầu. Nhưng không phải ngay từ đầu - tôi nghĩ tất cả chúng ta đều đã biết đồ thị là gì và chúng là gì (có hướng, không có hướng, có trọng số, không có trọng số, có hoặc không có nhiều cạnh và vòng lặp).
Vì vậy, chúng ta hãy đi. Chúng ta có những lựa chọn nào về cấu trúc dữ liệu để “lưu trữ biểu đồ”?
1. Cấu trúc dữ liệu ma trận
1.1 Ma trận kề. Ma trận kề là ma trận trong đó tiêu đề hàng và cột tương ứng với số đỉnh của đồ thị và giá trị từng phần tử a(i,j) của nó được xác định bởi sự có mặt hay vắng mặt của các cạnh giữa các đỉnh i và j (rõ ràng là đối với đồ thị vô hướng, ma trận như vậy sẽ đối xứng hoặc chúng ta có thể đồng ý rằng chúng ta chỉ lưu trữ tất cả các giá trị phía trên đường chéo chính). Đối với đồ thị không có trọng số, a(i,j) có thể được đặt theo số cạnh từ i đến j (nếu không có cạnh nào như vậy thì a(i,j)= 0) và đối với đồ thị có trọng số, cũng theo trọng số (tổng trọng lượng) của các cạnh được đề cập.
1.2 Ma trận liên thuộc. Trong trường hợp này, biểu đồ của chúng tôi cũng được lưu trữ trong một bảng trong đó, theo quy luật, số hàng tương ứng với số đỉnh của nó và số cột tương ứng với các cạnh được đánh số trước. Nếu một đỉnh và một cạnh gần nhau thì một giá trị khác 1 được ghi vào ô tương ứng (đối với đồ thị vô hướng, 1 được viết nếu đỉnh và cạnh gần nhau, đối với đồ thị có hướng - “1” nếu cạnh “thoát” khỏi đỉnh và “-1” nếu nó “bao gồm” trong đó (điều này đủ dễ nhớ vì dấu “trừ” dường như cũng được “bao gồm” trong số “-1”). Đối với đồ thị có trọng số, một lần nữa, thay vì 1 và -XNUMX, bạn có thể chỉ định tổng trọng số của cạnh.
2. Cấu trúc dữ liệu liệt kê
2.1 Danh sách lân cận. Chà, mọi thứ ở đây có vẻ đơn giản. Nói chung, mỗi đỉnh của đồ thị có thể được liên kết với bất kỳ cấu trúc liệt kê nào (danh sách, vectơ, mảng, ...), cấu trúc này sẽ lưu trữ số lượng của tất cả các đỉnh liền kề với đỉnh đã cho. Đối với đồ thị có hướng, chúng ta sẽ chỉ thêm vào danh sách những đỉnh có cạnh “có hướng” từ một đỉnh đặc trưng. Đối với đồ thị có trọng số, việc thực hiện sẽ phức tạp hơn.
2.2 Danh sách các xương sườn. Một cấu trúc dữ liệu khá phổ biến. Danh sách các cạnh, như Captain Obviousness cho chúng ta biết, thực ra là một danh sách các cạnh của đồ thị, mỗi cạnh được xác định bởi đỉnh bắt đầu, đỉnh kết thúc (đối với đồ thị vô hướng, thứ tự không quan trọng ở đây, mặc dù để thống nhất bạn có thể sử dụng các quy tắc khác nhau, ví dụ: chỉ định các đỉnh theo thứ tự tăng dần) và trọng số (chỉ dành cho đồ thị có trọng số).
Bạn có thể xem danh sách ma trận được liệt kê ở trên một cách chi tiết hơn (và kèm theo hình ảnh minh họa), ví dụ: .
2.3 Mảng liền kề. Không phải là cấu trúc phổ biến nhất. Về cốt lõi, nó là một dạng “đóng gói” các danh sách kề vào một cấu trúc liệt kê (mảng, vectơ). Phần tử n đầu tiên (theo số đỉnh của đồ thị) của một mảng như vậy chứa các chỉ số bắt đầu của cùng một mảng, bắt đầu từ đó tất cả các đỉnh liền kề với mảng đã cho được viết thành một hàng.
Ở đây tôi đã tìm thấy lời giải thích dễ hiểu nhất (đối với bản thân mình):
3. Vectơ kề và mảng kề cận kết hợp
Hóa ra tác giả của những dòng này, không phải là một lập trình viên chuyên nghiệp, nhưng là người định kỳ xử lý đồ thị, thường xử lý danh sách các cạnh. Thật vậy, sẽ thuận tiện nếu đồ thị có nhiều vòng và nhiều cạnh. Và vì vậy, khi phát triển danh sách các cạnh cổ điển, tôi đề xuất chú ý đến “sự phát triển/nhánh/sửa đổi/đột biến” của chúng, cụ thể là: vectơ kề và mảng kề kết hợp.
3.1 Vectơ lân cận
Trường hợp (a1): đồ thị không có trọng số
Chúng ta sẽ gọi vectơ kề của đồ thị không có trọng số là tập hợp có thứ tự của một số số nguyên chẵn (a[2i], a[2i+1],..., trong đó i được đánh số c 0), trong đó mỗi cặp số là a[2i], a[2i+1 ] chỉ định cạnh đồ thị giữa các đỉnh a[2i] và a[2i+1] tương ứng.
Định dạng ghi này không chứa thông tin về việc đồ thị có hướng hay không (có thể có cả hai tùy chọn). Khi sử dụng định dạng đồ thị, cạnh được coi là có hướng từ a[2i] đến a[2i+1]. Ở đây và dưới đây: đối với đồ thị vô hướng, nếu cần, có thể áp dụng yêu cầu về thứ tự ghi các đỉnh (ví dụ: đỉnh có giá trị thấp hơn của số được gán cho nó sẽ đứng trước).
Trong C++, nên chỉ định một vectơ kề bằng cách sử dụng std::vector, do đó có tên của cấu trúc dữ liệu này.
Trường hợp (a2): đồ thị không có trọng số, trọng số các cạnh là số nguyên
Bằng cách tương tự với trường hợp (a1), chúng ta gọi vectơ kề cho đồ thị có trọng số có trọng số cạnh nguyên là một tập hợp có thứ tự (mảng động) gồm các số (a[3i], a[3i+1], a[3i+2], ..., trong đó i được đánh số c 0), trong đó mỗi “bộ ba” số a[3i], a[3i+1], a[3i+2] chỉ định một cạnh của đồ thị giữa các đỉnh được đánh số a[3i] và a[3i+1] tương ứng, và giá trị a [3i+2] là trọng số của cạnh này. Một đồ thị như vậy cũng có thể có hướng hoặc không có hướng.
Trường hợp (b): đồ thị không có trọng số, trọng số cạnh không nguyên
Ví dụ: vì không thể lưu trữ các phần tử không đồng nhất trong một mảng (vectơ), nên có thể triển khai như sau. Đồ thị được lưu trữ trong một cặp vectơ, trong đó vectơ đầu tiên là vectơ kề của đồ thị không xác định trọng số và vectơ thứ hai chứa các trọng số tương ứng (có thể triển khai cho C++: std::pair ). Do đó, đối với một cạnh được xác định bởi một cặp đỉnh có chỉ số 2i, 2i+1 của vectơ thứ nhất, trọng số sẽ bằng phần tử thuộc chỉ số i của vectơ thứ hai.
Chà, tại sao điều này lại cần thiết?
Chà, tác giả của những dòng này thấy nó khá hữu ích trong việc giải quyết một số vấn đề. Vâng, từ quan điểm chính thức, sẽ có những lợi thế sau:
- Vectơ kề, giống như bất kỳ cấu trúc “liệt kê” nào khác, khá nhỏ gọn, chiếm ít bộ nhớ hơn ma trận kề (đối với đồ thị thưa thớt) và tương đối dễ thực hiện.
- Về nguyên tắc, các đỉnh của đồ thị cũng có thể được đánh dấu bằng số âm. Điều gì sẽ xảy ra nếu cần phải có sự “biến thái” như vậy?
- Đồ thị có thể chứa nhiều cạnh và nhiều vòng lặp, với các trọng số khác nhau (dương, âm, thậm chí bằng XNUMX). Không có hạn chế ở đây.
- Bạn cũng có thể gán các thuộc tính khác nhau cho các cạnh - nhưng để biết thêm về điều đó, hãy xem phần 4.
Tuy nhiên, phải thừa nhận rằng “danh sách” này không hàm ý việc truy cập nhanh vào rìa. Và ở đây Mảng liền kề kết hợp sẽ ra tay giải cứu, điều này sẽ được thảo luận dưới đây.
3.2 Mảng kề kết hợp
Vì vậy, nếu quyền truy cập vào một cạnh cụ thể, trọng số và các thuộc tính khác của nó là rất quan trọng đối với chúng ta và các yêu cầu về bộ nhớ không cho phép chúng ta sử dụng ma trận kề, thì hãy suy nghĩ về cách chúng ta có thể thay đổi vectơ kề để giải quyết vấn đề này. Vì vậy, khóa là một cạnh của biểu đồ, có thể được chỉ định dưới dạng một cặp số nguyên có thứ tự. điều này như thế nào? Nó không phải là một chìa khóa trong một mảng kết hợp sao? Và nếu vậy thì tại sao chúng ta không thực hiện nó? Chúng ta hãy có một mảng kết hợp trong đó mỗi khóa - một cặp số nguyên có thứ tự - sẽ được liên kết với một giá trị - một số nguyên hoặc một số thực xác định trọng số của cạnh. Trong C++, nên triển khai cấu trúc này dựa trên vùng chứa std::map (std::map , int> hoặc std::map , double>) hoặc std::multimap nếu mong đợi có nhiều cạnh. Chà, chúng tôi có một cấu trúc để lưu trữ đồ thị chiếm ít bộ nhớ hơn cấu trúc “ma trận”, có thể xác định đồ thị có nhiều vòng và cạnh và thậm chí không có yêu cầu nghiêm ngặt về tính không âm của số đỉnh (tôi không biết ai cần cái này, nhưng vẫn vậy).
4. Cấu trúc dữ liệu đã đầy nhưng thiếu một cái gì đó
Và điều đó đúng: khi giải một số bài toán, chúng ta có thể cần gán một số đặc điểm cho các cạnh của biểu đồ và theo đó, lưu trữ chúng. Nếu có thể giảm rõ ràng các tính năng này thành số nguyên, thì có thể lưu trữ “đồ thị với các tính năng bổ sung” bằng cách sử dụng các phiên bản mở rộng của vectơ kề và mảng kề kết hợp.
Vì vậy, chúng ta hãy có một biểu đồ không có trọng số, ví dụ, đối với mỗi cạnh của biểu đồ đó cần lưu trữ 2 tính năng bổ sung được chỉ định bởi số nguyên. Trong trường hợp này, có thể định nghĩa vectơ kề của nó là một tập có thứ tự không phải là “cặp”, mà là “bộ tứ” số nguyên (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , trong đó a[2i+2] và a[2i+3] sẽ xác định các đặc điểm của cạnh tương ứng. Đối với đồ thị có trọng số của các cạnh là số nguyên, thứ tự nhìn chung là tương tự nhau (sự khác biệt duy nhất là các thuộc tính sẽ tuân theo trọng số của cạnh và sẽ được chỉ định bởi các phần tử a[2i+3] và a[2i+4] và bản thân cạnh sẽ được chỉ định không phải là 4 mà là 5 số có thứ tự). Và đối với biểu đồ có trọng số cạnh không nguyên, các đặc điểm có thể được ghi vào thành phần không có trọng số của nó.
Khi sử dụng mảng kề kết hợp cho đồ thị có trọng số cạnh nguyên, có thể chỉ định dưới dạng một giá trị không phải là một số mà là một mảng (vectơ) gồm các số chỉ định, ngoài trọng số của một cạnh, tất cả những thứ cần thiết khác. đặc trưng. Đồng thời, một sự bất tiện đối với trường hợp trọng số không nguyên là cần phải chỉ định một dấu hiệu có số dấu phẩy động (vâng, đây là một sự bất tiện, nhưng nếu không có quá nhiều dấu hiệu như vậy và nếu bạn không Đừng đặt chúng quá “khó” gấp đôi thì có thể chẳng là gì cả). Điều này có nghĩa là trong C++, mảng kề cận kết hợp mở rộng có thể được định nghĩa như sau: std::map , std::vector> hoặc std::map , std::vector, trong đó giá trị đầu tiên trong “khóa-giá trị-vectơ” sẽ là trọng số của cạnh và sau đó đặt các ký hiệu số cho các đặc tính của nó.
Văn chương:
Về đồ thị và thuật toán nói chung:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Thuật toán: xây dựng và phân tích, tái bản lần 2: Trans. từ tiếng Anh – M.: Nhà xuất bản Williams, 2011.
2. Harari Frank. Lý thuyết đồ thị. M.: Mir, 1973.
Báo cáo của tác giả về cùng một vectơ và mảng kết hợp của các vùng lân cận:
3. Chernoukhov S.A. Vectơ kề và mảng kề cận kết hợp là cách biểu diễn và lưu trữ đồ thị / SA Chernouhov. Vectơ kề và bản đồ kề dưới dạng cấu trúc dữ liệu để biểu diễn biểu đồ // Tuyển tập các bài báo của Hội nghị khoa học và thực tiễn quốc tế “Các vấn đề về triển khai kết quả của sự phát triển đổi mới và cách giải quyết chúng” (Saratov, ngày 14.09.2019 tháng 2019 năm 65). – Sterlitamak: AMI, 69, tr. XNUMX-XNUMX
Các nguồn trực tuyến hữu ích về chủ đề này:
4.
5.
Nguồn: www.habr.com