在C++中,可以使用邻接矩阵或邻接表来表示和存储图。
邻接矩阵表示法:
#include <iostream>
#include <vector>
using namespace std;
const int MAX_V = 100;
// 邻接矩阵表示图
class Graph {
private:
int V; // 图中顶点数
int E; // 图中边数
int adj[MAX_V][MAX_V]; // 邻接矩阵
public:
Graph(int V) {
this->V = V;
this->E = 0;
for(int i = 0; i < V; i++) {
for(int j = 0; j < V; j++) {
adj[i][j] = 0;
}
}
}
void addEdge(int v, int w) {
adj[v][w] = 1;
adj[w][v] = 1;
E++;
}
void printGraph() {
for(int i = 0; i < V; i++) {
for(int j = 0; j < V; j++) {
cout << adj[i][j] << " ";
}
cout << endl;
}
}
};
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.printGraph();
return 0;
}
邻接表表示法:
#include <iostream>
#include <vector>
using namespace std;
// 邻接表表示图的边
struct Edge {
int dest; // 目标顶点
};
// 邻接表表示图的顶点
struct Vertex {
vector<Edge> edges; // 与该顶点相连的边
};
// 邻接表表示图
class Graph {
private:
int V; // 图中顶点数
vector<Vertex> adjList; // 邻接表
public:
Graph(int V) {
this->V = V;
adjList.resize(V);
}
void addEdge(int v, int w) {
Edge edge1 = {w};
adjList[v].edges.push_back(edge1);
Edge edge2 = {v};
adjList[w].edges.push_back(edge2);
}
void printGraph() {
for(int i = 0; i < V; i++) {
cout << i << ": ";
for(int j = 0; j < adjList[i].edges.size(); j++) {
cout << adjList[i].edges[j].dest << " ";
}
cout << endl;
}
}
};
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.printGraph();
return 0;
}
以上分别是邻接矩阵和邻接表表示法的实现例子。你可以根据自己的需求选择合适的表示方法来实现图的表示与存储。