31 lines
976 B
Plaintext
31 lines
976 B
Plaintext
// Graph flavor: breadth-first search with a LIST as a queue (REMOVE at 0) and a SET of seen nodes.
|
|
// Finding: a neighbor cannot be called Next, because names ignore case and NEXT is a keyword.
|
|
// EXPECT: [0, 1, 2, 3, 4]
|
|
FUNCTION BFS(Adj : HASHMAP OF INTEGER : LIST OF INTEGER, Start : INTEGER) RETURNS LIST OF INTEGER
|
|
DECLARE Queue, Order : LIST OF INTEGER
|
|
DECLARE Seen : SET OF INTEGER
|
|
APPEND(Queue, Start)
|
|
ADD(Seen, Start)
|
|
WHILE LENGTH(Queue) > 0
|
|
DECLARE Node : INTEGER
|
|
Node <- Queue[0]
|
|
REMOVE(Queue, 0)
|
|
APPEND(Order, Node)
|
|
IF Node IN Adj THEN
|
|
FOR EACH Nb IN Adj[Node]
|
|
IF NOT (Nb IN Seen) THEN
|
|
ADD(Seen, Nb)
|
|
APPEND(Queue, Nb)
|
|
ENDIF
|
|
NEXT Nb
|
|
ENDIF
|
|
ENDWHILE
|
|
RETURN Order
|
|
ENDFUNCTION
|
|
DECLARE G : HASHMAP OF INTEGER : LIST OF INTEGER
|
|
G[0] <- [1, 2]
|
|
G[1] <- [3]
|
|
G[2] <- [3, 4]
|
|
G[3] <- [4]
|
|
OUTPUT BFS(G, 0)
|