Là chuỗi hàng đợi ưu tiên python

Queue. First-In, First-Out [FIFO]

The word queue can have different meanings depending on the context. However, when people refer to a queue without using any qualifiers, they usually mean a FIFO queue, which resembles a line that you might find at a grocery checkout or tourist attraction

Note that unlike the line in the photo, where people are clustering side by side, a queue in a strict sense will be single file, with people admitted one at a time

FIFO is short for first-in, first-out, which describes the flow of elements through the queue. Elements in such a queue will be processed on a first-come, first-served basis, which is how most real-life queues work. To better visualize the element movement in a FIFO queue, have a look at the following animation

Notice that, at any given time, a new element is only allowed to join the queue on one end called the tail—which is on the right in this example—while the oldest element must leave the queue from the opposite end. When an element leaves the queue, then all of its followers shift by exactly one position towards the head of the queue. These few rules ensure that elements are processed in the order of their arrival

Note. You can think of elements in a FIFO queue as cars stopping at a traffic light

Adding an element to the FIFO queue is commonly referred to as an enqueue operation, while retrieving one from it is known as a dequeue operation. Don’t confuse a dequeue operation with the deque [double-ended queue] data type that you’ll learn about later

Enqueuing and dequeuing are two independent operations that may be taking place at different speeds. This fact makes FIFO queues the perfect tool for buffering data in streaming scenarios and for scheduling tasks that need to wait until some shared resource becomes available. For example, a web server flooded with HTTP requests might place them in a queue instead of immediately rejecting them with an error

Note. In programs that leverage concurrency, a FIFO queue often becomes the shared resource itself to facilitate two-way communication between asynchronous workers. By temporarily locking the read or write access to its elements, a blocking queue can elegantly coordinate a pool of producers and a pool of consumers. You’ll find more information about this use case in later sections about queues in multithreading and multiprocessing

Another point worth noting about the queue depicted above is that it can grow without bounds as new elements arrive. Picture a checkout line stretching to the back of the store during a busy shopping season. In some situations, however, you might prefer to work with a bounded queue that has a fixed capacity known up front. A bounded queue can help to keep scarce resources under control in two ways

1. Bằng cách từ chối không thể đảo ngược các yếu tố không phù hợp
2. By overwriting the oldest element in the queue

Under the first strategy, once a FIFO queue becomes saturated, it won’t take any more elements until others leave the queue to make some space. You can see an animated example of how this works below

This queue has a capacity of three, meaning it can hold at most three elements. If you try to stuff more elements into it, then they’ll bounce off into oblivion without leaving any trace behind. At the same time, as soon as the number of elements occupying the queue decreases, the queue will start accepting new elements again

Where would you find such a bounded FIFO queue in the wild?

Most digital cameras support the burst mode for continuously shooting a series of pictures as rapidly as possible in the hope of capturing at least one sharp photo of a moving object. Because saving data onto a memory card is the bottleneck, there’s usually an internal buffer that enables the camera to keep taking new pictures while earlier ones are being compressed and saved

In older still cameras, the buffer was usually quite small and would fill up within a few seconds. Khi điều đó xảy ra, việc giữ nút chụp sẽ không còn tác dụng nữa hoặc tốc độ chụp ảnh mới sẽ giảm đáng kể. Tốc độ tối đa của máy ảnh sẽ chỉ phục hồi hoàn toàn sau khi sử dụng hết bộ đệm dữ liệu

Chiến lược thứ hai để xử lý các phần tử đến trong hàng đợi FIFO có giới hạn cho phép bạn triển khai bộ đệm ẩn cơ bản quên phần tử cũ nhất mà không cần xem xét bạn đã truy cập phần tử đó bao nhiêu lần hoặc tần suất như thế nào. Bộ đệm FIFO hoạt động tốt nhất khi các phần tử mới hơn có nhiều khả năng được sử dụng lại hơn các phần tử cũ hơn. Ví dụ: bạn có thể sử dụng chiến lược loại bỏ bộ đệm ẩn FIFO để đăng xuất mạnh mẽ những người dùng đã đăng nhập từ lâu bất kể họ có còn hoạt động hay không

Ghi chú. For a brief comparison of other cache eviction strategies, head over to Caching in Python Using the LRU Cache Strategy

Here’s a visual depiction of a bounded FIFO queue that can hold up to three elements but, unlike before, won’t prevent you from adding more elements

When this queue reaches its maximum capacity, then adding a new element will first shift all existing elements by one position towards the head, discarding the oldest element and making room for the new one. Notice that the discarded element gets overwritten by its immediate neighbor

While the unbounded FIFO queue and its two bounded counterparts cover a wide range of use cases, they all share one common feature—that is, having separate entry and exit points. In the next section, you’ll learn about yet another popular type of queue, which has a slightly different layout

Stack. Last-In, First-Out [LIFO]

A stack is a more specialized queue, also known as a LIFO or last-in, first-out queue. It works almost exactly like a regular queue, except that elements must now join and leave it through only one end called the top of the stack. The name top reflects the fact that real-world stacks tend to be vertical. A pile of plates in the kitchen sink is an example of a stack

When the dishwasher is full, employees will push their dirty plates on the top of the stack after having a meal. Once there are no more clean plates in the cabinet, a hungry employee will have to pop the last dirty plate from the top of the stack and clean it with a sponge before microwaving their lunch

If there’s a much-needed fork at the bottom of the stack, then some poor soul will have to dig through all of the plates above, one by one, to get to the desired utensil. Similarly, when the cleaning personnel comes to the office at the end of a business day, they’ll have to go through the plates in reverse order before getting to the last one at the bottom of the stack

You’ll see this element movement in the following animated stack

Even though the LIFO queue above is oriented horizontally, it preserves the general idea of a stack. New elements grow the stack by joining it only on the right end, as in the previous examples. This time, however, only the last element pushed onto the stack can leave it. Phần còn lại phải đợi cho đến khi không còn phần tử nào tham gia vào ngăn xếp sau

Stacks are widely used in computing for various purposes. Perhaps the most familiar context for a programmer is the call stack containing the functions in the order they were called. Python will reveal this stack to you through a traceback in case of an unhandled exception. It’s usually a bounded stack with a limited capacity, which you’ll find out about during a stack overflow error caused by too many recursive calls

In compiled languages with static type checking, local variables are allocated on the stack, which is a fast memory region. Stacks can help detect unmatched brackets in a code block or evaluate arithmetic expressions represented in reverse Polish notation [RPN]. You can also use stacks to solve the Tower of Hanoi puzzle or keep track of the visited nodes in a graph or a tree traversed with the depth-first search [DFS] algorithm

Note. When you replace the stack, or LIFO queue, with a FIFO queue in the DFS algorithm and make a few minor tweaks, then you’ll get the breadth-first search [BFS] algorithm almost for free. You’ll explore both algorithms in more detail later in this tutorial

While a stack is a specialization of a queue, the deque or double-ended queue is a generalization that you can use as a basis to implement both FIFO and LIFO queues. You’ll see how deques work and where you can use them in the next section

Deque. Hàng đợi hai đầu

A double-ended queue or deque [pronounced deck] is a more generic data type that combines and extends the ideas behind the stack and the queue. It allows you to enqueue or dequeue elements from both ends in constant time at any given moment. Therefore, a deque can work as a FIFO or a LIFO queue, as well as anything in between and beyond

