邻接矩阵是图的一种常见的表示方式。在C++中,可以通过二维数组来实现邻接矩阵。
邻接矩阵是一个二维数组,其中的元素表示图中节点之间的连接关系。对于一个有n个节点的图,邻接矩阵是一个n * n的二维数组。假设图中的节点编号从0到n-1,则邻接矩阵中的元素A[i][j]表示节点i和节点j之间是否存在边,通常用1或0表示有无边的情况。
邻接矩阵的优点是可以快速地查询两个节点之间是否有边,时间复杂度是O(1)。而缺点是当图中边的数量较少时,邻接矩阵会占用较多的存储空间,因为大部分元素都是0。
下面是一个用C++实现邻接矩阵的示例代码:
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int numVertices;
vector<vector<int>> matrix;
public:
Graph(int num) {
numVertices = num;
matrix = vector<vector<int>>(num, vector<int>(num, 0)); // 初始化邻接矩阵为全0
}
void addEdge(int src, int dest) {
if (src >= 0 && src < numVertices && dest >= 0 && dest < numVertices) {
matrix[src][dest] = 1; // 在邻接矩阵中设置边的连接关系
}
}
bool hasEdge(int src, int dest) {
if (src >= 0 && src < numVertices && dest >= 0 && dest < numVertices) {
return matrix[src][dest] == 1; // 判断邻接矩阵中两个节点之间是否有边
}
return false;
}
};
int main() {
Graph graph(4);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 0);
cout << "Edge between 0 and 1: " << (graph.hasEdge(0, 1) ? "Yes" : "No") << endl;
cout << "Edge between 1 and 3: " << (graph.hasEdge(1, 3) ? "Yes" : "No") << endl;
cout << "Edge between 2 and 0: " << (graph.hasEdge(2, 0) ? "Yes" : "No") << endl;
cout << "Edge between 3 and 2: " << (graph.hasEdge(3, 2) ? "Yes" : "No") << endl;
return 0;
}
这段代码中,我们首先定义了一个Graph类,其中包含了一个私有变量numVertices表示节点的数量,以及一个私有变量matrix表示邻接矩阵。Graph类还定义了addEdge和hasEdge两个方法,分别用来添加边和判断边的存在。
在main函数中,我们创建了一个有4个节点的图,并添加了一些边。然后我们通过调用hasEdge方法来判断某些边的存在。
输出结果为:
Edge between 0 and 1: Yes
Edge between 1 and 3: No
Edge between 2 and 0: No
Edge between 3 and 2: Yes
可以看到,图中存在的边可以被正确地判断出来。