用C语言实现图的遍历算法
时间: 2023-10-30 22:07:52 浏览: 52
图的遍历算法有深度优先遍历和广度优先遍历两种。以下是用C语言实现这两种算法的代码:
1. 深度优先遍历算法
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
int visited[MAX_VERTICES];
int adj_matrix[MAX_VERTICES][MAX_VERTICES];
void dfs(int v, int n)
{
int i;
visited[v] = 1;
printf("%d ", v);
for (i = 0; i < n; i++) {
if (adj_matrix[v][i] && !visited[i]) {
dfs(i, n);
}
}
}
int main()
{
int n, i, j;
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &adj_matrix[i][j]);
}
}
printf("DFS traversal: ");
for (i = 0; i < n; i++) {
visited[i] = 0;
}
for (i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, n);
}
}
printf("\n");
return 0;
}
```
2. 广度优先遍历算法
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
int visited[MAX_VERTICES];
int adj_matrix[MAX_VERTICES][MAX_VERTICES];
void bfs(int v, int n)
{
int queue[MAX_VERTICES];
int front = 0, rear = 0, i, u;
visited[v] = 1;
printf("%d ", v);
queue[rear++] = v;
while (front < rear) {
u = queue[front++];
for (i = 0; i < n; i++) {
if (adj_matrix[u][i] && !visited[i]) {
visited[i] = 1;
printf("%d ", i);
queue[rear++] = i;
}
}
}
}
int main()
{
int n, i, j;
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &adj_matrix[i][j]);
}
}
printf("BFS traversal: ");
for (i = 0; i < n; i++) {
visited[i] = 0;
}
for (i = 0; i < n; i++) {
if (!visited[i]) {
bfs(i, n);
}
}
printf("\n");
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)