写完整代码,实现建立无向图邻接表存储结构,输出深度和宽度优先遍历顶点访问次序。
时间: 2024-12-21 15:24:04 浏览: 7
首先,我们需要定义一个图的数据结构表示邻接表,以及用于深度优先搜索(DFS)和广度优先搜索(BFS)的方法。以下是一个简单的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构
typedef struct Node {
int value; // 节点值
struct Node* next; // 邻接列表中的下一个节点指针
} Node;
// 创建新节点
Node* create_node(int val) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->value = val;
newNode->next = NULL;
return newNode;
}
// 添加边到邻接表
void add_edge(Node** adj_list, int src, int dest) {
Node* new_edge = create_node(dest);
new_edge->next = (*adj_list)[src];
(*adj_list)[src] = new_edge;
}
// 深度优先遍历
void dfs(Node** adj_list, int start, int visited[], int level) {
visited[start] = 1;
printf("%d ", start + 1); // 输出顶点编号
for (Node* node = (*adj_list)[start]; node != NULL; node = node->next) {
if (!visited[node->value]) {
dfs(adj_list, node->value, visited, level + 1);
}
}
}
// 广度优先遍历
void bfs(Node** adj_list, int start, int visited[]) {
int queue[100], front = -1, rear = -1;
visited[start] = 1;
queue[++rear] = start;
while (front < rear) {
int curr = queue[++front];
printf("%d ", curr + 1); // 输出顶点编号
for (Node* node = (*adj_list)[curr]; node != NULL; node = node->next) {
if (!visited[node->value]) {
visited[node->value] = 1;
queue[++rear] = node->value;
}
}
}
}
int main() {
int num_vertices; // 图的顶点数
printf("Enter number of vertices: ");
scanf("%d", &num_vertices);
// 初始化邻接表,假设为完全图
Node** adj_list = (Node**)malloc(num_vertices * sizeof(Node*));
for (int i = 0; i < num_vertices; ++i) {
adj_list[i] = NULL;
}
// 假设添加了所有可能的边
for (int i = 0; i < num_vertices; ++i) {
for (int j = i+1; j < num_vertices; ++j) {
add_edge(adj_list, i, j);
add_edge(adj_list, j, i); // 无向图,双向连接
}
}
// 深度优先搜索
printf("\nDepth First Traversal:\n");
int visited[num_vertices] = {0};
dfs(adj_list, 0, visited, 0);
// 广度优先搜索
printf("\nBreadth First Traversal:\n");
memset(visited, 0, sizeof(visited));
bfs(adj_list, 0, visited);
return 0;
}
```
在这个例子中,我们使用邻接表存储了一个无向图,然后分别实现了深度优先搜索和广度优先搜索。请注意,这个程序没有处理用户输入边的情况,所以你需要自己提供一个图。
阅读全文