有一个无向图G = (V, E)，如何为每条边分配一个方向，以便每个顶点在O(V+E)时间上最多有一个入度？应该有2个条件：
情况1.G没有循环
我应该用什么？BFS 或 DFS，又如何？情况 2. G 最多有 1 个
环 如果有一个环，我们如何选择指向同一个顶点的 2 条边的方向？
问问题
274 次
1 回答
1
对于任何只有一条边的顶点，如果你能完全解决这个难题，你仍然可以在确定连接到该顶点的唯一边有一个指向该顶点的方向后解决它。
所以我会在每个顶点上使用计数器来跟踪连接到该顶点的边数，并重复设置边的方向，这些边的一端在顶点上，没有其他附加边，然后从图中删除这些边及其顶点（或将它们标记为已删除）并继续。
如果此过程以空图终止，则没有循环并且您已经解决了问题。
如果它以一个或多个循环结束，其中每个顶点都有两条边连接到它，然后选择一条边的方向并跟随它围绕循环选择你遇到的每条边的唯一可能方向。如果有多个循环，则必须多次执行此操作才能为所有剩余边设置方向。
如果这以一个连接了两个以上边的顶点和每个顶点都连接了多个边而终止，那么你有比循环更复杂的东西，并且无法分配路径和方向，因此每个顶点最多有入度一。
于 2017-11-23T05:31:46.013 回答