建立图的邻接存储并在此基础上实现图的深度优先遍历和广度优先遍历 投歌答案

以下是C++实现图的邻接矩阵存储和深度广度优先遍历的方法：

1. 邻接矩阵存储图

c++
const int MAXN = 100; // 最大顶点数
int G[MAXN][MAXN]; // 邻接矩阵
int n, m; // n为顶点数，m为边数

void init() {
memset(G, 0, sizeof(G)); // 初始化邻接矩阵
}

void addEdge(int u, int v) {
G[u][v] = G[v][u] = 1; // 无向图，所以需要将两个方向都赋值为1
}

2. 深度优先遍历

bool vis[MAXN]; // 标记数组，标记每个顶点是否被访问过

void dfs(int u) {
vis[u] = true; // 标记该顶点已被访问
cout << u << " "; // 输出该顶点
for (int v = 0; v < n; v++) {
if (G[u][v] && !vis[v]) { // 如果u和v之间有边，并且v未被访问过
dfs(v); // 递归访问v
}
}
}

void dfsTraversal() {
memset(vis, false, sizeof(vis)); // 初始化标记数组
for (int u = 0; u < n; u++) {
if (!vis[u]) { // 如果该顶点未被访问过
dfs(u); // 从该顶点开始进行深度优先遍历
}
}
}

3. 广度优先遍历

bool vis[MAXN]; // 标记数组，标记每个顶点是否被访问过

void bfs(int u) {
queue<int> q; // 定义队列
q.push(u); // 将起始顶点u入队
vis[u] = true; // 标记该顶点已被访问
while (!q.empty()) { // 当队列不为空时
int v = q.front(); // 取出队首元素v
q.pop(); // 将队首元素v出队
cout << v << " "; // 输出该顶点
for (int i = 0; i < n; i++) {
if (G[v][i] && !vis[i]) { // 如果v和i之间有边，并且i未被访问过
q.push(i); // 将顶点i入队
vis[i] = true; // 标记该顶点已被访问
}
}
}
}

void bfsTraversal() {
memset(vis, false, sizeof(vis)); // 初始化标记数组
for (int u = 0; u < n; u++) {
if (!vis[u]) { // 如果该顶点未被访问过
bfs(u); // 从该顶点开始进行广度优先遍历
}
}
}