class QNode: def __init__(self, p, pre): self.vno = p self.pre = pre def Shortpath(G, u, v): visited = [0] * len(G.adjlist) res = [] qu = deque() qu.append(QNode(u, None)) visited[u] = 1 while len(qu) > 0: p = qu.popleft() if p.vno == v: q = p.pre while q != None: res.append(q.vno) q = q.pre res.reverse() return res for j in range(len(G.adjlist[p.vno])): w = G.adjlist[p.vno][j].adjvex if visited[w] == 0: qu.append(QNode(w, p)) visited[w] = 1 return None完善代码并写出主程序

这段代码实现了一个基于广度优先搜索的无权图最短路径算法。下面是完整的代码，并附上一个简单的测试程序。

from collections import deque

class QNode:
    def __init__(self, p, pre):
        self.vno = p
        self.pre = pre

def Shortpath(G, u, v):
    visited = [0] * len(G.adjlist)
    res = []
    qu = deque()
    qu.append(QNode(u, None))
    visited[u] = 1
    while len(qu) > 0:
        p = qu.popleft()
        if p.vno == v:
            q = p.pre
            while q != None:
                res.append(q.vno)
                q = q.pre
            res.reverse()
            return res
        for j in range(len(G.adjlist[p.vno])):
            w = G.adjlist[p.vno][j].adjvex
            if visited[w] == 0:
                qu.append(QNode(w, p))
                visited[w] = 1
    return None

# 测试程序
class EdgeNode:
    def __init__(self, adjvex, weight=None):
        self.adjvex = adjvex
        self.weight = weight

class Graph:
    def __init__(self, adjlist):
        self.adjlist = adjlist

if __name__ == '__main__':
    # 构造一个邻接表表示的无向图
    adjlist = [
        [EdgeNode(1), EdgeNode(2)],
        [EdgeNode(0), EdgeNode(2), EdgeNode(3)],
        [EdgeNode(0), EdgeNode(1), EdgeNode(4)],
        [EdgeNode(1), EdgeNode(4)],
        [EdgeNode(2), EdgeNode(3)]
    ]
    G = Graph(adjlist)

    # 测试最短路径算法
    u, v = 0, 4
    path = Shortpath(G, u, v)
    if path is None:
        print("No path from", u, "to", v)
    else:
        print("Shortest path from", u, "to", v, ":", path)

在主程序中，我们构造了一个简单的无向图，然后使用 `Shortpath` 函数计算从节点 0 到节点 4 的最短路径。如果不存在这样的路径，程序会输出一条相应的提示信息。否则，它会输出最短路径的节点序列。在此例中，最短路径是 [0, 2, 4]。