实现图的邻接矩阵的初始化,建立图,输出图,深度优先遍历,计算并输出每个顶点的毒等操作的完整代码
时间: 2023-08-11 10:04:05 浏览: 37
以下是基于邻接矩阵的图的实现,包括初始化、建立、输出、深度优先遍历、计算每个顶点的度等操作的完整代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100;
class Graph {
private:
int n; // 顶点数
int e; // 边数
int mat[MAXN][MAXN]; // 邻接矩阵
public:
Graph(int n) {
this->n = n;
this->e = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mat[i][j] = 0;
}
}
}
void addEdge(int u, int v) {
mat[u][v] = 1;
mat[v][u] = 1;
e++;
}
void output() {
cout << "Graph: " << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << mat[i][j] << " ";
}
cout << endl;
}
}
void dfs(int u, vector<bool>& visited) {
visited[u] = true;
cout << u << " ";
for (int v = 0; v < n; v++) {
if (mat[u][v] && !visited[v]) {
dfs(v, visited);
}
}
}
void dfsTraversal() {
vector<bool> visited(n, false);
cout << "DFS Traversal: ";
for (int u = 0; u < n; u++) {
if (!visited[u]) {
dfs(u, visited);
}
}
cout << endl;
}
void degree() {
cout << "Degrees: ";
for (int u = 0; u < n; u++) {
int deg = 0;
for (int v = 0; v < n; v++) {
if (mat[u][v]) {
deg++;
}
}
cout << deg << " ";
}
cout << endl;
}
};
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.output();
g.dfsTraversal();
g.degree();
return 0;
}
```
输出结果如下:
```
Graph:
0 1 1 0 0
1 0 1 0 0
1 1 0 1 0
0 0 1 0 1
0 0 0 1 0
DFS Traversal: 0 1 2 3 4
Degrees: 2 2 3 2 1
```