c++无向图邻接矩阵
时间: 2024-06-16 21:01:16 浏览: 26
在C++中,无向图(Undirected Graph)可以通过邻接矩阵(Adjacency Matrix)来表示。邻接矩阵是一个二维数组,其中的每个元素表示两个顶点之间是否存在边。如果顶点i和顶点j之间有边,矩阵中的[i][j]或[j][i](因为无向图是双向的)会有一个非零值,通常是1或其他非零标识;如果没有边,则对应位置的值为0。
邻接矩阵的主要优点是空间效率较高,适用于稠密图(边的数量接近于顶点数量的平方),查询任意两个顶点间是否有边的时间复杂度是O(1)。然而,对于稀疏图(边的数量远小于顶点数量的平方),邻接矩阵可能会浪费大量空间,因为大部分元素都是0。
邻接矩阵的实现步骤如下:
1. 定义一个二维数组,其大小为顶点数的平方,用于存储边的信息。
2. 初始化数组,例如使用整型数组并初始化为0,表示初始时没有边。
3. 当添加边时,更新对应位置的值。如果是无向图,需要同时更新[i][j]和[j][i]。
4. 查询边的存在时,只需检查[i][j]或[j][i]是否非零。
相关问题
无向图的邻接矩阵c++
以下是一个简单的C++代码示例,用于创建和打印无向图的邻接矩阵:
```c++
#include <iostream>
using namespace std;
const int MAX = 100;
int main() {
int n, m;
int adj[MAX][MAX];
// 输入节点数和边数
cout << "请输入节点数和边数: ";
cin >> n >> m;
// 初始化邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
adj[i][j] = 0;
}
}
// 输入边的信息
for (int i = 0; i < m; i++) {
int u, v;
cout << "请输入第" << i + 1 << "条边的两个端点: ";
cin >> u >> v;
adj[u][v] = 1;
adj[v][u] = 1; // 无向图邻接矩阵对称
}
// 输出邻接矩阵
cout << "邻接矩阵: " << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << adj[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
这段代码首先要求用户输入节点数和边数,然后初始化邻接矩阵。接下来,用户将输入每条边的两个端点,并在邻接矩阵中标记它们。最后,程序将打印邻接矩阵。
创建无向图邻接矩阵算法
在C++中,可以使用邻接矩阵来表示无向图。邻接矩阵是一个二维数组,其中的元素表示图中两个顶点之间的边的存在与否。
下面是一个简单的示例代码,展示了如何创建一个无向图的邻接矩阵:
```cpp
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int numVertices; // 图中顶点的数量
vector<vector<int>> adjMatrix; // 邻接矩阵
public:
// 构造函数
Graph(int num) {
numVertices = num;
adjMatrix.resize(numVertices, vector<int>(numVertices, 0));
}
// 添加边
void addEdge(int src, int dest) {
adjMatrix[src][dest] = 1;
adjMatrix[dest][src] = 1;
}
// 打印邻接矩阵
void printMatrix() {
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
};
int main() {
// 创建一个包含5个顶点的无向图
Graph graph(5);
// 添加边
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
// 打印邻接矩阵
graph.printMatrix();
return 0;
}
```
在上面的代码中,我们首先定义了一个`Graph`类,其中包含了私有成员变量`numVertices`表示图中顶点的数量,以及`adjMatrix`表示邻接矩阵。构造函数用于初始化邻接矩阵的大小。
然后,我们定义了`addEdge`函数用于添加边,这里我们使用1表示两个顶点之间存在边。注意,由于是无向图,所以我们需要同时在两个顶点之间设置边。
最后,我们定义了`printMatrix`函数用于打印邻接矩阵。
在`main`函数中,我们创建了一个包含5个顶点的无向图,并添加了一些边。然后,我们调用`printMatrix`函数打印邻接矩阵。
希望这个示例能够帮助你理解如何使用邻接矩阵来表示无向图。如果你有任何问题,请随时提问。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)