I want to optimize a bidirectional node traversal algorithm.

Because the node is bidirectional, it may cause an infinite loop. The current algorithm uses memory records. However, memory writing will be slower and not friendly to multi-threading.

Maybe I can't express myself well, so I drew a schematic diagram

So I hope I can remove the memory write operation. And the insertion and deletion of nodes is equal to O(1).

Does anyone have any good ideas?

  • \$\begingroup\$ The generic way this is described sounds like a general programming problem that might fit better on StackOverflow. Can you explain more of the context of what this traversal algorithm is doing in your game feature, and include code for a Minimal, Complete, Verifiable example? \$\endgroup\$
    – DMGregory
    Sep 30 at 16:48
  • \$\begingroup\$ @DMGregory This algorithm is used in the constraint system of physical objects. Use this algorithm to traverse all objects in the entire joint system and then calculate the total momentum \$\endgroup\$
    – noodle_run
    Sep 30 at 17:09
  • \$\begingroup\$ So the topology is not necessarily a list but could be an arbitrary graph with branching or cycles? Please edit your question to contain the requested code sample. \$\endgroup\$
    – DMGregory
    Sep 30 at 17:14
  • \$\begingroup\$ @DMGregory Maybe I can't express it well, so I drew a diagram \$\endgroup\$
    – noodle_run
    Sep 30 at 17:42
  • 1
    \$\begingroup\$ I think you might get better answers if you edit your question to ask "How to optimize calculation of sequential impulse" showing your strategy for calculating it so far and your profiling results showing where the bottlenecks are. That kind of specificity will help tailor answers better to your use case than asking a generic question about iterating graphs, and might even permit higher-level algorithmic optimizations or approximations. \$\endgroup\$
    – DMGregory
    Sep 30 at 19:11


You must log in to answer this question.

Browse other questions tagged .