用C语言写一个图算法,以数组(邻接矩阵)或邻接表为存储结构,建立一个图,包括定义图的数组或邻接表存储表示,输出图G的深度优先序列或广度优先序列。
时间: 2023-11-27 20:54:32 浏览: 111
以下是一个使用邻接矩阵存储的图的深度优先搜索算法的C语言实现。
```c
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数量
int visited[MAX_VERTEX_NUM]; // 记录每个顶点是否被访问
int graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储图的邻接矩阵
int vertex_num, edge_num; // 顶点数量和边数量
// 深度优先遍历函数
void DFS(int v) {
visited[v] = 1;
printf("%d ", v); // 输出遍历的顶点
for (int i = 0; i < vertex_num; i++) {
if (graph[v][i] == 1 && visited[i] == 0) { // 如果顶点v与顶点i之间有边,并且顶点i没有被访问过
DFS(i); // 递归遍历顶点i
}
}
}
int main() {
printf("请输入顶点数和边数:");
scanf("%d%d", &vertex_num, &edge_num);
// 初始化邻接矩阵
for (int i = 0; i < vertex_num; i++) {
for (int j = 0; j < vertex_num; j++) {
graph[i][j] = 0;
}
}
// 读入边的信息,构建邻接矩阵
printf("请输入每条边连接的两个顶点:\n");
for (int i = 0; i < edge_num; i++) {
int v1, v2;
scanf("%d%d", &v1, &v2);
graph[v1][v2] = graph[v2][v1] = 1; // 无向图
}
// 深度优先遍历
printf("深度优先遍历序列为:");
for (int i = 0; i < vertex_num; i++) {
if (visited[i] == 0) { // 如果顶点i没有被访问过
DFS(i); // 从顶点i开始进行深度优先遍历
}
}
return 0;
}
```
使用类似的方式,也可以实现广度优先搜索算法。需要借助一个队列来记录待遍历的顶点。
阅读全文
相关推荐
![zip](https://img-home.csdnimg.cn/images/20241231045053.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)