写一段C++代码,要求图的邻接矩阵存储方式深度遍历和广度遍历算法的实现; 图的邻接表存储方式深度遍历和广度遍历算法的实现。
时间: 2024-12-23 18:26:41 浏览: 43
在C++中,我们可以使用邻接矩阵和邻接表两种方式来表示图。这里分别给出这两种存储方式下,深度优先搜索(DFS)和广度优先搜索(BFS)的简单实现:
**邻接矩阵的方式**
```cpp
#include <iostream>
using namespace std;
// 图结构,邻接矩阵表示
const int MAXN = 100;
bool adj[MAXN][MAXN];
void DFS(int u, bool visited[]) {
visited[u] = true;
cout << u << " ";
for (int v = 0; v < MAXN; ++v)
if (adj[u][v] && !visited[v])
DFS(v, visited);
}
void BFS(int s, bool visited[]) {
queue<int> q;
visited[s] = true;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
for (int v = 0; v < MAXN; ++v)
if (adj[u][v] && !visited[v])
q.push(v), visited[v] = true;
}
}
int main() {
// 初始化图的邻接矩阵...
// 调用DFS和BFS
bool visited[MAXN];
DFS(0, visited); // 深度优先遍历
cout << "\nDepth First Traversal: \n";
BFS(0, visited); // 广度优先遍历
cout << "\nBreadth First Traversal: \n";
return 0;
}
```
**邻接表的方式**
```cpp
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int dest;
vector<Node*> adj; // 存储邻接节点
};
void DFS(Node* node, bool visited[]) {
visited[node->dest] = true;
cout << node->dest << " ";
for (Node* n : node->adj)
if (!visited[n->dest])
DFS(n, visited);
}
void BFS(Node* root, bool visited[]) {
queue<Node*> q;
visited[root->dest] = true;
q.push(root);
while (!q.empty()) {
Node* node = q.front();
q.pop();
cout << node->dest << " ";
for (Node* n : node->adj)
if (!visited[n->dest])
q.push(n), visited[n->dest] = true;
}
}
int main() {
// 初始化图的邻接表...
// 调用DFS和BFS
bool visited[MAXN];
DFS(graph[0], visited); // 深度优先遍历
cout << "\nDepth First Traversal: \n";
BFS(graph[0], visited); // 广度优先遍历
cout << "\nBreadth First Traversal: \n";
return 0;
}
```
在这里,`graph`是一个邻接表形式的图,`Node`结构表示每个顶点及其相邻顶点列表。
阅读全文