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

                                
                                ######## solution.q ########

// using 'scan'
bfs:{raze ({n:(),y[0];v:y[1],n;r:raze $[count[n]<sum v in n;();x n];(r;v)}[x]\[(y;())])[;0]}

// using recursion
bfs:{v:();{z,:y;$[count[y]<sum z in y;y;y,.z.s[x;;z] raze x y]}[x;(),y;v]}

Explanation: To traverse the graph, we will need to keep iteratively traversing the adjacent vertices of the current vertex. We do this using the 'scan' operator, and pass in the starting vertex and empty list into the function as a two-element list (the function also takes in the graph 'x' as an argument). The two-element list represents the current vertex and the visited vertices. We use the visited list to prevent duplicate traversals of the same vertex. Extract the traversed vertices by indexing the 0th index across each two-element list and raze to flatten the result to a single list.

Code:

https://bitbucket.org/alvikabir/dailyq/src/master/Intermediate/graphs-bfs

Tags:

algorithms dictionaries functions

Searchable Tags

algorithms api architecture asynchronous c csv data structures dictionaries disk feedhandler finance functions ingestion ipc iterators machine learning math multithreading optimizations realtime shared library sql statistics streaming strings tables temporal utility websockets

daily q

Graphs - Breadth First Search

Example

Solution

Tags:

Searchable Tags