按递增顺序对图形边缘进行排序

Question

我使用标准的邻接列表表示来表示图形，其中每个节点都作为链表出去。您可以在此处阅读有关邻接列表的更多信息。

假设下面是我的图表：

         10
    0--------1
    |       |
   6|   5   |15
    |       |
    2--------3
        4

邻接列表如下所示：

[0,  1,  2,  3]
 |   |   |   |
 10  10  6   6
 |   |   |   |
[1] [0] [0] [2]
 |   |   |   |
 6   15  4   5
 |   |   |   |
[2] [3] [3] [0]
 |   |   |   |
 |   |   |   15
    NULL     |
            [1]
             |
             |
            NULL

由于图形是无向的，因此应将边从源添加到目标，从目标添加到源以及边的粗细。这就是在这种情况下代码表示

形式的样子。

// Linked list representation
class Adj_Node {
  public:
    int data;
    int weight;
    Adj_Node* next;
};
// Adjacency list representation
class Adj_List {
  public:
    Adj_Node* head;
};
// Graph representation
class Graph {
  public:
    int vertices;
    Adj_List* source;
    Graph(int v) {
      vertices = v;
      source = new Adj_List[vertices];
      for (int i = 0; i < vertices; ++i) {
        source[i].head = NULL;
      }
    }
    void addEdge(int, int, int);
    void printGraph();
};
// Creates an linked list node
Adj_Node* createNode(int d) {
  Adj_Node* tmp = new Adj_Node;
  tmp->data   = d;
  tmp->weight = 0;
  tmp->next   = NULL;
  return tmp;
}
// Adds edge to both src and destination
void Graph::addEdge(int src, int dest, int weight) {
  Adj_Node* node = createNode(dest);
  node->next = source[src].head;
  source[src].head = node;
  node->weight = weight;
  node = createNode(src);
  node->next = source[dest].head;
  source[dest].head = node;
  node->weight = weight;
}
void Graph::printGraph() {
  for(int i = 0; i < vertices; ++i) {
  Adj_Node* n = source[i].head;
  std::cout << i << " = ";
  while(n != NULL) {
    std::cout << n->data << " " << n->weight << ", ";
    n = n->next;
  }
  std::cout << std::endl;
}

因此，在说了上述所有内容之后，我在上面描述了链表表示形式，其中图形的每个加权边缘都被描述为链表中的一个节点。问题是：您建议通过哪些方法按递增顺序获得边缘？

Answer 1

如果额外的空间不是问题，我建议只创建一个具有适当operator<的Edge类，但边缘放入标准容器(我会使用 std::vector (并使用 std::sort 对其进行排序。这绝对是一个比实现自己的排序算法更好的主意。

顺便说一句，我认为没有任何理由使用您现在使用的结构。如果要将边存储在列表中，而不是向量中，则可以只使用 std::list(具有 sort 成员函数(而不是重新实现它。

Answer 2

嗯。我实现的是这样的：

当我在链表中添加节点时，以排序方式添加它，以便链表保持按权重排序。因此，最终的图形描述如下所示：

[0,  1,  2,  3]
 |   |   |   |
 6   10  4   5
 |   |   |   |
[2] [0] [3] [0]
 |   |   |   |
10   15  6   6
 |   |   |   |
[1] [3] [0] [2]
 |   |   |   |
 |   |   |   15
    NULL     |
            [1]
             |
             |
            NULL

然后编写一个迭代器，遍历所有链表并将值放入向量中。 矢量模板将是：

// First int is weight, second is source, third is destination of the node.
std::vector < std::pair <int, std::pair<int, int> > >::iterator it = vv.begin();

:)在需要时使用矢量。