Phần 2 Phần 3 Phần 4 Tôi được nhắc viết bài này bởi một nhiệm vụ có hại từ nhiệm vụ Đa luồng Java, nhiệm vụ này, không phải không có một số lời trêu chọc từ các nhà phát triển, được họ gọi là “nhiệm vụ StringBuilder”. Bản chất tình trạng của cô là một tập hợp các từ (trong điều kiện tên các thành phố được đưa ra, gợi nhớ đến trò chơi chữ của trẻ em) phải được sắp xếp theo nguyên tắc domino, chữ cái cuối cùng của từ n' phải là bằng chữ cái đầu tiên của từ (n+1) go, và người ta biết rằng tất cả các từ (riêng lẻ) đã cho đều được cộng lại thành một chuỗi như vậy. Nếu có thể soạn ra một số phương án cho chuỗi từ mong muốn thì phương án nào cũng được chấp nhận làm giải pháp. Bất chấp sự đơn giản và rõ ràng của tình trạng, việc giải quyết vấn đề không hề dễ dàng và việc sử dụng thành thạo StringBuilder đã không cứu vãn được tình hình. Các nhà phát triển của vấn đề hóa ra là những người đồng hình được đặt hàng từ hành tinh Linear Chaos, kẻ đã hơn một lần khiến các học viên JavaRush khiếp sợ. Đúng như dự đoán, các giải pháp hời hợt không phù hợp với người xác thực, vì luôn có những chuỗi buộc thuật toán ngây thơ phải bỏ qua các từ. Cần phải chất thêm những chiếc nạng bổ sung, tuy làm phức tạp vấn đề nhưng không đưa giải pháp đến gần hơn trong trường hợp tổng quát và ngày càng củng cố cảm giác rằng một điều kiện đơn giản phải có giải pháp đơn giản tương đương. Tôi phải thay đổi chiến thuật và đi sâu hơn một chút vào các lĩnh vực cơ bản hơn. Hãy để tôi bảo lưu ngay rằng trong mọi trường hợp tôi không coi mình là chuyên gia về lý thuyết đồ thị; các chủ đề mà tôi sẽ đề cập hầu như không vượt quá phạm vi giải bài toán domino, có lẽ ngoại trừ chỉ một vài lạc đề có tính chất lý thuyết. Vì vậy, đồ thị. Biểu đồ là gì: nó là một tập hợp (tập hợp, tập hợp, danh sách - bất cứ thứ gì) các đỉnh được kết nối với nhau . Các kết nối thường được gọi là các cạnh , các đỉnh còn được gọi là nút hoặc nút. Đây là một đồ thị: Đây cũng là một đồ thị: Nếu chúng ta có thể nói về một cạnh mà nó có hướng thì đồ thị đó được gọi là có hướng : Đồ thị trong hai hình đầu tiên là đồ thị vô hướng. Về chúng, chúng ta có thể nói rằng cạnh (u, v) giống với cạnh (v, u), tức là cạnh (0, 4) và (4, 0) là cùng một cạnh. Mũi tên trên các cạnh của đồ thị có hướng có nghĩa là cạnh (u, v) là đường đi từ đỉnh u đến đỉnh v và cạnh (v, u) không tồn tại. Trong hình thứ ba có một cạnh (E, A). Không có cạnh (A, E). Chúng ta hãy xem xét kỹ hơn bản vẽ cuối cùng. Bạn có thể nhận thấy rằng đỉnh F không có cạnh nào cả, điều này hoàn toàn có thể xảy ra. Chúng tôi cũng lưu ý rằng một cạnh đã xuất hiện gần đỉnh A - một vòng lặp và giữa đỉnh B và D có hai cạnh có hướng khác nhau. Đồ thị có hướng cho phép tạo tác như vậy. Giả sử biểu đồ mô tả một nhóm người quen tặng quà cho nhau. Ta thấy F tham lam không đưa gì cho ai cả, B và D trao đổi quà (trừ việc mỗi người tặng quà cho người khác), còn A tự tặng quà cho mình, chắc là nhân dịp giải quyết thành công một vụ án. vấn đề từ hành tinh Linear Chaos. Nhân tiện, hãy lưu ý rằng các đỉnh của biểu đồ không nhất thiết phải là số hoặc chứa số; chúng là các thùng chứa, tức là. họ có thể lưu trữ bất kỳ đối tượng nào. Biểu đồ là sự mô tả các kết nối. Một thuật ngữ quan trọng sẽ hữu ích cho chúng ta sau này - số cạnh gắn với một đỉnh (hoặc, như người ta cũng nói, phụ thuộc vào nó) được gọi là bậc của một đỉnh đã cho. Ví dụ: ở hình thứ nhất, đỉnh 0 có bậc 2, 1 có bậc 4, 3 có bậc 3, đỉnh 0 của hình thứ hai có bậc 1. Trong bài viết này chúng ta sẽ không đi sâu vào sự đa dạng của các loại đồ thị khác nhau, chúng tôi sẽ chỉ đề cập rằng cũng có những biểu đồ có trọng số. những cái trong đó một số nhất định được gắn vào mỗi cạnh, biểu thị “giá” của đoạn văn đó. Các biểu đồ liên kết có một số kiểu con, được phân biệt bằng các thuộc tính của chúng. Ví dụ: các đồ thị có các cạnh không tạo thành chu trình ở bất kỳ đâu được gọi là cây (chúng có các họ thú vị với những cái tên hay như “cây đỏ-đen”) và được sử dụng rộng rãi trong nhiều thuật toán và cấu trúc dữ liệu quan trọng. Bạn nói , sử dụng biểu đồ để giải bài toán Tất cả những điều này rất thú vị, nhưng tất cả những điều này có liên quan gì đến việc xây dựng một chuỗi từ? Hóa ra điều trực tiếp nhất là. Hãy xem ví dụ thử nghiệm của chúng tôi với điều kiện: { Amsterdam Melbourne New York Kyiv Vienna }. Hãy viết theo thứ tự bất kỳ các chữ cái "nút" mà các từ bám vào: {A, M, N, K, B} và nối chúng với các từ. Như chúng ta thấy, chúng ta có một đồ thị có hướng trong đó các nút là các chữ cái và các cạnh là các từ, kết nối chúng. Nếu chúng ta tìm được cách đi qua tất cả các cạnh từ đỉnh này sang đỉnh khác sao cho chỉ ghé thăm mỗi cạnh một lần thì vấn đề của chúng ta sẽ được giải quyết. Hãy thử phân phối các nút trong sơ đồ khác nhau một chút: Bây giờ chúng ta có thể thấy rõ hơn rằng đồ thị của chúng ta là một vòng khép kín. Chúng ta có thể bắt đầu chuỗi bằng bất kỳ từ nào và đó sẽ là quyết định đúng đắn. Tuy nhiên, điều kiện của bài toán cho chúng ta biết rằng bất kỳ một giải pháp nào cũng đủ. Hãy thay Vena bằng Vladimir: Chúng ta thấy hai hậu quả: thứ nhất, chúng ta phải thêm một đỉnh mới, chữ P, và thứ hai, chúng ta thấy rằng không thể lặp biểu đồ của mình được nữa. Hãy tóm tắt tất cả những điều trên và giới thiệu hai thuật ngữ mới: 1. Một đồ thị liên thông có các cạnh có thể đi qua bằng cách ghé thăm mỗi cạnh chỉ một lần được gọi là đồ thị chứa “đường đi Euler ” . Đặc điểm của đồ thị như vậy (ngoại trừ việc không có đỉnh không có cạnh) là bậc chẵn của tất cả các đỉnh ngoại trừ hai (và chỉ hai). 2. Nếu có thể quay lại nút ban đầu, chúng ta nói rằng có một “chu trình Euler” trong biểu đồ . Một đặc điểm của đồ thị như vậy (ngoại trừ việc không có đỉnh không có cạnh) là bậc chẵn của tất cả các đỉnh. Hãy tưởng tượng danh sách các thành phố của chúng ta như thế này: {Moscow Anapa Adler Rostov-on-Don Vũ Hán}. Hãy xây dựng một biểu đồ: Trong sơ đồ bạn có thể thấy biểu đồ này có đường đi Euler. Chỉ có hai đỉnh có bậc lẻ là M và L, các đỉnh còn lại là bậc chẵn: A có bậc 4, vì vòng lặp được tính hai lần và P và Y có bậc 2. Nếu chúng ta đưa ra một thuật toán có thể xây dựng tuyến đường Euler dựa trên sơ đồ này, chẳng hạn, ở dạng danh sách {M, A, A, P, Y , L} thì ta sẽ giải được bài toán , vì việc xuất các từ theo một thứ tự nhất định sẽ chỉ là vấn đề kỹ thuật. Do đó, giải pháp cho vấn đề từ domino của chúng ta là thực hiện một thuật toán tìm đường đi Euler (chu trình “tự do”) trong đồ thị có hướng. Tiếp theo ->
Đây cũng là một đồ thị: 
Nếu chúng ta có thể nói về một cạnh mà nó có hướng thì đồ thị đó được gọi là có hướng : 
Đồ thị trong hai hình đầu tiên là đồ thị vô hướng. Về chúng, chúng ta có thể nói rằng cạnh (u, v) giống với cạnh (v, u), tức là cạnh (0, 4) và (4, 0) là cùng một cạnh. Mũi tên trên các cạnh của đồ thị có hướng có nghĩa là cạnh (u, v) là đường đi từ đỉnh u đến đỉnh v và cạnh (v, u) không tồn tại. Trong hình thứ ba có một cạnh (E, A). Không có cạnh (A, E). Chúng ta hãy xem xét kỹ hơn bản vẽ cuối cùng. Bạn có thể nhận thấy rằng đỉnh F không có cạnh nào cả, điều này hoàn toàn có thể xảy ra. Chúng tôi cũng lưu ý rằng một cạnh đã xuất hiện gần đỉnh A - một vòng lặp và giữa đỉnh B và D có hai cạnh có hướng khác nhau. Đồ thị có hướng cho phép tạo tác như vậy. Giả sử biểu đồ mô tả một nhóm người quen tặng quà cho nhau. Ta thấy F tham lam không đưa gì cho ai cả, B và D trao đổi quà (trừ việc mỗi người tặng quà cho người khác), còn A tự tặng quà cho mình, chắc là nhân dịp giải quyết thành công một vụ án. vấn đề từ hành tinh Linear Chaos. Nhân tiện, hãy lưu ý rằng các đỉnh của biểu đồ không nhất thiết phải là số hoặc chứa số; chúng là các thùng chứa, tức là. họ có thể lưu trữ bất kỳ đối tượng nào. Biểu đồ là sự mô tả các kết nối. Một thuật ngữ quan trọng sẽ hữu ích cho chúng ta sau này - số cạnh gắn với một đỉnh (hoặc, như người ta cũng nói, phụ thuộc vào nó) được gọi là bậc của một đỉnh đã cho. Ví dụ: ở hình thứ nhất, đỉnh 0 có bậc 2, 1 có bậc 4, 3 có bậc 3, đỉnh 0 của hình thứ hai có bậc 1. Trong bài viết này chúng ta sẽ không đi sâu vào sự đa dạng của các loại đồ thị khác nhau, chúng tôi sẽ chỉ đề cập rằng cũng có những biểu đồ có trọng số. những cái trong đó một số nhất định được gắn vào mỗi cạnh, biểu thị “giá” của đoạn văn đó. Các biểu đồ liên kết có một số kiểu con, được phân biệt bằng các thuộc tính của chúng. Ví dụ: các đồ thị có các cạnh không tạo thành chu trình ở bất kỳ đâu được gọi là cây (chúng có các họ thú vị với những cái tên hay như “cây đỏ-đen”) và được sử dụng rộng rãi trong nhiều thuật toán và cấu trúc dữ liệu quan trọng. Bạn nói , sử dụng biểu đồ để giải bài toán Tất cả những điều này rất thú vị, nhưng tất cả những điều này có liên quan gì đến việc xây dựng một chuỗi từ? Hóa ra điều trực tiếp nhất là. Hãy xem ví dụ thử nghiệm của chúng tôi với điều kiện: { Amsterdam Melbourne New York Kyiv Vienna }. Hãy viết theo thứ tự bất kỳ các chữ cái "nút" mà các từ bám vào: {A, M, N, K, B} 
và nối chúng với các từ. 
Như chúng ta thấy, chúng ta có một đồ thị có hướng trong đó các nút là các chữ cái và các cạnh là các từ, kết nối chúng. Nếu chúng ta tìm được cách đi qua tất cả các cạnh từ đỉnh này sang đỉnh khác sao cho chỉ ghé thăm mỗi cạnh một lần thì vấn đề của chúng ta sẽ được giải quyết. Hãy thử phân phối các nút trong sơ đồ khác nhau một chút: 
Bây giờ chúng ta có thể thấy rõ hơn rằng đồ thị của chúng ta là một vòng khép kín. Chúng ta có thể bắt đầu chuỗi bằng bất kỳ từ nào và đó sẽ là quyết định đúng đắn. Tuy nhiên, điều kiện của bài toán cho chúng ta biết rằng bất kỳ một giải pháp nào cũng đủ. Hãy thay Vena bằng Vladimir: 
Chúng ta thấy hai hậu quả: thứ nhất, chúng ta phải thêm một đỉnh mới, chữ P, và thứ hai, chúng ta thấy rằng không thể lặp biểu đồ của mình được nữa. Hãy tóm tắt tất cả những điều trên và giới thiệu hai thuật ngữ mới: 1. Một đồ thị liên thông có các cạnh có thể đi qua bằng cách ghé thăm mỗi cạnh chỉ một lần được gọi là đồ thị chứa “đường đi Euler ” . Đặc điểm của đồ thị như vậy (ngoại trừ việc không có đỉnh không có cạnh) là bậc chẵn của tất cả các đỉnh ngoại trừ hai (và chỉ hai). 2. Nếu có thể quay lại nút ban đầu, chúng ta nói rằng có một “chu trình Euler” trong biểu đồ . Một đặc điểm của đồ thị như vậy (ngoại trừ việc không có đỉnh không có cạnh) là bậc chẵn của tất cả các đỉnh. Hãy tưởng tượng danh sách các thành phố của chúng ta như thế này: {Moscow Anapa Adler Rostov-on-Don Vũ Hán}. Hãy xây dựng một biểu đồ: 
Trong sơ đồ bạn có thể thấy biểu đồ này có đường đi Euler. Chỉ có hai đỉnh có bậc lẻ là M và L, các đỉnh còn lại là bậc chẵn: A có bậc 4, vì vòng lặp được tính hai lần và P và Y có bậc 2. Nếu chúng ta đưa ra một thuật toán có thể xây dựng tuyến đường Euler dựa trên sơ đồ này, chẳng hạn, ở dạng danh sách {M, A, A, P, Y , L} thì ta sẽ giải được bài toán , vì việc xuất các từ theo một thứ tự nhất định sẽ chỉ là vấn đề kỹ thuật. Do đó, giải pháp cho vấn đề từ domino của chúng ta là thực hiện một thuật toán tìm đường đi Euler (chu trình “tự do”) trong đồ thị có hướng. Tiếp theo ->
GO TO FULL VERSION