c++ - 如何在 C++ 中表示图形

Question

我想编写创建 MST 的 prims 和 dijkstra 算法。但我不知道在 C++ 中表示图的最佳方式是什么。

我可以用两个整数对表示边，例如 vector 0 到 1 将是 pair(0,1)；

typedef pair<int, int> Edge;

然后 prims 函数将采用由边及其权重组成的对 vector 。

void prims(vector<pair<Edge, int>>);

我认为这种方式不是最好的方式，谁能告诉我哪种方式最适合表示图形？

Answer 1

我前段时间一直在实现 Dijkstra 以在二进制图像中查找路径。我将图形表示为结构 GraphNodes 的 vector ，其中包含 Connections 的 vector ，其中包含节点与其他节点的所有连接。每个连接都有其距离属性，即边的权重。这是我使用的两个结构:

//forward declaration
struct GraphNode;
struct Connection {
    Connection() : distance(1) { };
    Connection(GraphNode* ptr, double distance) : ptr(ptr), distance(distance) { };
    bool operator==(const Connection &other) const;
    GraphNode* ptr;
    double distance;
};

struct GraphNode {
    GraphNode() : connections(8), predecessor(NULL), distance(-1) { };
    cv::Point point;
    double distance;
    GraphNode* predecessor;
    std::vector<Connection> connections;
};

bool Connection::operator==(const Connection &other) const {
    return ptr == other.ptr && distance == other.distance;
}

GraphNode的distance属性是它当前在Dijkstra算法中的距离，所以是当前已知距离起始节点的最短距离。在开始时，这是用 -1 初始化的。

然后我像这样实现了 Dijkstra 算法:

std::vector<cv::Point> findShortestPathDijkstra(std::vector<GraphNode>& graph, int startNodeIndex, int destNodeIndex) const {
    GraphDistanceSorter sorter(graph);
    std::set<GraphNode*, GraphDistanceSorter> unusedNodes(sorter);
    for (int i = 0; i < graph.size(); ++i) {
        unusedNodes.insert(&graph[i]);
    }

    while (unusedNodes.size() > 0) {

        GraphNode* currentNode = *unusedNodes.begin();
        if (currentNode->distance == -1) {
            return std::vector<cv::Point>();
        }
        if (currentNode == &graph[destNodeIndex]) break;
        unusedNodes.erase(currentNode);
        //update distances of connected nodes
        for (Connection const& con : currentNode->connections) {
            /*here we could check if the element is really in unusedNodes (search, O(log n)), but this would
            actually take longer than calculating the new distance (O(1)), which will in this case always be greater
            than the old one, so the distance is never updated for nodes not in unusedNodes ()*/
            double newDistance = currentNode->distance + con.distance;
            if (newDistance < con.ptr->distance || con.ptr->distance == -1) {
                unusedNodes.erase(con.ptr);
                con.ptr->distance = newDistance;
                con.ptr->predecessor = currentNode;
                unusedNodes.insert(con.ptr);
            }
        }
    }

    //now trace back the path as a list of points
    std::vector<cv::Point> points;
    GraphNode* current = &graph[destNodeIndex];
    points.push_back(current->point);
    while (current != &graph[startNodeIndex]) {
        if (current->predecessor == NULL) return std::vector<cv::Point>();
        current = current->predecessor;
        points.push_back(current->point);
    }

    return points;

}

如您所见，有一组 unusedNodes 包含到目前为止所有未使用的节点。它只包含图形节点上的指针。实际的图形表示在 vector 中。拥有一个集合的好处是，它总是根据特定的标准进行排序。我实现了自己的排序器 GraphDistanceSorter，它根据 Dijkstra 算法的距离标准对 GraphNode 进行排序。这样我只需要从集合中选择第一个节点并知道它是距离最小的节点:

struct GraphDistanceSorter {
    bool operator() (const GraphNode* lhs, const GraphNode* rhs) const;
};

bool GraphDistanceSorter::operator() (const GraphNode* lhs, const GraphNode* rhs) const {
    if (lhs->distance == rhs->distance) {
        return lhs < rhs;
    } else {
        if (lhs->distance != -1 && rhs->distance != -1) {
            if (lhs->distance != rhs->distance) {
                return lhs->distance < rhs->distance;
            }
        } else if (lhs->distance != -1 && rhs->distance == -1) {
            return true;
        }
        return false;
    }
}