Algorithm - 2023.1 English

Vitis Libraries

Release Date
2023-12-20
Version
2023.1 English

The implemented Breadth-first Search is based on a First-In-First-Out execution queue. Below is the pseudo-code of the algorithm:

procedure BFS(graph, source)
for each vertex v in graph
    discover(v) := positive infinity

discover(source) := 0
dtime := 0
cnt_bfr := 1
cnt_cur := 0
cnt_nxt := 0
cnt_lvl := 0
push source into Q
while Q is not empty
    u := pop Q
    cnt_cur++
    for each edge(u,v) in graph
        if discover(v) == positive infinity then
            discover(v) := dtime
            level(v) := cnt_lvl
            parent(v) := u
            push v into Q
            dtime++
            cnt_nxt++
        end if
    end for
    finish(u) := dtime
    dtime++
    if cnt_cur == cur_bfr then
        cnt_bfr := cnt_nxt
        cnt_cur := 0
        cnt_nxt := 0
        cnt_lvl ++
    end if
end while

return (level, parent, discover, finish)

Here, graph is a graph with a list of vertices and a list of edges. source is the start vertex of the algorithm. Q is a first-in-first-out queue.