编写具有以下要求的程序: 1. 使用 5x5 布尔二维数组来表示需要遍历的图形的连通性。 2. 使用深度优先算法遍历图形。 3. 使用广度优先算法遍历图形。 4、根据图的连通性合理选择遍历的起始位置。给出C++代码
时间: 2024-02-22 18:57:42 浏览: 76
以下是符合要求的C++代码,其中包含深度优先和广度优先的遍历算法:
```c++
#include <iostream>
#include <queue>
using namespace std;
const int N = 5; // 图形大小
void DFS(bool graph[N][N], bool visited[N][N], int x, int y) {
visited[x][y] = true;
cout << "(" << x << "," << y << ")" << endl; // 输出遍历到的点的坐标
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && graph[nx][ny] && !visited[nx][ny]) {
DFS(graph, visited, nx, ny);
}
}
}
void BFS(bool graph[N][N], bool visited[N][N], int x, int y) {
queue<pair<int, int>> q;
q.push(make_pair(x, y));
visited[x][y] = true;
while (!q.empty()) {
pair<int, int> p = q.front();
q.pop();
int x = p.first, y = p.second;
cout << "(" << x << "," << y << ")" << endl; // 输出遍历到的点的坐标
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && graph[nx][ny] && !visited[nx][ny]) {
q.push(make_pair(nx, ny));
visited[nx][ny] = true;
}
}
}
}
int main() {
// 假设图形如下
bool graph[N][N] = {
{1, 0, 0, 0, 0},
{1, 1, 0, 0, 0},
{0, 1, 0, 1, 1},
{0, 1, 0, 0, 1},
{0, 1, 1, 1, 0}
};
bool visited[N][N] = {0};
int x = 0, y = 0; // 选择遍历的起始位置
while (!graph[x][y]) { // 如果起始位置不连通,就向右下方寻找一个连通的位置
if (y < N - 1) y++;
else {
x++;
y = 0;
}
}
cout << "DFS遍历结果:" << endl;
DFS(graph, visited, x, y);
cout << "BFS遍历结果:" << endl;
memset(visited, 0, sizeof(visited)); // 重置visited数组
BFS(graph, visited, x, y);
return 0;
}
```
这个程序使用bool类型的二维数组来表示图形的连通性,使用visited数组来记录每个点是否已经被遍历过。在主函数中,我们可以选择一个合适的起始位置开始遍历,如果起始位置不连通,则向右下方寻找一个连通的位置。最后,我们分别使用深度优先和广度优先算法对图形进行遍历,并输出遍历到的点的坐标。
阅读全文