定义图的邻接矩阵存储结构,并编写图的初始化、建立图、输出图、深度优先遍历、计算并输出图中每个顶点的度等基本操作实现函数。以下两图为例,建立一个验证操作实现的主函数进行测试。
时间: 2024-02-16 13:00:46 浏览: 12
好的,我会根据您的要求进行回答。以下是图的邻接矩阵存储结构及相关操作实现函数的代码:
```c++
#include <iostream>
using namespace std;
const int MAXV = 100; // 最大顶点数
typedef struct {
int edges[MAXV][MAXV]; // 邻接矩阵
int n; // 顶点数
int e; // 边数
} MGraph;
// 初始化图
void InitGraph(MGraph &g, int n) {
g.n = n;
g.e = 0;
for (int i = 0; i < g.n; i++) {
for (int j = 0; j < g.n; j++) {
g.edges[i][j] = 0;
}
}
}
// 建立图
void CreateGraph(MGraph &g) {
int m;
cout << "请输入边数:";
cin >> m;
cout << "请依次输入每条边的两个端点及权值(用空格隔开):" << endl;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
g.edges[u][v] = w;
g.edges[v][u] = w;
g.e++;
}
}
// 输出图
void PrintGraph(MGraph g) {
cout << "该图的邻接矩阵为:" << endl;
for (int i = 0; i < g.n; i++) {
for (int j = 0; j < g.n; j++) {
cout << g.edges[i][j] << " ";
}
cout << endl;
}
}
// 深度优先遍历
void DFS(MGraph g, int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
for (int i = 0; i < g.n; i++) {
if (g.edges[v][i] != 0 && !visited[i]) {
DFS(g, i, visited);
}
}
}
void DFSTraverse(MGraph g) {
bool visited[MAXV];
for (int i = 0; i < g.n; i++) {
visited[i] = false;
}
cout << "深度优先遍历结果为:";
for (int i = 0; i < g.n; i++) {
if (!visited[i]) {
DFS(g, i, visited);
}
}
cout << endl;
}
// 计算每个顶点的度并输出
void GetDegree(MGraph g) {
cout << "各顶点的度为:" << endl;
for (int i = 0; i < g.n; i++) {
int degree = 0;
for (int j = 0; j < g.n; j++) {
if (g.edges[i][j] != 0) {
degree++;
}
}
cout << "顶点" << i << "的度为:" << degree << endl;
}
}
int main() {
MGraph g1, g2;
InitGraph(g1, 5);
PrintGraph(g1);
CreateGraph(g1);
PrintGraph(g1);
DFSTraverse(g1);
GetDegree(g1);
InitGraph(g2, 6);
PrintGraph(g2);
CreateGraph(g2);
PrintGraph(g2);
DFSTraverse(g2);
GetDegree(g2);
return 0;
}
```
您可以在上面的代码中进行测试,建立两个图并进行相关操作。