c++数据结构建立有向图

在C++中，可以使用邻接表或邻接矩阵来表示有向图。下面分别介绍这两种表示方法的实现。

1.邻接表表示法

邻接表是一种链式存储结构，它将每个顶点的所有邻接点存储在一个链表中。每个链表的头节点表示该顶点，该链表中的其他节点表示该顶点所指向的邻接点。因此，邻接表的存储空间与图中的边数成正比。

邻接表的实现代码如下：

#include <iostream>
#include <vector>

using namespace std;

// 定义邻接表中的节点
struct Node {
    int val;            // 节点的值
    Node* next;         // 指向下一个节点的指针
    Node(int v) : val(v), next(NULL) {}
};

// 定义邻接表
class Graph {
public:
    int n;              // 图中节点的个数
    vector<Node*> adj;  // 存储每个节点的邻接表

    // 构造函数
    Graph(int num) : n(num) {
        adj.resize(n);
        for (int i = 0; i < n; i++)
            adj[i] = new Node(i);   // 初始化每个邻接表的头节点
    }

    // 添加一条从起点到终点的有向边
    void addEdge(int from, int to) {
        Node* node = new Node(to);
        node->next = adj[from]->next;
        adj[from]->next = node;
    }
};

int main() {
    Graph g(5);     // 创建一个有5个节点的图

    g.addEdge(0, 1);    // 添加边0->1
    g.addEdge(0, 2);    // 添加边0->2
    g.addEdge(1, 3);    // 添加边1->3
    g.addEdge(2, 3);    // 添加边2->3
    g.addEdge(2, 4);    // 添加边2->4

    return 0;
}

2.邻接矩阵表示法

邻接矩阵是一种二维数组，其中行和列分别代表图中的节点，矩阵中的每个元素表示相应节点之间是否存在一条边。对于有向图，邻接矩阵是一个对称矩阵。

邻接矩阵的实现代码如下：

#include <iostream>
#include <vector>

using namespace std;

// 定义邻接矩阵
class Graph {
public:
    int n;                  // 图中节点的个数
    vector<vector<int>> adj; // 存储邻接矩阵

    // 构造函数
    Graph(int num) : n(num) {
        adj.resize(n, vector<int>(n, 0));   // 初始化邻接矩阵
    }

    // 添加一条从起点到终点的有向边
    void addEdge(int from, int to) {
        adj[from][to] = 1;
    }
};

int main() {
    Graph g(5);     // 创建一个有5个节点的图

    g.addEdge(0, 1);    // 添加边0->1
    g.addEdge(0, 2);    // 添加边0->2
    g.addEdge(1, 3);    // 添加边1->3
    g.addEdge(2, 3);    // 添加边2->3
    g.addEdge(2, 4);    // 添加边2->4

    return 0;
}

以上是两种常见的有向图的表示方法，你可以根据具体情况选择适合的方法。