动态添加到图形数据结构

Question

让我首先说明我只想要方向，而不是实际的代码，除非一个小片段是唯一的方法来获得重点。

我需要在C ++中使用邻接列表或矩阵创建DIRECTED图形数据结构，并从标准输入添加顶点/边缘，这意味着动态。

如果我能够首先实例化一组顶点，然后创建边并将它们添加到图形中，我想我能够创建一个图形，但我不明白如何添加一个包含边的边尚未实例化的顶点。

例如，标准输入的第一行读取：

迈阿密 - >纽约/ 1100 - >华盛顿/ 1000 - > albuquerque / 1700

如果尚未将纽约顶点添加到图表中，我应该如何添加从迈阿密到纽约的边缘？

感谢大家的指导！

Answer 1

如何添加包含尚未实例化的顶点的边缘。

简单：实例化它..

我没有看到任何问题。假设V是到目前为止看到的顶点集。 V最初是空的。当你阅读输入x->y时，你得到它的终点（x和y）。如果它们中的任何一个未实例化（即，不在V中），则将其实例化并将其添加到顶点集。

另一种看待它的方法：想象一下我们通过边缘集E定义图形。根据定义，任何边都是一对顶点，这些顶点又定义了图的顶点集。

Answer 2

每次有新的唯一节点进入时，如何调整邻接列表？您可以维护一组唯一的节点值，并在每次添加节点时使用其大小来调整邻接列表的大小。下面是一些相同的代码。

class Graph
{
    public:
    // Add links in the graph
    void addLink(int id1, int id2){
        // Add to hashset
        uniqueNodes.insert(id1);
        uniqueNodes.insert(id2);
        // Resize on the adjacency list based on how many nodes exists in the uniqueNodes set
        adjList.resize(uniqueNodes.size());
        // Make the connections assuming undirected graph
        adjList[id1].push_back(id2);
        adjList[id2].push_back(id1);
    }

    // Print the graph
    void printGraph(){
        for(int i = 0; i < adjList.size(); i++){
            cout << i << ":";
            for(auto it = adjList[i].begin(); it != adjList[i].end(); it++)
                cout << *it << "->";
            cout << "NULL\n";
        }
    }

    private:
    // Adjacency list for the graph
    vector<list<int>> adjList;
    // Hashset to help define the size of the adjacency list as nodes come in
    set<int> uniqueNodes;
};