用数据结构c语言语法写出用邻接表的存储结构创建一个如图2所示的图a和b,分别打印出这两个图的深度优先遍历和广度优先遍历的结点信息序列。
时间: 2024-12-24 13:37:33 浏览: 9
在C语言中,我们可以使用链表作为邻接表的存储结构来表示图。首先,我们需要定义节点结构体(Node),然后创建两个图结构体(Graph),每个节点包含一个指向前向邻居的指针数组。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构体
typedef struct Node {
int value;
struct Node* neighbors[5]; // 假设最多有5个邻居
} Node;
// 定义图结构体
typedef struct Graph {
Node** nodes;
int num_nodes;
int max_nodes;
} Graph;
// 创建图并添加节点
void create_graph(Graph* graph, int a[], int size) {
graph->nodes = (Node**)malloc(sizeof(Node*) * (graph->max_nodes + 1));
graph->num_nodes = 0;
for (int i = 0; i <= size; i++) {
if (!graph->nodes[i]) {
graph->nodes[i] = (Node*)malloc(sizeof(Node));
graph->nodes[i]->value = a[i];
graph->max_nodes = i;
}
if (i > 0) {
graph->nodes[a[i]]->neighbors[i - 1] = graph->nodes[i];
}
}
}
// 深度优先遍历
void dfs(Graph* graph, int node, int visited[]) {
printf("%d ", graph->nodes[node]->value);
visited[node] = 1;
for (int i = 0; i < graph->max_nodes && graph->nodes[node]->neighbors[i]; i++) {
if (!visited[graph->nodes[node]->neighbors[i]->value]) {
dfs(graph, graph->nodes[node]->neighbors[i]->value, visited);
}
}
}
// 广度优先遍历
void bfs(Graph* graph, int start_node) {
int visited[graph->max_nodes + 1] = {0};
int queue[graph->max_nodes + 1], front = 0, rear = 0;
queue[rear++] = start_node;
visited[start_node] = 1;
while (front < rear) {
int current_node = queue[front++];
printf("%d ", graph->nodes[current_node]->value);
for (int i = 0; i < graph->max_nodes && graph->nodes[current_node]->neighbors[i]; i++) {
if (!visited[graph->nodes[current_node]->neighbors[i]->value]) {
queue[rear++] = graph->nodes[current_node]->neighbors[i]->value;
visited[graph->nodes[current_node]->neighbors[i]->value] = 1;
}
}
}
}
// 打印图的DFS和BFS结果
void print_graph_dfs_bfs(Graph* graph_a, Graph* graph_b) {
printf("图a DFS 结果:\n");
dfs(graph_a, 0, NULL); // 图a的起始节点通常设为0
printf("\n图a BFS 结果:\n");
bfs(graph_a, 0); // 图a的起始节点同上
printf("\n图b DFS 结果:\n");
dfs(graph_b, 0, NULL);
printf("\n图b BFS 结果:\n");
bfs(graph_b, 0);
}
int main() {
// 初始化两个图的数据,这里仅举例子
int a[] = {0, 1, 2, 3, 4};
int b[] = {0, 5, 6, 7};
Graph graph_a, graph_b;
create_graph(&graph_a, a, sizeof(a) / sizeof(int));
create_graph(&graph_b, b, sizeof(b) / sizeof(int));
print_graph_dfs_bfs(&graph_a, &graph_b);
return 0;
}
```
这个程序首先创建了两个图`graph_a`和`graph_b`,然后分别用深度优先遍历(dfs)和广度优先遍历(bfs)算法打印它们的节点信息序列。注意,由于缺少具体的图结构数据,这只是一个基本框架,实际应用中需要替换`a[]`和`b[]`数组以构建真实的邻接表。运行这个程序,你应该能看到预期的节点访问顺序。
阅读全文