我正在处理一个图中，其中有一定数量的节点，并且它们之间有预定义的连接，这些连接还没有“方向”。
问题是给所有边一个方向（例如，如果A和B之间存在连接，则给该边指定A-> B方向，或B-> A），这样就没有节点位于接收方不止一个优势。
示例：对于此模型（ABC），A-> B-> C有效，但A-> B <-C不起作用，因为B位于多个连接的接收端。尽管A <-B-> C起作用，但是因为B在其两个连接的给定端上。
我曾尝试过环路检测，但实际上这些节点可以任意连接，事实是，可能有很多环路可能彼此直接连接，也可能不直接连接，我找不到使用信息的解决方案。
节点数可以是数千个，在我的情况下，连接数可以是数百个。这也排除了蛮力。
不能保证会有一个确定的解决方案，该算法的目的是找到一种连接数量最少的组合，从而使节点指向它们的边多于一个。
不是一个完整的算法，但考虑到您在评论中对问题的描述，我觉得这些步骤可能会将问题带回暴力范围。
首先，您应该“修剪”您的图表。任何一级节点都应该被修剪，它们的连接边指向被修剪的节点。由于没有其他边可以指向该节点，因此我们知道这个选择是最优的。冲洗并重复，直到剩余的所有节点都有两个或多个边缘。
接下来，正如您所提到的，您应该排除任何孤立的节点。您实际上可以将其扩展到size <= 3. 这是因为对于最多三个节点，您的边数不能超过节点数，因此您可以随机分配一条边，其余的将就位。
现在，剩下的就是一堆大型的、高度连接的、互联的组件。实际上，您可以再做一次检查，看看其中是否有任何一个形成单个循环（所有节点的度数为 2），然后随机分配一条边，但这可能是一种相当罕见的情况。您可能只想开始独立地暴力破解其中每一个。最好首先从边数最少的节点开始，在分配边时更新节点的度数（并像以前一样修剪任何度数的边），并根据需要回溯。