C++中最简单的图实现

Question

我目前正在学习图的实现。我找到了两种实现方法，分别是使用cpp中的矩阵和基于向量的邻接表。但我面临以下问题：

矩阵的实现方式

• 参数传递困难
• 无法添加新节点
• 内存利用率低效

基于向量的邻接表实现方式

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

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

• 无法添加新节点
• 同时将其传递给函数也很困难

因此，我希望有一种可以解决上述两个问题的 cpp 解决方案。

- BeOpen

---

二维向量？你说的“传递给函数很难”是什么意思？你在将数组adj传递给函数时遇到了什么问题？像所有数组一样，它很容易衰减为指向其第一个元素的指针。 - Some programmer dude

如果您不想使用固定大小的容器（C数组/std::array），请用动态容器（std::vector）替换它们。 - Jarod42

@Someprogrammerdude：我认为OP谈到了通过“丑陋”的语法传递C数组的引用。 - Jarod42

我认为“指针”对我来说是一个非常难的话题。我正在严格遵守与它相关的“社交距离”。感谢@Someprogrammerdude和@PSKP向我介绍了“向量的向量”。 - BeOpen

Answer 1

我在cpp中有高效且简单的图实现。它解决了您上述提到的所有问题。它被称为“向量中的向量”。

// 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

优点

• 可以在运行时添加节点
• 内存效率高
• 像普通向量一样轻松传递到函数中
• 无需传递即可在另一个函数中查找节点

- PSKP

Answer 2

这并不是一个高效的实现，但也许一组键值对正是你所需要的。

#include <iostream>
#include <utility>
#include <set>
#include <algorithm>

template<class T>
class graph
{
public:
    std::set<std::pair<T, T>> storage;

    /* true item added, false otherwise */
    bool add_edge(T v1, T v2)
    {
        auto ret = storage.insert(std::make_pair(v1, v2));
        return ret.second;
    }

    /* return value: edges deleted */
    int delete_edge(T v1, T v2)
    {
        return storage.erase(std::make_pair(v1, v2));
    }

    void print_graph()
    {
        std::for_each(storage.begin(), storage.end(),
        [](std::pair<T, T> const& p) {
            std::cout << p.first << "--> " << p.second << std::endl;
        });
    }
};

---

#include <iostream>
#include "graph.h"

int main()
{
    graph<int> g;
    g.add_edge(5, 4);
    g.add_edge(5, 4);
    g.add_edge(6, 2);
    g.print_graph();
    g.delete_edge(5, 4);
    g.print_graph();
    return 0;
}

编译命令

g++ -std=c++17 -Wall -Wextra -pedantic main.cpp

输出

5 --> 4
6 --> 2
/* Deleted 5 --> 4 */
6 --> 2

- Tony