c# - topological sort subset of nodes in graph

Question

I have a large graph which represents a set of dependencies. A user can specify that they want to use a certain number of these dependencies and I need to figure out the correct order to use them (they may specify dependent nodes which are not directly related, but which are dependent through other nodes in the graph).

Currently I am implementing this by running a topological sort of the graph and stopping once all of the nodes the user specified have been sorted. However, this does not result in a minimal sort of the needed dependencies and I have to go back and try to remove any unneeded nodes.

Is there some better way to do this or known algorithm for finding the topological sort of a subset of nodes?

Answer 1

最適なソリューションは、依存関係が適切に割り当てられた、ユーザーが選択したノードのみの新しいグラフを作成することです。たとえば、A-->B-->C の場合、ユーザーが A と C を選択すると、構築されたグラフは A-->C になります。次に、標準のトポロジカル ソートを実行します。