计算 BFS 算法中的节点和弧

Question

在 DFS 中，您可以通过初始化两个计数器并在 DFS-VISIT 过程中递增它们来对元素进行计数（每次调用该过程时 +1 个节点，每次探索邻接表时 +1 个弧）。我想知道如何在 BFS 中获得相同的结果。这是来自 Cormen "Introduction to Algorithms" 的 BFS 伪代码，其中 G 是图，s 是源节点，d 是距离，π 是父节点。如何修改得到G中的节点数和弧数？

BFS(G, s)
    for each node u ∈ G.V - {s}
        u.color = white 
        u.d = ∞
        u.π = NIL
    s.color = GRAY
    s.d = 0
    s.π = NIL
    Q = Ø
    ENQUEUE(Q, s)
    while Q != Ø
        u = DEQUEUE(Q)
        for each v ∈ G.Adj[u]
                if v.color == WHITE
                        v.color = GRAY
                        v.d = u.d + 1
                        v.π = u
                        ENQUEUE(Q, v)
        u.color = BLACK

Answer 1

好吧，邻接表遍历和新顶点（节点）发现都是在伪代码的最后一个 while 循环中完成的。因此，类似下面给出的修改可能会起作用。

numArcs = 0
numNodes = 0
while Q != Ø
    u = DEQUEUE(Q)
    numNodes += 1
    for each v ∈ G.Adj[u]
            numArcs += 1
            if v.color == WHITE
                    v.color = GRAY
                    v.d = u.d + 1
                    v.π = u
                    ENQUEUE(Q, v)
    u.color = BLACK

注意，如果要统计所有的弧，numArcs的增量应该在其后面的if语句的范围之外，因为if语句只有在目的节点不存在时才进入之前排队。

另请注意，此算法仅给出连通分量中的弧和节点数，包括起始节点 s。因此，除非修改 BFS 算法以处理具有多个连通分量的图的情况，否则该算法将无法找出未连通图中的所有节点和弧。

计算 BFS 算法中的节点和弧

Counting nodes and arcs in BFS Algorithm

computer-science

graph

graph-algorithm