用c语言针对给定的无向图,实现图的深度优先遍历和广度优先遍历算法,并输出相应遍历的结果
时间: 2023-11-22 20:53:25 浏览: 48
好的,下面是使用C语言实现图的深度优先遍历和广度优先遍历算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
typedef struct edge_node {
int adjvex; // 邻接点
struct edge_node* next; // 指向下一个邻接点的指针
} EdgeNode;
typedef struct vertex_node {
int data; // 顶点信息
EdgeNode* first_edge; // 指向第一个邻接点的指针
} VertexNode;
typedef struct {
VertexNode vertex_list[MAX_VERTEX_NUM]; // 顶点数组
int vertex_num; // 顶点数目
int edge_num; // 边数目
} Graph;
// 初始化图
void init_graph(Graph* G) {
int i;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertex_list[i].data = 0;
G->vertex_list[i].first_edge = NULL;
}
G->vertex_num = 0;
G->edge_num = 0;
}
// 添加边
void add_edge(Graph* G, int v1, int v2) {
EdgeNode* p, * q;
p = (EdgeNode*)malloc(sizeof(EdgeNode));
p->adjvex = v2;
p->next = G->vertex_list[v1].first_edge;
G->vertex_list[v1].first_edge = p;
q = (EdgeNode*)malloc(sizeof(EdgeNode));
q->adjvex = v1;
q->next = G->vertex_list[v2].first_edge;
G->vertex_list[v2].first_edge = q;
G->edge_num++;
}
// 深度优先遍历
void DFS(Graph* G, int v, int* visited) {
printf("%d ", G->vertex_list[v].data);
visited[v] = 1;
EdgeNode* p = G->vertex_list[v].first_edge;
while (p) {
int w = p->adjvex;
if (!visited[w]) {
DFS(G, w, visited);
}
p = p->next;
}
}
// 广度优先遍历
void BFS(Graph* G, int v, int* visited) {
int queue[MAX_VERTEX_NUM];
int front = 0, rear = 0;
printf("%d ", G->vertex_list[v].data);
visited[v] = 1;
queue[rear++] = v;
while (front < rear) {
int u = queue[front++];
EdgeNode* p = G->vertex_list[u].first_edge;
while (p) {
int w = p->adjvex;
if (!visited[w]) {
printf("%d ", G->vertex_list[w].data);
visited[w] = 1;
queue[rear++] = w;
}
p = p->next;
}
}
}
int main() {
Graph G;
init_graph(&G);
// 添加顶点
int vertex_data[] = { 1, 2, 3, 4, 5 };
int i;
for (i = 0; i < sizeof(vertex_data) / sizeof(int); i++) {
G.vertex_list[i].data = vertex_data[i];
G.vertex_num++;
}
// 添加边
add_edge(&G, 0, 1);
add_edge(&G, 0, 3);
add_edge(&G, 1, 2);
add_edge(&G, 1, 4);
add_edge(&G, 2, 4);
add_edge(&G, 3, 4);
// 深度优先遍历
int visited[MAX_VERTEX_NUM] = { 0 };
printf("深度优先遍历结果:");
for (i = 0; i < G.vertex_num; i++) {
if (!visited[i]) {
DFS(&G, i, visited);
}
}
printf("\n");
// 广度优先遍历
for (i = 0; i < G.vertex_num; i++) {
visited[i] = 0;
}
printf("广度优先遍历结果:");
for (i = 0; i < G.vertex_num; i++) {
if (!visited[i]) {
BFS(&G, i, visited);
}
}
printf("\n");
return 0;
}
```
上述代码中,我们定义了一个 `Graph` 类型的结构体,其中包含了顶点数组、顶点数目和边数目等信息。我们通过 `init_graph` 函数来初始化图,通过 `add_edge` 函数来添加边。在深度优先遍历和广度优先遍历函数中,我们通过递归和队列来实现遍历。最后,我们通过 `main` 函数来测试我们的代码,并输出相应遍历的结果。