Using the same example of a line of people as before, you can take advantage of a deque to model more sophisticated corner cases. In real life, the last person in the queue might get impatient and decide to leave the queue early or join another queue at a new checkout that has just opened. Conversely, someone who has booked a visit online for a particular date and time in advance may be allowed to join the queue at the front without waiting

Below is an animation that shows an unbounded deque in action

In this particular example, most elements generally follow one direction by joining the queue on the right and leaving it on the left, just like in a plain FIFO queue. However, some privileged elements are allowed to join the queue from the left end, while the last element can leave the queue through the opposite end

Adding an element to a bounded deque that has already reached its full capacity will overwrite the element currently located at the opposite end. That feature might be handy for isolating the first few or the last few elements from a sequence. You may also want to stop anywhere in that sequence and then move to the left or right in smaller steps

Suppose you were calculating the moving average of pixel intensities in a scan line of a raster image. Moving left or right would give you a preview of the few consecutive pixel values and dynamically calculate their average. This is more or less how convolution kernels work for applying filters in advanced image processing

Most deques support two additional operations called rotate left and rotate right, which shift the elements a specified number of places in one or the other direction in a circular fashion. Because the deque’s size remains unchanged, elements that would stick out get wrapped around at the ends, as in an analog car odometer

When rotated right, the last element in the deque becomes first. On the other hand, when rotated left, the first element becomes the last one. Perhaps you could imagine this process more easily by arranging the deque’s elements in a circle so that both ends meet. Then, rotating right and left would correspond to a clockwise and counterclockwise rotation, respectively

Rotations, combined with the deque’s core capabilities, open up interesting possibilities. For example, you could use a deque to implement a load balancer or a task scheduler working in a round-robin fashion. In a GUI application, you could use a deque to store recently opened files, allow a user to undo and redo their actions, or let the user navigate back and forth through their web browsing history

As you can see, deques find many practical uses, especially in tracking the most recent activity. However, some problems will require you to take advantage of yet another type of queue, which you’ll read about next

Priority Queue. Sorted From High to Low

A priority queue is different from those you’ve seen so far because it can’t store ordinary elements. Instead, each element must now have an associated priority to compare against other elements. The queue will maintain a sorted order, letting new elements join where necessary while shuffling the existing elements around if needed. When two elements are of equal priority, they’ll follow their insertion order

