Graphs - Depth First Search

Question: Depth First Search (DFS) is an algorithm for traversing graphs. It starts at a vertex and travels as far as possible through each branch before backtracking. Define a function 'dfs' which takes in a graph and vertex, that traverses the graph in a DFS 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/Depth-first_search

Example

                                
                                q)g:`a`b`c`d`e!(`b`c;`a`d;`a`d;`a;`z)
q)h:`a`b`c`d!(`b`c;`d`c;();())
q)dfs[g;`a]
`a`b`d`c`d
q)dfs[h;`a]
`a`b`d`c`c
q)a:1
q)b::a+1
q)c::b+1
q)v:6
q)z::v
q).z.b
a| b
b| c
v| z
q)dfs[.z.b;`a]  // get dependencies for variable 'a'
`a`b`c
                                
                            

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