c++ - 按顺时针顺序对图邻接列表中的顶点进行排序

Question

我有一个表示为循环链表数组的平面图。每个列表代表一个顶点及其相邻的顶点。

我需要按顺时针平面顺序对每个邻接表中的顶点进行排序。

我不知道该怎么做。有什么算法吗？

Answer 1

由于您在评论中指出您拥有平面坐标，因此这里有一个使用它们的解决方案(在伪代码中)。基本上，您按照从顶点到相邻顶点的 vector 的 atan2 的升序对每个顶点 v 的相邻顶点 a 进行排序 (a - v)。

struct Point
{
    x, y;
};
// assume Point has overloaded arithmetic operators

void sortAdjacentVertices(Point v, list<Point> adjacentVertices)
{
    map<double, Point> sorted;
    for each (a in adjacentVertices)
    {
        Point dir = a - v;
        sorted[atan2(dir.y, dir.x)] = a;
    }
    adjacentVertices.clear();
    for each (a in sorted)
    {
        adjacentVertices.push(a.value);
    }
}

为图的每个顶点调用此函数将在 O(V * log(V)) 中运行，其中 V 是顶点数，假设可以在 O(1) 中获得邻接列表。这是因为每条边只检查一次(对于有向图)或两次(对于无向图)并且 number of edges in a planar graph is O(V) .