• 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 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