用C或C++语言编写一个完整代码,用结构体类型描述图的存储结构,编写具体函数实现对无向图或有向图进行DFS(深度优先遍历)和BFS(广度优先遍历)等基本操作,在输入栏输入一个随机图,并输出其DFS和BFS运行结果。
时间: 2024-05-10 17:15:21 浏览: 94
以下是一个基于邻接表存储图的C语言代码,实现了深度优先遍历和广度优先遍历:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 顶点结构体
typedef struct Vertex {
int data; // 顶点数据
struct Edge* first_edge; // 指向第一条依附于该顶点的边的指针
} Vertex;
// 边结构体
typedef struct Edge {
int adjvex; // 边指向的顶点的下标
struct Edge* next_edge; // 指向下一条依附于同一顶点的边的指针
} Edge;
// 图结构体
typedef struct Graph {
Vertex vertex[MAX_VERTEX_NUM]; // 顶点数组
int vertex_num; // 顶点数
int edge_num; // 边数
} Graph;
// 初始化图
void init_graph(Graph* graph, int vertex_num) {
graph->vertex_num = vertex_num;
graph->edge_num = 0;
for (int i = 0; i < vertex_num; i++) {
graph->vertex[i].data = i;
graph->vertex[i].first_edge = NULL;
}
}
// 添加边
void add_edge(Graph* graph, int start, int end) {
Edge* new_edge = (Edge*) malloc(sizeof(Edge));
new_edge->adjvex = end;
new_edge->next_edge = graph->vertex[start].first_edge;
graph->vertex[start].first_edge = new_edge;
graph->edge_num++;
}
// 深度优先遍历
void dfs(Graph* graph, int vertex_index, int* visited) {
visited[vertex_index] = 1;
printf("%d ", graph->vertex[vertex_index].data);
Edge* edge = graph->vertex[vertex_index].first_edge;
while (edge != NULL) {
if (!visited[edge->adjvex]) {
dfs(graph, edge->adjvex, visited);
}
edge = edge->next_edge;
}
}
// 广度优先遍历
void bfs(Graph* graph, int vertex_index, int* visited) {
int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
visited[vertex_index] = 1;
printf("%d ", graph->vertex[vertex_index].data);
queue[rear++] = vertex_index;
while (front < rear) {
int cur_vertex = queue[front++];
Edge* edge = graph->vertex[cur_vertex].first_edge;
while (edge != NULL) {
if (!visited[edge->adjvex]) {
visited[edge->adjvex] = 1;
printf("%d ", graph->vertex[edge->adjvex].data);
queue[rear++] = edge->adjvex;
}
edge = edge->next_edge;
}
}
}
// 打印图
void print_graph(Graph* graph) {
printf("Graph:\n");
for (int i = 0; i < graph->vertex_num; i++) {
printf("%d: ", graph->vertex[i].data);
Edge* edge = graph->vertex[i].first_edge;
while (edge != NULL) {
printf("%d ", graph->vertex[edge->adjvex].data);
edge = edge->next_edge;
}
printf("\n");
}
}
int main() {
Graph graph;
int vertex_num, edge_num, start_vertex;
printf("Input vertex num and edge num: ");
scanf("%d %d", &vertex_num, &edge_num);
init_graph(&graph, vertex_num);
for (int i = 0; i < edge_num; i++) {
int start, end;
printf("Input edge (start end): ");
scanf("%d %d", &start, &end);
add_edge(&graph, start, end);
}
print_graph(&graph);
printf("Input start vertex: ");
scanf("%d", &start_vertex);
int visited[MAX_VERTEX_NUM] = {0};
printf("DFS: ");
dfs(&graph, start_vertex, visited);
printf("\n");
for (int i = 0; i < vertex_num; i++) {
visited[i] = 0;
}
printf("BFS: ");
bfs(&graph, start_vertex, visited);
printf("\n");
return 0;
}
```
可以通过输入顶点数和边数以及每条边的起点和终点构造一个图,然后输入起始顶点,输出该顶点为起点的深度优先遍历和广度优先遍历结果。
阅读全文