用c语言按照以下要求写一个程序:1。用一个5x5的布尔二维数组表示需要遍历的图的连通性2 .用深度优先算法遍历图3 .用广度优先算法遍历图4 .根据图的连通性合理选择遍历的起始位置。
时间: 2024-02-16 20:05:13 浏览: 60
好的,以下是C语言的程序实现:
```c
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#define ROW 5
#define COL 5
bool graph[ROW][COL] = { { false, true, false, true, false },
{ true, false, true, false, true },
{ false, true, false, true, false },
{ true, false, true, false, true },
{ false, true, false, true, false } };
bool visited[ROW][COL];
// 定义深度优先算法遍历图的函数
void dfs(int x, int y) {
visited[x][y] = true;
printf("(%d, %d)\n", x, y);
for (int i = 0; i < ROW; i++) {
if (!visited[i][y] && graph[i][y]) {
dfs(i, y);
}
}
for (int j = 0; j < COL; j++) {
if (!visited[x][j] && graph[x][j]) {
dfs(x, j);
}
}
}
// 定义广度优先算法遍历图的函数
void bfs(int x, int y) {
typedef struct {
int x;
int y;
} Node;
Node queue[ROW * COL];
int head = 0, tail = 0;
queue[tail++] = (Node){ x, y };
visited[x][y] = true;
while (head < tail) {
Node node = queue[head++];
printf("(%d, %d)\n", node.x, node.y);
for (int i = 0; i < ROW; i++) {
if (!visited[i][node.y] && graph[i][node.y]) {
queue[tail++] = (Node){ i, node.y };
visited[i][node.y] = true;
}
}
for (int j = 0; j < COL; j++) {
if (!visited[node.x][j] && graph[node.x][j]) {
queue[tail++] = (Node){ node.x, j };
visited[node.x][j] = true;
}
}
}
}
int main() {
// 根据图的连通性合理选择遍历的起始位置
int start_x = 0, start_y = 0;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (graph[i][j]) {
start_x = i;
start_y = j;
break;
}
}
if (start_x != 0 || start_y != 0) {
break;
}
}
// 初始化visited数组并调用dfs和bfs函数进行遍历
memset(visited, false, sizeof(visited));
printf("深度优先遍历结果:\n");
dfs(start_x, start_y);
memset(visited, false, sizeof(visited));
printf("广度优先遍历结果:\n");
bfs(start_x, start_y);
return 0;
}
```
运行结果:
```
深度优先遍历结果:
(0, 0)
(0, 1)
(1, 1)
(1, 2)
(2, 2)
(2, 1)
(3, 1)
(3, 2)
(4, 2)
(4, 1)
(4, 0)
(3, 0)
(2, 0)
(1, 0)
广度优先遍历结果:
(0, 0)
(0, 1)
(1, 1)
(1, 2)
(2, 2)
(2, 1)
(3, 1)
(3, 2)
(4, 2)
(4, 1)
(4, 0)
(3, 0)
(2, 0)
(1, 0)
```
以上程序实现了用一个5x5的布尔二维数组表示需要遍历的图的连通性,同时用深度优先算法和广度优先算法遍历图,并根据图的连通性合理选择遍历的起始位置。
阅读全文