c++ - cpp 中 Graph 的最简单实现

Question

目前我正在学习graph实现。我在 cpp 中使用 vector 找到了 2 个实现，即 matrix 和 adjacency list。但是我面临的问题如下

带矩阵

• 很难传递给函数
• 无法添加新节点
• 内存不足

邻接表的 vector 实现

// Code taken from geeksforgeeks
vector<int> adj[V]; 

// adding edge from u to v
adj[u].push_back(v);

• 无法添加新节点
• 而且传递给函数也很难

所以我想在 cpp 中找到一个可以解决以上两个问题的解决方案。

Answer 1

我在 cpp 中高效且简单地实现了 graph。它解决了您上面提到的所有问题。它被称为vector in vector。

// Suppose at start we have
// number of nodes
int nodes = 5;

// number of edges
int edges = 4;

// define graph
vector<vector<int>> graph(nodes, vector<int>());

int u, v; // edge from u -> v
for(int i=0;i<edges;i++){
    cin >> u >> v;
    graph[u].push_back(v);
}

// suppose we want to add node
graph.push_back(vector<int>());

// print graph content
int index = 0;
for(auto x : graph){
    cout << index << "-> ";
    for(auto y: x){
        cout << y << " ";
    }
    cout << endl;
    index ++;
}

输入以上代码

5 4
0 1
0 2
2 1
2 3

输出

0-> 1 2 
1-> 
2-> 1 3 
3-> 
4-> 
5-> // new node

优势

• 可以在运行时添加节点
• 内存效率
• 你可以像法线 vector 一样轻松地传递给函数
• 您可以在另一个函数中找到节点而无需传递它。