Graphs - Breadth First Search

Question: Breadth First Search (BFS) is an algorithm for traversing graphs level by level. It starts at a vertex and travels to the adjacent vertices, and keeps doing this until it reaches the end of the graph. Define a function 'bfs' which takes in a graph and vertex, that traverses the graph in a BFS manner from that vertex and returns the traversal path as a list. If the graph contains cycles, ignore them.

More Information:

https://en.wikipedia.org/wiki/Breadth-first_search

Example

                                
                                q)g:`a`b`c`d!(`b`c;`a`d;`a`d;`a) // contains cycles
q)bfs[g;`a]
`a`b`c`a`d`a`d`a`a

q)h:`a`b`c`d!(`b`c;`d;();()) // no cycles
q)bfs[h;`a]
`a`b`c`d
                                
                            

Solution

Tags:
algorithms dictionaries functions
Searchable Tags
algorithms api architecture csv data structures dictionaries disk feedhandler finance functions ingestion ipc iterators machine learning math multithreading optimizations realtime sql statistics streaming strings tables temporal websockets

Email sent!

Email not sent