用C语言写一个图算法,以数组(邻接矩阵)或邻接表为存储结构,建立一个图,包括定义图的数组或邻接表存储表示,输出图G的深度优先序列,广度优先序列和邻接矩阵。
时间: 2023-11-19 21:05:56 浏览: 76
好的,以下是一个简单的图算法的C语言实现,使用邻接矩阵作为存储结构:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
int visited[MAX_VERTICES]; // 记录是否已经访问过
int adjacency_matrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int queue[MAX_VERTICES]; // 广度优先搜索需要使用的队列
int num_vertices = 0; // 图中顶点的数量
// 添加边
void add_edge(int start, int end) {
adjacency_matrix[start][end] = 1;
adjacency_matrix[end][start] = 1;
}
// 深度优先搜索
void dfs(int vertex) {
visited[vertex] = 1;
printf("%d ", vertex);
for (int i = 0; i < num_vertices; i++) {
if (adjacency_matrix[vertex][i] && !visited[i]) {
dfs(i);
}
}
}
// 广度优先搜索
void bfs(int vertex) {
int front = 0, rear = 0;
queue[rear++] = vertex;
visited[vertex] = 1;
while (front != rear) {
int v = queue[front++];
printf("%d ", v);
for (int i = 0; i < num_vertices; i++) {
if (adjacency_matrix[v][i] && !visited[i]) {
visited[i] = 1;
queue[rear++] = i;
}
}
}
}
int main() {
scanf("%d", &num_vertices);
int num_edges;
scanf("%d", &num_edges);
for (int i = 0; i < num_edges; i++) {
int start, end;
scanf("%d %d", &start, &end);
add_edge(start, end);
}
printf("邻接矩阵:\n");
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
printf("%d ", adjacency_matrix[i][j]);
}
printf("\n");
}
printf("深度优先序列:");
for (int i = 0; i < num_vertices; i++) {
visited[i] = 0;
}
for (int i = 0; i < num_vertices; i++) {
if (!visited[i]) {
dfs(i);
}
}
printf("\n");
printf("广度优先序列:");
for (int i = 0; i < num_vertices; i++) {
visited[i] = 0;
}
for (int i = 0; i < num_vertices; i++) {
if (!visited[i]) {
bfs(i);
}
}
printf("\n");
return 0;
}
```
使用邻接表作为存储结构的实现和上述代码类似,只需要修改存储结构和深度优先搜索、广度优先搜索的实现即可。
阅读全文
相关推荐
![txt](https://img-home.csdnimg.cn/images/20241231045021.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)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)