在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;
}
以上分別是鄰接矩陣和鄰接表表示法的實現例子。你可以根據自己的需求選擇合適的表示方法來實現圖的表示與存儲。