帮我用c++语言写一个程序,其功能是定义图的邻接矩阵存储结构,并编写创建图、输出图、深度优先遍历、计算并输出图中每个顶点的度等基本操作实现函数。
时间: 2024-01-22 11:17:37 浏览: 71
好的,以下是代码实现:
```c++
#include <iostream>
using namespace std;
const int MAXN = 100;
// 定义邻接矩阵存储结构
struct GraphMatrix {
int vertexNum; // 顶点数
int edgeNum; // 边数
int matrix[MAXN][MAXN]; // 邻接矩阵
};
// 创建图
void createGraph(GraphMatrix &graph) {
cout << "请输入顶点数和边数:" << endl;
cin >> graph.vertexNum >> graph.edgeNum;
cout << "请输入每条边的两个顶点编号:" << endl;
for (int i = 0; i < graph.edgeNum; i++) {
int u, v;
cin >> u >> v;
graph.matrix[u][v] = 1; // 有向图
}
}
// 输出图
void printGraph(GraphMatrix graph) {
cout << "邻接矩阵为:" << endl;
for (int i = 0; i < graph.vertexNum; i++) {
for (int j = 0; j < graph.vertexNum; j++) {
cout << graph.matrix[i][j] << " ";
}
cout << endl;
}
}
// 深度优先遍历
void dfs(GraphMatrix graph, int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
for (int i = 0; i < graph.vertexNum; i++) {
if (graph.matrix[v][i] == 1 && !visited[i]) {
dfs(graph, i, visited);
}
}
}
// 计算每个顶点的度
void calcDegree(GraphMatrix graph) {
for (int i = 0; i < graph.vertexNum; i++) {
int degree = 0;
for (int j = 0; j < graph.vertexNum; j++) {
if (graph.matrix[i][j] == 1) {
degree++;
}
}
cout << "顶点" << i << "的度为:" << degree << endl;
}
}
int main() {
GraphMatrix graph;
createGraph(graph);
printGraph(graph);
cout << "深度优先遍历结果为:";
bool visited[MAXN] = {0}; // 记录是否访问过
dfs(graph, 0, visited); // 从0号顶点开始遍历
cout << endl;
calcDegree(graph);
return 0;
}
```
希望能够帮到你!
阅读全文