I have a collection of graph nodes which are connected to each other.
I wrote a DFS algorithm to recursively search the connectivity of the graph to find all connected nodes, however due to the size of the network, it is taking too long.
To improve the performance, I wanted to assign tags to the nodes, as MAJOR and NOT-MAJOR, such that I can create a new graph that only contains the connections from MAJOR nodes to other MAJOR nodes, sort of illustrated in the photo below where the big circle denotes MAJOR and the red dot denotes NOT-MAJOR:
The desired result would be taking the left graph and compressing it down to the right.
The data I am working through is very large, and there are a lot of interconnections, many islands, and always at least 1 major node.
I have written a second version of my DFS function to take the graph and a major node, traverse each connected node to the major and check if the connected node is a major node, if so then append that major node to a new list, and return the list as the new connections, otherwise return a list only containing the major node itself.
But this is still taking a very long time to pass through the entire network, with the program sometimes crashing due to maximum recursion depth exceeded (Which tells me I have not implemented this very well).
Is there a better way I can approach this compression problem?