C++ 优先队列实现对图边进行排序

Question

我正在尝试对图的边进行排序，但我做不到。下面给出了我实现相同的优先级队列的实现。

  class CompareDistance
    {
        public:    
            bool operator()(pair<int,int> n1,pair<int,int> n2)
            {
                if(g[n1.first][n2.second] < g[n2.first][n2.second])
                return true;
                else
                return false;
           }
    };
    int g[3][3] = {{4,1,3},{3,3,3},{3,3,3}};//graph edges


int main()
{

    priority_queue<pair<int,int>,vector<pair<int,int> >,CompareDistance> pq;


    for(int i = 0 ; i < 3 ; i++)
        for(int j = 0 ; j < 3 ; j++)
            pq.push(pair<int,int>(i,j));

    cout<<"\t"<<g[pq.top().first][pq.top().second];//does not give the correct result
    pq.pop();




    getch();
}

Answer 1

好的，如果我理解正确的话，您就有了一个有向图（例如三个节点的完整图）。每个弧线都有关联的值——权重，您需要的是按此值对弧线集合进行排序。首先，您可能应该创建弧线集合。我认为 priority_queue 不是您的最佳选择。由于简单，我会在这里使用向量：

std::vector<std::pair<int, std::pair<int, int>>> arcs;

其中第一对将包含弧权重和弧存在于其间的节点的有向对。接下来，在添加所有节点后，您只需对指定要比较的自定义函数的集合进行排序。如果您使用 c++11，它可能如下所示：

std::sort(arcs.begin(), arcs.end(), 
          [] (const std::pair<int, std::pair<int, int>>& a,
              const std::pair<int, std::pair<int, int>>& b) { 
                  return a.first < b.first; 
              });

Answer 2

您的代码无法编译，但这很容易解决。我假设 g 包含边权重。这里有一个错误：

if(g[n1.first][n2.second] < g[n2.first][n2.second])

应该是

if(g[n1.first][n1.second] < g[n2.first][n2.second])

注意左边第二个索引的名称。 Live On Coliru

C++ 优先队列实现对图边进行排序

C++ Priority Queue implementation to sort graph edges

c++

stl

graph

priority-queue