定义图的邻接矩阵存储结构,并编写图的初始化、建立图、输出图、深度优先/广度优先遍历、计算并输出图中每个顶点的度(入度+出度)等基本操作的实现函数。以下图为例,建立一个验证操作实现的主函数进行测试。
时间: 2024-10-29 17:16:29 浏览: 42
邻接矩阵是一种常用的图数据结构,它是一个二维数组,其中行代表源节点,列表示目标节点。如果矩阵的(i, j)位置非零,表示从i到j存在一条边;如果是0,则表示没有连接。
首先,我们可以定义一个邻接矩阵的结构:
```cpp
#include <vector>
using namespace std;
// 图的邻接矩阵表示
class AdjMatrixGraph {
public:
vector<vector<int>> adjMatrix; // 存储邻接关系
// 初始化空图
AdjMatrixGraph(int vertices) {
adjMatrix.resize(vertices, vector<int>(vertices, 0));
}
// 添加边 (u, v)
void addEdge(int u, int v) {
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1; // 如果需要考虑有向图,这里只对u到v加1
}
// 输出图的邻接矩阵
void printAdjMatrix() {
for (int i = 0; i < adjMatrix.size(); i++) {
for (int j = 0; j < adjMatrix[i].size(); j++) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
// 深度优先搜索
void dfs(int start) {
vector<bool> visited(adjMatrix.size(), false);
dfsHelper(start, visited);
}
// 辅助深度优先搜索函数
void dfsHelper(int node, vector<bool>& visited) {
visited[node] = true;
cout << node << " "; // 可以打印节点值或其他操作
for (int i = 0; i < adjMatrix[node].size(); i++) {
if (!visited[i]) {
dfsHelper(i, visited);
}
}
}
// 广度优先搜索
void bfs(int start) {
vector<bool> visited(adjMatrix.size(), false);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << " "; // 打印节点值或其他操作
for (int i = 0; i < adjMatrix[node].size(); i++) {
if (!visited[i]) {
visited[i] = true;
q.push(i);
}
}
}
}
// 计算并输出每个顶点的度
void degreeOfEachNode() {
for (int i = 0; i < adjMatrix.size(); i++) {
int inDegree = 0, outDegree = 0;
for (int j = 0; j < adjMatrix[i].size(); j++) {
if (adjMatrix[i][j] == 1) {
inDegree++; // 对于无向图,这里只计算一次
}
}
for (int j = 0; j < i; j++) {
if (adjMatrix[j][i] == 1) {
outDegree++;
}
}
cout << "Node " << i << ": In Degree = " << inDegree << ", Out Degree = " << outDegree << endl;
}
}
};
// 主函数用于测试
int main() {
AdjMatrixGraph graph(5); // 创建一个包含5个顶点的图
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3); // 自环
graph.printAdjMatrix();
graph.dfs(0);
graph.bfs(2);
graph.degreeOfEachNode();
return 0;
}
```
这个例子展示了如何创建一个邻接矩阵图结构以及其基本操作的实现,包括初始化、添加边、输出图、深度优先和广度优先遍历以及计算度。主函数中,我们创建了一个简单的图并进行了相应的操作。
阅读全文