c++ 产生图的数据结构
时间: 2023-08-06 20:09:23 浏览: 88
在C++中,可以使用多种数据结构来表示图。以下是几种常见的图数据结构:
1. 邻接矩阵(Adjacency Matrix):使用二维数组来表示图的连接关系。矩阵中的元素表示节点之间的边的存在与否。适用于稠密图,但对于稀疏图会浪费空间。
```cpp
const int MAX_SIZE = 100;
int graph[MAX_SIZE][MAX_SIZE]; // 邻接矩阵
// 初始化
memset(graph, 0, sizeof(graph));
// 添加边
graph[node1][node2] = 1;
graph[node2][node1] = 1;
```
2. 邻接表(Adjacency List):使用数组和链表的组合来表示图的连接关系。每个节点都有一个链表存储与其相邻的节点。适用于稀疏图,节省空间。
```cpp
#include <vector>
using namespace std;
class Graph {
private:
int numVertices;
vector<vector<int>> adjList;
public:
Graph(int n) {
numVertices = n;
adjList.resize(n);
}
void addEdge(int src, int dest) {
adjList[src].push_back(dest);
adjList[dest].push_back(src);
}
};
```
3. 边列表(Edge List):使用数组来存储图中的所有边。每个边由起点和终点组成。
```cpp
#include <vector>
using namespace std;
class Edge {
public:
int src;
int dest;
Edge(int s, int d) {
src = s;
dest = d;
}
};
class Graph {
private:
int numVertices;
vector<Edge> edgeList;
public:
Graph(int n) {
numVertices = n;
}
void addEdge(int src, int dest) {
Edge edge(src, dest);
edgeList.push_back(edge);
}
};
```
这些是常见的图数据结构示例,根据具体需求可以选择适合的数据结构来表示图。