Note. Make sure to choose a data type for your priorities whose values are comparable through the comparison operators, such as less than [

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

This kind of queue works in a way that’s analogous to priority boarding on a plane

Regular passengers will join the queue at the very end unless they’re accompanied by small children, have disabilities, or have earned loyalty points, in which case they’ll be fast-tracked to the front of the line. Business-class travelers usually enjoy the luxury of a separate, much smaller queue, but even they sometimes have to let the first-class travelers pass

The animation below illustrates a sample flow of elements having three distinct priorities through an unbounded priority queue

Blue squares represent the lowest priority, yellow triangles are higher in the hierarchy, and red circles are the most important. A new element gets inserted between one with a higher or equal priority and another one with a lower priority. This rule resembles the insertion sort algorithm, which happens to be stable, as elements with the same priority never swap their initial places

You could use the priority queue to sort a sequence of elements by a given key or get the top few elements. However, that would be overkill because there are far more efficient sorting algorithms available. Hàng đợi ưu tiên phù hợp hơn với các tình huống khi các phần tử có thể đến và đi một cách linh hoạt. One such situation would be searching for the shortest path in a weighted graph using Dijkstra’s algorithm, which you’ll read about later

Ghi chú. Even though the priority queue is conceptually a sequence, its most efficient implementation builds on top of the heap data structure, which is a kind of binary tree. Therefore, the terms heap and priority queue are sometimes used interchangeably

That was a longish introduction to the theory and taxonomy of queues. Trong quá trình thực hiện, bạn đã tìm hiểu về hàng đợi FIFO, ngăn xếp [hàng đợi LIFO], deques và hàng đợi ưu tiên. Bạn cũng đã thấy sự khác biệt giữa hàng đợi có giới hạn và không có giới hạn, đồng thời bạn đã có ý tưởng về các ứng dụng tiềm năng của chúng. Bây giờ, đã đến lúc bạn tự mình thực hiện một số hàng đợi đó

Biểu diễn hàng đợi FIFO và LIFO bằng Deque

Để thể hiện hàng đợi FIFO trong bộ nhớ của máy tính, bạn sẽ cần một chuỗi có O[1] hoặc thời gian không đổi, hiệu suất cho thao tác xếp hàng ở một đầu và thao tác xếp hàng hiệu quả tương tự ở đầu kia. Như bạn đã biết bây giờ, deque hoặc hàng đợi kết thúc kép đáp ứng các yêu cầu đó. Ngoài ra, nó cũng đủ phổ biến để thích ứng với hàng đợi LIFO

Tuy nhiên, vì viết mã sẽ nằm ngoài phạm vi của hướng dẫn này, nên bạn sẽ tận dụng bộ sưu tập

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Ghi chú. A deque is an abstract data type that you may implement in a few ways. Using a doubly linked list as the underlying implementation will ensure that accessing and removing elements from both ends will have the desired O[1] time complexity. If your deque has a fixed size, then you can use a circular buffer instead, letting you access any element in constant time. Unlike a linked list, a circular buffer is a random-access data structure

Why not use a Python

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Both sequences allow for enqueuing elements with their

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Unfortunately, dequeuing an element from the front of a list with

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

With that, you can proceed to define your custom

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Building a Queue Data Type

Now that you’ve chosen a suitable queue representation, you can fire up your favorite code editor, such as Visual Studio Code or PyCharm, and create a new Python module for the different queue implementations. You can call the file

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Note. You’ll have a closer look at the built-in

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Because you want your custom FIFO queue to support at least the enqueue and dequeue operations, go ahead and write a bare-bones

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

This class merely wraps a

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

You can test your FIFO queue by importing it from the local module within an interactive Python interpreter session

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

As expected, the enqueued elements come back to you in their original order. If you want, you may improve your class by making it iterable and able to report its length and optionally accept initial elements

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

A

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Note. The implementation of

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Restart the Python interpreter and import your class again to see the updated code in action

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

The queue has three elements initially, but its length drops to zero after consuming all elements in a loop. Next up, you’ll implement a stack data type that’ll dequeue elements in reverse order

Building a Stack Data Type

Building a stack data type is considerably more straightforward because you’ve already done the bulk of the hard work. Vì hầu hết việc triển khai sẽ không thay đổi, bạn có thể mở rộng lớp

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Đó là nó. Các phần tử hiện được bật ra từ cùng một đầu của hàng đợi mà bạn đã đẩy chúng qua trước đó. Bạn có thể nhanh chóng xác minh điều này trong phiên Python tương tác

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Với dữ liệu thử nghiệm và thiết lập giống hệt như trước đây, các phần tử sẽ trả về cho bạn theo thứ tự ngược lại, đây là hành vi dự kiến ​​của hàng đợi LIFO

Ghi chú. Trong hướng dẫn này, bạn sử dụng tính kế thừa như một cơ chế thuận tiện để sử dụng lại mã. Tuy nhiên, mối quan hệ lớp hiện tại không đúng về mặt ngữ nghĩa, bởi vì ngăn xếp không phải là kiểu con của hàng đợi. Bạn cũng có thể xác định ngăn xếp trước và để hàng đợi mở rộng nó. Trong thế giới thực, có lẽ bạn nên làm cho cả hai lớp kế thừa từ một lớp cơ sở trừu tượng vì chúng có chung giao diện

Trong các tập lệnh một lần, bạn có thể thoát khỏi việc sử dụng Python

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Danh sách Python có thể lặp lại ngay lập tức. Họ có thể báo cáo độ dài của họ và có một đại diện văn bản hợp lý. Trong phần tiếp theo, bạn sẽ chọn chúng làm nền tảng cho hàng đợi ưu tiên

Biểu diễn hàng đợi ưu tiên bằng một đống

Hàng đợi cuối cùng mà bạn sẽ triển khai trong hướng dẫn này sẽ là hàng đợi ưu tiên. Không giống như ngăn xếp, hàng đợi ưu tiên không thể mở rộng lớp

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Có nhiều cách để triển khai hàng đợi ưu tiên, chẳng hạn như

• Một danh sách các phần tử không có thứ tự và mức độ ưu tiên của chúng mà bạn luôn tìm kiếm trước khi loại bỏ phần tử có mức độ ưu tiên cao nhất
• Một danh sách các phần tử được sắp xếp theo thứ tự và mức độ ưu tiên của chúng, mà bạn sắp xếp mỗi khi liệt kê một phần tử mới
• Một danh sách các phần tử được sắp xếp theo thứ tự và mức độ ưu tiên của chúng mà bạn sắp xếp theo thứ tự bằng cách tìm đúng vị trí cho một phần tử mới bằng cách sử dụng tìm kiếm nhị phân
• A binary tree that maintains the heap invariant after the enqueue and dequeue operations

Bạn có thể coi hàng đợi ưu tiên là một danh sách cần được sắp xếp mỗi khi có một phần tử mới để bạn có thể xóa phần tử cuối cùng có mức độ ưu tiên cao nhất khi thực hiện thao tác dequeue. Ngoài ra, bạn có thể bỏ qua thứ tự phần tử cho đến khi loại bỏ phần tử có mức độ ưu tiên cao nhất mà bạn có thể tìm thấy bằng thuật toán tìm kiếm tuyến tính

Tra cứu một phần tử trong danh sách không có thứ tự có độ phức tạp thời gian O[n]. Sắp xếp toàn bộ hàng đợi sẽ còn tốn kém hơn, đặc biệt là khi thực hiện thường xuyên. Phương thức

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

May mắn thay, bạn có thể thông minh trong việc sắp xếp các phần tử trong hàng đợi ưu tiên bằng cách sử dụng cấu trúc dữ liệu heap dưới mui xe. Nó cung cấp một triển khai hiệu quả hơn so với những gì được liệt kê trước đó. Dưới đây là bảng so sánh nhanh về độ phức tạp của thời gian đối với các thao tác xếp hàng và xếp hàng được cung cấp bởi các cách triển khai khác nhau đó

Thực hiệnEnqueueDequeueTìm Tối đa trên DequeueO[1]O[n]Sắp xếp trên EnqueueO[n log[n]]O[1]Chia đôi và Chèn trên EnqueueO[n]O[1]Đẩy lên một đống trên EnqueueO[log[n]]O

Heap có hiệu suất tổng thể tốt nhất cho khối lượng dữ liệu lớn. Mặc dù sử dụng phương pháp chia đôi để tìm đúng vị trí cho một phần tử mới là O[log[n]], nhưng việc chèn phần tử đó thực sự là O[n], khiến nó ít được mong muốn hơn so với một đống

Python có mô-đun

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

1. >>> from queues import Queue
   
   >>> fifo = Queue[]
   >>> fifo.enqueue["1st"]
   >>> fifo.enqueue["2nd"]
   >>> fifo.enqueue["3rd"]
   
   >>> fifo.dequeue[]
   '1st'
   >>> fifo.dequeue[]
   '2nd'
   >>> fifo.dequeue[]
   '3rd'
   

   36

2. >>> from queues import Queue
   
   >>> fifo = Queue[]
   >>> fifo.enqueue["1st"]
   >>> fifo.enqueue["2nd"]
   >>> fifo.enqueue["3rd"]
   
   >>> fifo.dequeue[]
   '1st'
   >>> fifo.dequeue[]
   '2nd'
   >>> fifo.dequeue[]
   '3rd'
   

   37

Khi bạn đẩy một phần tử mới vào một đống không trống, nó sẽ kết thúc ở đúng vị trí, duy trì sự bất biến của đống. Lưu ý rằng điều này không nhất thiết có nghĩa là các phần tử kết quả sẽ được sắp xếp

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Tên trái cây trong đống kết quả trong ví dụ trên không theo thứ tự bảng chữ cái. Tuy nhiên, nếu bạn đẩy chúng theo một thứ tự khác, chúng có thể

Điểm quan trọng của một đống không phải là sắp xếp các phần tử mà là giữ chúng trong một mối quan hệ nhất định để cho phép tra cứu nhanh. Điều thực sự quan trọng là phần tử đầu tiên trên heap luôn có giá trị nhỏ nhất [min-heap] hoặc cao nhất [max-heap], tùy thuộc vào cách bạn xác định điều kiện cho mối quan hệ được đề cập. Heap của Python là min-heap, nghĩa là phần tử đầu tiên có giá trị nhỏ nhất

Khi bạn bật một phần tử từ một đống, bạn sẽ luôn nhận được phần tử đầu tiên, trong khi các phần tử còn lại có thể xáo trộn một chút

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Chú ý đổi chỗ cho quả chuối và quả cam để đảm bảo phần tử đầu tiên tiếp tục nhỏ nhất. Khi bạn yêu cầu Python so sánh hai đối tượng chuỗi theo giá trị, nó bắt đầu xem xét từng cặp ký tự của chúng từ trái sang phải và kiểm tra từng cặp một. Ký tự có điểm mã Unicode thấp hơn được coi là nhỏ hơn, giải quyết trật tự từ

Bây giờ, bạn sắp xếp các ưu tiên như thế nào? . Để giải quyết vấn đề này, bạn có thể tận dụng phép so sánh bộ của Python, tính năng này sẽ tính đến các thành phần của bộ, nhìn từ trái sang phải cho đến khi biết kết quả

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Ở đây, bạn có ba bộ đại diện cho những người khác nhau. Mỗi người đều có tên, họ và tuổi. Python xác định rằng

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bạn có thể thực thi thứ tự ưu tiên trên heap bằng cách lưu trữ các bộ dữ liệu có phần tử đầu tiên là ưu tiên. Tuy nhiên, sẽ có một vài chi tiết nhỏ mà bạn cần phải cẩn thận. Bạn sẽ tìm hiểu thêm về chúng trong phần tiếp theo

Xây dựng loại dữ liệu hàng đợi ưu tiên

Hãy tưởng tượng bạn đang xây dựng phần mềm cho một công ty ô tô. Các phương tiện hiện đại thực tế là các máy tính trên bánh xe, sử dụng xe buýt mạng khu vực điều khiển [CAN] để phát thông báo về các sự kiện khác nhau đang diễn ra trong ô tô của bạn, chẳng hạn như mở khóa cửa hoặc bung túi khí. Rõ ràng, một số sự kiện đó quan trọng hơn những sự kiện khác và cần được ưu tiên phù hợp

Sự thật thú vị. Bạn có thể tải xuống ứng dụng di động cho điện thoại thông minh của mình, chẳng hạn như Torque, ứng dụng này sẽ cho phép bạn kết nối với bus CAN của ô tô qua Bluetooth hoặc mạng WiFi đặc biệt thông qua một thiết bị quét nhỏ được kết nối với thiết bị chẩn đoán trên ô tô của bạn [

Thiết lập này sẽ cho phép bạn theo dõi các thông số của xe theo thời gian thực, ngay cả khi chúng không hiển thị trên bảng điều khiển. Điều này bao gồm những thứ như nhiệt độ nước làm mát, điện áp pin, dặm mỗi gallon, và lượng khí thải. Hơn nữa, bạn sẽ có thể kiểm tra xem ECU trên ô tô của mình có báo cáo bất kỳ mã lỗi nào không

Bạn có thể bỏ lỡ thông báo đèn pha bị lỗi hoặc đợi thêm một thời gian nữa để mức âm lượng giảm xuống. Tuy nhiên, khi bạn nhấn bàn đạp phanh, bạn sẽ mong đợi nó có tác dụng ngay lập tức vì đây là một hệ thống con quan trọng về an toàn. Each message has a priority in the CAN bus protocol, which tells the intermediate units whether they should relay the message further or disregard it completely

Mặc dù đây là một sự đơn giản hóa quá mức của vấn đề, nhưng bạn có thể coi bus CAN như một hàng đợi ưu tiên sắp xếp các thư theo mức độ quan trọng của chúng. Bây giờ, hãy quay lại trình chỉnh sửa mã của bạn và xác định lớp sau trong mô-đun Python mà bạn đã tạo trước đó

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Đó là một triển khai hàng đợi ưu tiên cơ bản, định nghĩa một đống phần tử bằng cách sử dụng danh sách Python và hai phương thức thao tác nó. Phương thức

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Thật không may, có một số vấn đề với việc triển khai ở trên trở nên rõ ràng khi bạn cố gắng sử dụng nó

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bạn đã xác định ba mức độ ưu tiên. quan trọng, quan trọng và trung lập. Tiếp theo, bạn đã khởi tạo một hàng đợi ưu tiên và sử dụng nó để liệt kê một vài thư với những ưu tiên đó. Tuy nhiên, thay vì xếp hàng tin nhắn có mức độ ưu tiên cao nhất, bạn có một bộ dữ liệu tương ứng với tin nhắn có mức độ ưu tiên thấp nhất

Ghi chú. Cuối cùng, tùy thuộc vào cách bạn muốn xác định thứ tự ưu tiên của mình. Trong hướng dẫn này, mức ưu tiên thấp hơn tương ứng với giá trị số thấp hơn, trong khi mức ưu tiên cao hơn có giá trị lớn hơn

Điều đó nói rằng, có thể thuận tiện hơn để đảo ngược thứ tự này trong một số trường hợp. Ví dụ: trong thuật toán đường đi ngắn nhất của Dijkstra, bạn sẽ muốn ưu tiên các đường dẫn có tổng chi phí nhỏ hơn so với những đường dẫn có chi phí cao. Để xử lý tình huống như vậy, bạn sẽ triển khai một lớp khác sau

Vì heap của Python là min-heap nên phần tử đầu tiên của nó luôn có giá trị thấp nhất. Để khắc phục điều này, bạn có thể lật dấu hiệu của mức độ ưu tiên khi đẩy một bộ vào heap, đặt mức độ ưu tiên thành một số âm để mức cao nhất trở thành mức thấp nhất

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Với thay đổi nhỏ này, bạn sẽ đẩy các thông báo quan trọng lên trước các thông báo quan trọng và trung lập. Ngoài ra, khi thực hiện thao tác dequeue, bạn sẽ giải nén giá trị khỏi bộ dữ liệu bằng cách truy cập thành phần thứ hai của nó, nằm ở chỉ mục một bằng cách sử dụng cú pháp dấu ngoặc vuông [

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bây giờ, nếu bạn quay lại trình thông dịch Python tương tác của mình, hãy nhập mã đã cập nhật và liệt kê lại các thông báo tương tự một lần nữa, sau đó chúng sẽ quay lại với bạn theo thứ tự hợp lý hơn

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bạn nhận được thông báo quan trọng đầu tiên, tiếp theo là hai thông báo quan trọng và sau đó là thông báo trung lập. Cho đến nay, rất tốt, phải không? . Một trong số chúng bạn đã có thể nhìn thấy ở đầu ra, trong khi cái còn lại sẽ chỉ xuất hiện trong những trường hợp cụ thể. Bạn có thể phát hiện ra những vấn đề này?

Xử lý các trường hợp góc trong hàng đợi ưu tiên của bạn

Hàng đợi của bạn có thể sắp xếp chính xác các phần tử theo mức độ ưu tiên, nhưng đồng thời, nó vi phạm tính ổn định của sắp xếp khi so sánh các phần tử có mức độ ưu tiên như nhau. Điều này có nghĩa là trong ví dụ trên, nhấp nháy đèn báo nguy hiểm được ưu tiên hơn là bật cần gạt nước, mặc dù thứ tự này không tuân theo trình tự thời gian của các sự kiện. Cả hai tin nhắn đều có cùng mức độ ưu tiên, quan trọng, vì vậy hàng đợi sẽ sắp xếp chúng theo thứ tự chèn của chúng

To be clear, this is a direct consequence of tuple comparison in Python, which moves to the next component in a tuple if the earlier ones didn’t resolve the comparison. Vì vậy, nếu hai thông báo có mức độ ưu tiên như nhau, thì Python sẽ so sánh chúng theo giá trị, đó sẽ là một chuỗi trong ví dụ của bạn. Các chuỗi tuân theo thứ tự từ điển, trong đó từ Hazard xuất hiện trước từ Windshield, do đó thứ tự không nhất quán

Có một vấn đề khác liên quan đến điều đó, điều này sẽ phá vỡ hoàn toàn so sánh bộ dữ liệu trong một số trường hợp hiếm hoi. Cụ thể, sẽ không thành công nếu bạn cố gắng xếp một phần tử không hỗ trợ bất kỳ toán tử so sánh nào, chẳng hạn như một thể hiện của lớp tùy chỉnh và hàng đợi đã chứa ít nhất một phần tử có cùng mức độ ưu tiên mà bạn muốn sử dụng. Hãy xem xét lớp dữ liệu sau đây để biểu thị các thư trong hàng đợi của bạn

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Các đối tượng

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Miễn là bạn liệt kê các thư có mức độ ưu tiên khác nhau, Python sẽ không so sánh chúng theo giá trị

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Ví dụ: khi bạn liệt kê một thông báo quan trọng và một thông báo quan trọng, Python sẽ xác định thứ tự của chúng một cách rõ ràng bằng cách xem xét các mức độ ưu tiên tương ứng. Tuy nhiên, ngay khi bạn thử xử lý một thư quan trọng khác, bạn sẽ gặp lỗi quen thuộc

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Khoảng thời gian này, việc so sánh không thành công vì hai trong số các thông báo có mức độ ưu tiên như nhau và Python quay lại so sánh chúng theo giá trị mà bạn chưa xác định cho các phiên bản lớp

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bạn có thể giải quyết cả hai vấn đề—tức là, tính không ổn định của sắp xếp và so sánh bộ dữ liệu bị hỏng—bằng cách đưa một thành phần khác vào các phần tử được lưu trữ trên heap. Thành phần bổ sung này phải có thể so sánh được và biểu thị thời gian đến. Khi được đặt giữa mức độ ưu tiên và giá trị của phần tử trong một bộ, nó sẽ giải quyết thứ tự nếu hai phần tử có cùng mức độ ưu tiên, bất kể giá trị của chúng là gì

Cách đơn giản nhất để biểu thị thời gian đến trong hàng đợi ưu tiên có lẽ là một bộ đếm đơn điệu tăng dần. Nói cách khác, bạn muốn đếm số thao tác xếp hàng được thực hiện mà không cần xem xét các thao tác xếp hàng tiềm năng có thể đang diễn ra. Sau đó, bạn sẽ lưu trữ giá trị hiện tại của bộ đếm trong mọi phần tử được xếp hàng để phản ánh trạng thái hàng đợi của bạn ngay lúc đó

Bạn có thể sử dụng trình vòng lặp

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bộ đếm được khởi tạo khi bạn tạo một phiên bản

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Chi tiết nhỏ cuối cùng cần ghi nhớ sau khi đưa thành phần bộ đếm bổ sung này vào bộ dữ liệu là cập nhật chỉ mục giá trị được bật lên trong hoạt động dequeue. Bởi vì các phần tử bây giờ là các bộ có ba thành phần, bạn phải trả về giá trị nằm ở chỉ mục hai thay vì một. Tuy nhiên, sẽ an toàn hơn nếu sử dụng giá trị âm làm chỉ mục để chỉ ra thành phần cuối cùng của bộ dữ liệu, bất kể độ dài của nó

Hàng đợi ưu tiên của bạn gần như đã sẵn sàng, nhưng nó thiếu hai phương thức đặc biệt,

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Tái cấu trúc mã bằng lớp Mixin

Để sử dụng lại mã trên các lớp không liên quan, bạn có thể xác định mẫu số chung nhỏ nhất của chúng và sau đó trích xuất mã đó vào một lớp mixin. Một lớp mixin giống như một loại gia vị. Nó không thể tự đứng vững, vì vậy bạn thường không khởi tạo nó, nhưng nó có thể bổ sung thêm hương vị đó khi bạn trộn nó vào một lớp khác. Đây là cách nó sẽ hoạt động trong thực tế

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bạn đã di chuyển các phương thức

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Không giống như các ngôn ngữ lập trình như Scala hỗ trợ mixin trực tiếp với các đặc điểm, Python sử dụng nhiều kế thừa để triển khai cùng một khái niệm. Tuy nhiên, việc mở rộng một lớp mixin khác về mặt ngữ nghĩa so với việc mở rộng một lớp thông thường, đây không còn là một dạng chuyên môn hóa kiểu. Để nhấn mạnh sự khác biệt này, một số người gọi nó là sự bao gồm của một lớp mixin hơn là kế thừa thuần túy

Lưu ý rằng lớp mixin của bạn đề cập đến thuộc tính

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Mở rộng phần có thể thu gọn bên dưới để hiển thị mã nguồn hoàn chỉnh

Mã nguồn hoàn chỉnh cho hàng đợiHiển thị/Ẩn

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Với ba lớp xếp hàng tại chỗ, cuối cùng bạn cũng có thể áp dụng chúng để giải một bài toán thực tế

Dữ liệu mẫu. Bản đồ đường đi của Vương quốc Anh

Khi bạn đã cài đặt các thư viện cần thiết, bạn sẽ đọc biểu đồ có trọng số và vô hướng của các thành phố ở Vương quốc Anh từ tệp DOT, bạn có thể tìm thấy tệp này trong các tài liệu đi kèm

Get Source Code. Click here to get access to the source code and sample data that you’ll use to explore queues in Python

Biểu đồ này có 70 nút đại diện cho các thành phố của Vương quốc Anh và 137 cạnh có trọng số theo khoảng cách ước tính tính bằng dặm giữa các thành phố được kết nối

Lưu ý rằng biểu đồ được mô tả ở trên là một mô hình đơn giản hóa của mạng lưới đường bộ ở Vương quốc Anh, vì nó không tính đến các loại đường, sức chứa, giới hạn tốc độ, giao thông hoặc đường tránh. Nó cũng bỏ qua thực tế là thường có nhiều hơn một con đường nối hai thành phố. Vì vậy, đường đi ngắn nhất được xác định bằng điều hướng vệ tinh hoặc Google Maps rất có thể sẽ khác với đường đi mà bạn sẽ tìm thấy khi xếp hàng trong hướng dẫn này

Điều đó nói rằng, biểu đồ trên biểu thị các kết nối đường thực tế giữa các thành phố trái ngược với các đường thẳng theo đường chim bay. Mặc dù các cạnh có thể trông giống như các đường thẳng trong hình ảnh trực quan, nhưng chúng chắc chắn không có trong đời thực. Về mặt đồ họa, bạn có thể biểu diễn cùng một biểu đồ theo vô số cách

Tiếp theo, bạn sẽ sử dụng thư viện networkx để đọc biểu đồ này bằng Python

Đại diện đối tượng của các thành phố và đường

Mặc dù networkx không thể tự đọc các tệp DOT, nhưng thư viện cung cấp một số chức năng trợ giúp ủy quyền nhiệm vụ này cho các thư viện bên thứ ba khác. Bạn sẽ sử dụng pygraphviz để đọc tệp DOT mẫu trong hướng dẫn này

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Mặc dù pygraphviz có thể hơi khó cài đặt trên một số hệ điều hành, nhưng cho đến nay, đây là cách nhanh nhất và phù hợp nhất với các tính năng nâng cao của định dạng DOT. Theo mặc định, networkx đại diện cho các nút biểu đồ bằng cách sử dụng các mã định danh văn bản có thể tùy chọn có một từ điển các thuộc tính được liên kết

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Ví dụ: chuỗi

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Vì đó không phải là cách thuận tiện nhất để suy nghĩ về biểu đồ, nên bạn sẽ xác định loại dữ liệu tùy chỉnh đại diện cho một thành phố trong bản đồ chỉ đường của mình. Hãy tiếp tục, tạo một tệp mới có tên là

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bạn mở rộng một bộ được đặt tên để đảm bảo rằng các đối tượng nút của bạn có thể băm được, điều này được yêu cầu bởi networkx. Thay vào đó, bạn có thể sử dụng một lớp dữ liệu được định cấu hình đúng, nhưng một bộ dữ liệu được đặt tên có thể được băm ngay lập tức. Nó cũng có thể so sánh được mà sau này bạn có thể cần để xác định thứ tự duyệt đồ thị. Phương thức lớp

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Để tận dụng lớp mới của mình, bạn sẽ cần tạo một thể hiện đồ thị mới và lưu ý ánh xạ của các định danh nút tới các thể hiện thành phố. Thêm chức năng trợ giúp sau vào mô-đun

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Hàm lấy tên tệp và nhà máy có thể gọi được cho các đối tượng nút, chẳng hạn như phương thức lớp

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Giờ đây, bạn có thể bắt đầu chơi lại với bản đồ đường đi của Vương quốc Anh trong phiên phiên dịch Python tương tác

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Sau khi nhập hàm trợ giúp và lớp

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Khi tìm kiếm con đường ngắn nhất giữa hai thành phố, bạn sẽ muốn xác định các lân cận ngay lập tức của một thành phố nhất định để tìm các tuyến đường có sẵn để đi theo. Bạn có thể làm điều đó theo một số cách với biểu đồ networkx. Trong trường hợp đơn giản nhất, bạn sẽ gọi phương thức

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Điều này chỉ hiển thị các nút lân cận mà không có trọng số có thể có của các cạnh kết nối, chẳng hạn như khoảng cách hoặc thời gian di chuyển ước tính mà bạn có thể cần biết để chọn đường đi tốt nhất. Nếu bạn muốn bao gồm các trọng số, hãy truy cập một nút bằng cú pháp dấu ngoặc vuông

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Các hàng xóm luôn được liệt kê theo cùng thứ tự mà bạn đã xác định chúng trong tệp DOT. Để sắp xếp chúng theo một hoặc nhiều trọng số, bạn có thể sử dụng đoạn mã sau

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Đầu tiên, bạn xác định một hàm trợ giúp trả về danh sách các hàng xóm và trọng số của chúng được sắp xếp theo chiến lược đã chỉ định. Chiến lược lấy một từ điển gồm tất cả các trọng số được liên kết với một cạnh và trả về một khóa sắp xếp. Tiếp theo, bạn xác định một chiến lược cụ thể tạo ra khoảng cách dấu phẩy động dựa trên từ điển đầu vào. Cuối cùng, bạn duyệt qua các vùng lân cận của Luân Đôn, được sắp xếp theo khoảng cách theo thứ tự tăng dần

Với kiến ​​thức cơ bản về thư viện networkx này, giờ đây bạn có thể chuyển sang triển khai thuật toán duyệt đồ thị dựa trên các loại dữ liệu hàng đợi tùy chỉnh mà bạn đã tạo trước đó

Tìm kiếm theo chiều rộng đầu tiên bằng cách sử dụng hàng đợi FIFO

Trong thuật toán tìm kiếm theo chiều rộng, bạn tìm kiếm một nút thỏa mãn một điều kiện cụ thể bằng cách khám phá biểu đồ theo các lớp hoặc cấp độ đồng tâm. Bạn bắt đầu duyệt đồ thị tại nút nguồn được chọn tùy ý trừ khi đồ thị là cấu trúc dữ liệu cây, trong trường hợp đó bạn thường bắt đầu tại nút gốc của cây đó. Ở mỗi bước, bạn truy cập tất cả các hàng xóm trực tiếp của nút hiện tại trước khi đi sâu hơn

Ghi chú. Để tránh bị mắc kẹt trong một vòng lặp khi biểu đồ chứa các chu kỳ, hãy theo dõi những người hàng xóm mà bạn đã truy cập và bỏ qua họ trong lần tiếp theo bạn gặp họ. Ví dụ: bạn có thể thêm các nút đã truy cập vào một tập hợp Python và sau đó sử dụng toán tử

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Ví dụ: giả sử bạn muốn tìm bất kỳ địa điểm nào ở Vương quốc Anh đã được công nhận là thành phố trong thế kỷ XX, bắt đầu tìm kiếm của bạn ở Edinburgh. Thư viện networkx đã triển khai nhiều thuật toán, bao gồm tìm kiếm theo chiều rộng, có thể giúp kiểm tra chéo việc triển khai trong tương lai của bạn. Gọi hàm

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Các dòng được đánh dấu cho biết tất cả sáu hàng xóm trực tiếp của Edinburgh, là nút nguồn của bạn. Lưu ý rằng chúng được truy cập theo trình tự mà không bị gián đoạn trước khi chuyển sang lớp tiếp theo của biểu đồ. Lớp tiếp theo bao gồm các nút lân cận cấp hai bắt đầu từ nút nguồn

Bạn khám phá những người hàng xóm chưa được ghé thăm của các thành phố nổi bật. Cái đầu tiên là Dundee, có hàng xóm bao gồm Aberdeen và Perth, nhưng bạn đã đến thăm Perth rồi, vì vậy bạn bỏ qua nó và chỉ ghé thăm Aberdeen. Glasgow không có bất kỳ hàng xóm nào không được thăm viếng, trong khi Perth chỉ có Inverness. Tương tự, bạn đã đến thăm những người hàng xóm của Stirling nhưng không phải của Carlisle, nơi kết nối với Lancaster. Bạn ngừng tìm kiếm vì Lancaster là câu trả lời của bạn

Kết quả tìm kiếm của bạn đôi khi có thể khác nhau tùy thuộc vào lựa chọn điểm xuất phát của bạn, cũng như thứ tự của các lân cận nếu có nhiều hơn một nút thỏa mãn một điều kiện. Để đảm bảo kết quả nhất quán, bạn có thể sắp xếp các hàng xóm theo một số tiêu chí. Ví dụ: trước tiên bạn có thể đến thăm các thành phố có vĩ độ cao hơn

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bây giờ, câu trả lời đã khác vì Newcastle được viếng thăm trước Carlisle do có vĩ độ cao hơn một chút. Đổi lại, điều này làm cho thuật toán tìm kiếm theo chiều rộng tìm thấy Sunderland trước Lancaster, đây là một nút thay thế phù hợp với điều kiện của bạn

Ghi chú. Trong trường hợp bạn đang thắc mắc tại sao

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bây giờ bạn đã nắm được ý tưởng chung về thuật toán tìm kiếm theo chiều rộng, đã đến lúc tự triển khai nó. Vì phép duyệt theo chiều rộng là cơ sở cho các thuật toán thú vị khác, nên bạn sẽ trích xuất logic của nó thành một hàm riêng biệt mà bạn có thể ủy quyền cho

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Hàm đầu tiên lấy biểu đồ networkx và nút nguồn làm đối số trong khi mang lại các nút được truy cập với giao dịch truyền tải theo chiều rộng đầu tiên. Lưu ý rằng nó sử dụng hàng đợi FIFO của bạn từ mô-đun

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Ghi chú. Thay vì sử dụng vòng lặp

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Tuy nhiên, điều này phụ thuộc vào chi tiết triển khai không rõ ràng trong lớp

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Hàm thứ hai được xây dựng trên đỉnh của hàm thứ nhất bằng cách lặp qua các nút đã tạo và dừng khi nút hiện tại đáp ứng các tiêu chí dự kiến. Nếu không có nút nào làm cho vị từ trung thực, thì hàm sẽ trả về ngầm định

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Để kiểm tra hoạt động triển khai tìm kiếm và duyệt theo chiều rộng đầu tiên của bạn, bạn có thể thay thế chức năng tiện lợi được tích hợp trong networkx bằng chức năng của riêng bạn

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Như bạn có thể thấy, thứ tự truyền tải giống hệt với lần thử đầu tiên của bạn với networkx, xác nhận rằng thuật toán của bạn hoạt động chính xác cho tập dữ liệu này. Tuy nhiên, chức năng của bạn không cho phép sắp xếp hàng xóm theo thứ tự cụ thể. Hãy thử sửa đổi mã để nó chấp nhận chiến lược sắp xếp tùy chọn. Bạn có thể nhấp vào phần có thể thu gọn bên dưới để xem một giải pháp khả thi

Giải pháp. Sắp xếp hàng xómHiển thị/Ẩn

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Thuật toán tìm kiếm theo chiều rộng đảm bảo rằng cuối cùng bạn sẽ khám phá tất cả các nút được kết nối trong biểu đồ trong khi tìm kiếm nút thỏa mãn điều kiện mong muốn. Bạn có thể sử dụng nó để giải quyết một mê cung chẳng hạn. Phép duyệt theo chiều rộng cũng là cơ sở để tìm đường đi ngắn nhất giữa hai nút trong đồ thị vô hướng và không trọng số. Trong phần tiếp theo, bạn sẽ điều chỉnh mã của mình để làm việc đó

Đường dẫn ngắn nhất sử dụng tính năng truyền tải theo chiều rộng đầu tiên

Trong nhiều trường hợp, càng ít nút trên đường đi từ nguồn đến đích thì khoảng cách càng ngắn. Bạn có thể tận dụng quan sát này để ước tính khoảng cách ngắn nhất nếu các kết nối giữa các thành phố của bạn không có trọng số. Điều đó sẽ tương đương với việc có trọng lượng bằng nhau trên mọi cạnh

Duyệt qua biểu đồ bằng cách sử dụng phương pháp tiếp cận theo chiều rộng sẽ tạo ra một đường dẫn được đảm bảo có ít nút nhất. Đôi khi có thể có nhiều hơn một đường đi ngắn nhất giữa hai nút. Ví dụ: có hai con đường ngắn nhất như vậy giữa Aberdeen và Perth khi bạn bỏ qua khoảng cách đường. Như trước đây, kết quả thực tế trong trường hợp này sẽ phụ thuộc vào cách bạn sắp xếp thứ tự các nút lân cận

Bạn có thể sử dụng networkx để hiển thị tất cả các con đường ngắn nhất giữa hai thành phố, sẽ có cùng độ dài tối thiểu

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Sau khi tải biểu đồ, bạn liệt kê các con đường ngắn nhất giữa hai thành phố và in chúng lên màn hình. Bạn có thể thấy chỉ có hai con đường ngắn nhất giữa Aberdeen và Perth. Ngược lại, London và Edinburgh có bốn đường đi ngắn nhất riêng biệt với chín nút mỗi đường, nhưng giữa chúng tồn tại nhiều đường đi dài hơn

Làm thế nào để duyệt theo chiều rộng đầu tiên giúp bạn tìm ra con đường ngắn nhất một cách chính xác?

Bất cứ khi nào bạn truy cập một nút, bạn phải theo dõi nút trước đó đã dẫn bạn đến nút đó bằng cách lưu thông tin này dưới dạng cặp khóa-giá trị trong từ điển. Later, you’ll be able to trace back your way from the destination to the source by following the previous nodes. Quay lại trình chỉnh sửa mã của bạn và tạo một hàm khác bằng cách sao chép và điều chỉnh mã từ hàm

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Hàm mới này lấy một nút khác làm đối số và tùy chọn cho phép bạn sắp xếp các nút lân cận bằng cách sử dụng chiến lược tùy chỉnh. Nó cũng xác định một từ điển trống mà bạn điền vào khi truy cập một hàng xóm bằng cách liên kết nó với nút trước đó trên đường dẫn của bạn. Tất cả các cặp khóa-giá trị trong từ điển này là hàng xóm ngay lập tức mà không có bất kỳ nút nào giữa chúng

Nếu một đường dẫn tồn tại giữa nguồn và đích của bạn, thì hàm này sẽ trả về một danh sách các nút được tạo bằng một hàm trợ giúp khác thay vì trả về các nút riêng lẻ như

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Ghi chú. Bạn có thể thử cấu trúc lại mã này bằng cách kết hợp

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Để tạo lại đường đi ngắn nhất giữa nguồn và đích, bạn có thể lặp lại tra cứu từ điển được tạo trước đó khi duyệt qua biểu đồ bằng cách tiếp cận theo chiều rộng

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bởi vì bạn bắt đầu từ điểm đến và quay trở lại, nên việc sử dụng bộ sưu tập Python

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Khi bạn gọi triển khai đường đi ngắn nhất dựa trên hàng đợi, bạn sẽ nhận được kết quả tương tự như với networkx

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Đường dẫn đầu tiên tuân theo thứ tự tự nhiên của các hàng xóm từ tệp DOT, trong khi đường dẫn thứ hai ưu tiên các hàng xóm có vĩ độ cao hơn mà bạn chỉ định thông qua chiến lược sắp xếp tùy chỉnh. Để thực thi thứ tự giảm dần, bạn thêm dấu trừ [______095] trước thuộc tính

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Lưu ý rằng một đường dẫn có thể không tồn tại đối với một số nút. Ví dụ: Belfast và Glasgow không có kết nối đất liền vì chúng nằm trên hai hòn đảo riêng biệt. Bạn cần đi phà để đi từ thành phố này sang thành phố khác. Giao dịch theo chiều rộng đầu tiên có thể cho bạn biết liệu hai nút có còn được kết nối hay không. Đây là cách thực hiện kiểm tra như vậy

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Sau khi bắt đầu tại nút nguồn và duyệt qua toàn bộ biểu đồ con của các nút được kết nối, chẳng hạn như Bắc Ireland, từ điển của các nút trước đó sẽ không bao gồm nút đích của bạn. Do đó, quá trình quay lại sẽ dừng ngay lập tức và trả về

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bạn có thể xác minh điều này trong phiên phiên dịch Python tương tác

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Đáng kinh ngạc. Với hàng đợi FIFO tùy chỉnh của bạn, bạn có thể duyệt qua biểu đồ, tìm đường đi ngắn nhất giữa hai nút và thậm chí xác định xem chúng có được kết nối hay không. Bằng cách thêm một tinh chỉnh nhỏ vào mã của bạn, bạn sẽ có thể thay đổi thứ tự truyền tải từ thứ tự theo chiều rộng sang thứ tự theo chiều sâu, điều mà bạn sẽ thực hiện ngay bây giờ

Tìm kiếm theo chiều sâu bằng hàng đợi LIFO

Đúng như tên gọi, đường duyệt theo chiều sâu đi theo một đường dẫn từ nút nguồn bằng cách đi sâu vào biểu đồ càng sâu càng tốt trước khi quay lại đường đi qua cạnh cuối cùng và thử một nhánh khác. Lưu ý sự khác biệt trong thứ tự truyền tải khi bạn sửa đổi một ví dụ trước đó bằng cách thay thế

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bây giờ, các nút lân cận được đánh dấu của nút nguồn không còn được khám phá theo trình tự. Sau khi đến Dundee, thuật toán tiếp tục đi theo cùng một con đường thay vì truy cập hàng xóm tiếp theo của Edinburgh trên lớp biểu đồ đầu tiên

Để tạo điều kiện quay lui, về cơ bản, bạn có thể thay thế hàng đợi FIFO bằng hàng đợi LIFO trong chức năng truyền tải theo chiều rộng trước và bạn sẽ tiến rất gần đến quá trình truyền tải theo chiều sâu. Tuy nhiên, nó sẽ chỉ hoạt động chính xác khi duyệt qua các cấu trúc dữ liệu dạng cây. Có một sự khác biệt nhỏ trong biểu đồ có chu kỳ, yêu cầu thay đổi bổ sung trong mã của bạn. Nếu không, bạn sẽ triển khai tính năng duyệt đồ thị dựa trên ngăn xếp, hoạt động hoàn toàn khác

Ghi chú. Trong duyệt cây nhị phân, thuật toán tìm kiếm theo chiều sâu xác định một vài thứ tự nổi tiếng cho các nút con truy cập—ví dụ: thứ tự trước, thứ tự sau và thứ tự sau

In the classic depth-first traversal, in addition to replacing the queue with a stack, you initially won’t mark the source node as visited

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Lưu ý rằng các nút đã truy cập của bạn được khởi tạo thành một tập hợp trống trước khi bạn bắt đầu lấy các phần tử ra khỏi ngăn xếp. Bạn cũng kiểm tra xem nút đã được truy cập sớm hơn nhiều so với khi bạn truy cập theo chiều rộng trước chưa. Khi lặp lại các hàng xóm, bạn đảo ngược thứ tự của chúng để giải thích cho sự đảo ngược của hàng đợi LIFO. Cuối cùng, bạn không đánh dấu những người hàng xóm là đã truy cập ngay sau khi đẩy họ vào ngăn xếp

Vì quá trình truyền tải theo chiều sâu dựa trên cấu trúc dữ liệu ngăn xếp, nên bạn có thể tận dụng ngăn xếp cuộc gọi tích hợp để lưu đường dẫn tìm kiếm hiện tại để quay lui sau này và viết lại hàm của bạn theo cách đệ quy

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Bằng cách đó, bạn tránh phải duy trì một ngăn xếp của riêng mình, vì Python đẩy từng lệnh gọi hàm vào một ngăn xếp ở hậu trường cho bạn. Nó bật lên khi hàm tương ứng trả về. Bạn chỉ cần theo dõi các nút đã truy cập. Another advantage of the recursive implementation is the fact that you don’t have to reverse the neighbors when iterating over them, and you don’t push already visited neighbors onto the stack

With the traversal function in place, you can now implement the depth-first search algorithm. Because both breadth-first and depth-first search algorithms look almost identical and only differ in the traversal order, you can refactor your code by delegating the common parts of both algorithms to a template function

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Now, your

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

>>>

>>> from queues import Queue

>>> fifo = Queue[]
>>> fifo.enqueue["1st"]
>>> fifo.enqueue["2nd"]
>>> fifo.enqueue["3rd"]

>>> fifo.dequeue[]
'1st'
>>> fifo.dequeue[]
'2nd'
>>> fifo.dequeue[]
'3rd'

Even though the search result happens to be the same as with your breadth-first search algorithm, you can clearly see that the order of traversal is now different and follows a linear path

You’ve seen how choosing between a FIFO and a LIFO queue can affect the underlying graph traversal algorithm. So far, you’ve only considered the number of intermediate nodes when looking for the shortest path between two cities. In the next section, you’ll take it one step further by leveraging a priority queue to find the most optimal route, which may sometimes contain more nodes

Dijkstra’s Algorithm Using a Priority Queue

According to the graph in the sample DOT file, the paths with the fewest nodes between London and Edinburgh have exactly nine stops and a total distance ranging from 451 to 574 miles. There are four such paths

451 miles460 miles465 miles574 milesCity of LondonCity of LondonCity of LondonCity of LondonCoventryPeterboroughPeterboroughBristolBirminghamLincolnNottinghamNewportStoke-on-TrentSheffieldSheffieldSt AsaphLiverpoolWakefieldWakefieldLiverpoolPrestonYorkYorkPrestonLancasterDurhamDurhamLancasterCarlisleNewcastle upon TyneNewcastle upon TyneCarlisleEdinburghEdinburghEdinburghEdinburgh

There’s a significant overlap between these paths, as they quickly merge at a few intersections before your destination. To some degree, they also overlap with the only path with the shortest distance between London and Edinburgh, equal to 436 miles, despite having two more stops

1. City of London
2. St Albans
3. Coventry
4. Birmingham
5. Stoke-on-Trent
6. Manchester
7. Salford
8. Preston
9. Lancaster
10. Carlisle
11. Edinburgh

Sometimes, it’s worthwhile to take a detour on your route to save time, fuel, or miles, even if it means going through more places along the way

When you throw edge weights into the mix, then interesting possibilities open up in front of you. For example, you can implement rudimentary artificial intelligence in a video game by assigning negative weights to edges that lead to a virtual enemy and positive weights that point you toward some reward. You may also represent moves in a game like the Rubik’s Cube as a decision tree to find the most optimal solution

Perhaps the most common use for traversing a weighted graph is when planning a route. A recipe to find the shortest path in a weighted graph, or a multigraph with many parallel connections, is Dijkstra’s algorithm, which builds on top of the breadth-first search algorithm. However, Dijkstra’s algorithm uses a special priority queue instead of the regular FIFO queue

Explaining Dijkstra’s shortest path algorithm is beyond the scope of this tutorial. However, in a nutshell, you can break it down into the following two steps

1. Build the shortest-path three from a fixed source node to every other node in the graph
2. Trace back the path from the destination to the source node in the same way as you did before with the plain shortest-path algorithm

The first part is about sweeping the weighted edges of every unvisited node in a greedy manner by checking whether they provide a cheaper connection from the source to one of the current neighbors. The total cost of a path from the source to the neighbor is the sum of the edge’s weight and the cumulative cost from the source to the currently visited node. Sometimes, a path consisting of more nodes will have a smaller total cost

Here’s a sample result of the first step of Dijkstra’s algorithm for the paths originating in Belfast

CityPreviousTotal CostArmaghLisburn41Belfast-0DerryBelfast71LisburnBelfast9NewryLisburn40

The first column in the table above indicates a destination city on the shortest path from the source. The second column shows the previous city on the shortest path from the source through which you’ll arrive at your destination. The last column contains information about the total distance to a city from the source

Belfast is the source city, so it has no previous node leading to it and a distance of zero. The source neighbors Derry and Lisburn, which you can reach from Belfast directly at the cost of their corresponding edges. To get to Armagh or Newry, going through Lisburn will give you the shortest total distance from Belfast

Now, if you want to find the shortest path between Belfast and Armagh, then start at your destination and follow the previous column. To reach Armagh, you must go through Lisburn, and to get to Lisburn, you must start in Belfast. That’s your shortest path in reverse order

You’ll only need to implement the first part of Dijkstra’s algorithm because you already have the second part, which is responsible for retracing the shortest path based on the previous nodes. However, to enqueue the unvisited nodes, you’ll have to use a mutable version of a min-heap so that you can update the element priorities as you discover cheaper connections. Expand the collapsible section below for the implementation of this new queue

Complete Code For the Mutable Min-HeapShow/Hide