stack queue deque priority_queue

这是关于数据结构的问题。栈（Stack）、队列（Queue）、双端队列（Deque）和优先队列（Priority Queue）是常见的数据结构。

栈（Stack）是一种后进先出（LIFO）的数据结构，类似于我们叠放书籍的方式。元素只能在栈顶进行插入和删除操作。

队列（Queue）是一种先进先出（FIFO）的数据结构，类似于排队购物的方式。元素可以在队列的一端插入，在另一端删除。

双端队列（Deque，即Double Ended Queue）是一种同时具有栈和队列特性的数据结构，它允许在两端进行插入和删除操作。

优先队列（Priority Queue）是一种按照元素优先级

相关问题

Given the adjacency matrix of a digraph G, and a pair of starting node s and destination node d, determine if the destination d is reachable from s. Implement the following function is_reachable(adj_matrix, s, d), where adj_matrix is the adjacency matrix with 1 denoting an arc exists, and 0 otherwise. The function return True if d is reachable from s, and False otherwise. Note: You can use any Python built-in package to implement stack/queue/priority queue if needed. For example: Test Result adj_matrix = [[0,1,1,0],[0,0,1,0],[1,0,0,0],[0,1,0,0]] print(is_reachable(adj_matrix, 0, 3)) print(is_reachable(adj_matrix, 3, 0)) False True

Here's one possible implementation of the is_reachable function using breadth-first search:

from collections import deque

def is_reachable(adj_matrix, s, d):
    n = len(adj_matrix)
    visited = [False] * n
    queue = deque([s])
    visited[s] = True
    
    while queue:
        node = queue.popleft()
        if node == d:
            return True
        for neighbor, arc in enumerate(adj_matrix[node]):
            if arc == 1 and not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
    
    return False

The function starts by initializing a list of visited nodes with False, and a queue with the starting node s. It then enters a loop where it repeatedly dequeues a node from the queue, and checks if it is equal to the destination node d. If it is, the function returns True, indicating that d is reachable from s. Otherwise, the function enqueues all unvisited neighbors of the dequeued node, and marks them as visited.

If the loop completes without finding the destination node, the function returns False, indicating that d is not reachable from s.

The time complexity of this implementation is O(n^2), where n is the number of nodes in the graph, since we may visit all nodes and arcs in the worst case. However, the actual time complexity may be lower depending on the structure of the graph and the position of s and d.

Consider a problem to find the shortest path from a given starting node s to any other nodes in the (undirected) graph. The length of a path in the graph is the number of edges included. Complete the function shortest_path(adj_list, s), which takes the adjacency list of the graph and a starting node as input, and returns a list containing the length of the shortest path from the starting node to all other nodes. Note: If there is no path from the starting node to a node, set the length of shortest path as float('inf'). You can use any Python built-in package to implement the stack/queue/priority queue if needed. Hint: Consider the three graph traversal strategies (DFS, BFS and PFS) discussed in the class. Which one is applicable in this problem? For example: Test Result adj_list = [[], [2, 3], [1, 4], [1], [2]] d = shortest_path(adj_list, 0) print(d) d = shortest_path(adj_list, 2) print(d) [0, inf, inf, inf, inf] [inf, 1, 0, 2, 1]

To find the shortest path from a given starting node s to any other nodes in the (undirected) graph, we can use Breadth-First Search (BFS) algorithm. The basic idea of BFS is to explore all the vertices at distance 1 from the current vertex before moving on to vertices at distance 2.

Here is the implementation of the shortest_path function using BFS algorithm:

from collections import deque

def shortest_path(adj_list, s):
    n = len(adj_list)
    visited = [False] * n
    distance = [float('inf')] * n
    distance[s] = 0
    queue = deque([s])
    
    while queue:
        u = queue.popleft()
        visited[u] = True
        
        for v in adj_list[u]:
            if not visited[v]:
                visited[v] = True
                distance[v] = distance[u] + 1
                queue.append(v)
    
    for i in range(n):
        if not visited[i]:
            distance[i] = float('inf')
    
    return distance

In the above code, we first initialize two lists: visited and distance. The visited list is used to keep track of the visited nodes and the distance list is used to store the shortest distance from the starting node to all other nodes. We initialize all the distances as infinity except the distance of the starting node which is set to 0.

We then use a deque (double-ended queue) to implement the BFS algorithm. We start by adding the starting node to the queue. Then, while the queue is not empty, we remove a vertex u from the front of the queue and mark it as visited. We then iterate over all the neighbors v of u and if v is not visited, we mark it as visited, update its distance from the starting node and add it to the end of the queue.

Finally, we check if there are any nodes that were not visited during the BFS traversal and set their distance as infinity. We then return the distance list.

Let's use the above code to solve the given example:

adj_list = [[], [2, 3], [1, 4], [1], [2]]
d = shortest_path(adj_list, 0)
print(d) # Output: [0, inf, inf, inf, inf]

d = shortest_path(adj_list, 2)
print(d) # Output: [inf, 1, 0, 2, 1]

In the first test case, the starting node is 0 and there are no edges connected to it. Hence, the distance to all other nodes is infinity.

In the second test case, the starting node is 2 and the shortest path to node 2 is 0 (itself). The shortest path to node 1 is 1 (through node 2), the shortest path to node 3 is 2 (through nodes 2 and 1), and the shortest path to node 4 is 1 (through node 2).