实现图的广度优先遍历（BFS）和深度优先遍历（DFS）
C语言中实现图的广度优先遍历（BFS）和深度优先遍历（DFS）通常涉及到使用队列和栈数据结构。以下是使用邻接表表示图的BFS和DFS的简单示例：
```c
#include <stdio.h>
#include <stdlib.h>
// 定义图的节点结构
typedef struct Node {
int data;
struct Node* next;
} Node;
// 定义图的结构
typedef struct Graph {
int numVertices;
Node** adjLists;
int* visited;
} Graph;
// 创建一个新的节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 添加边到图中
void addEdge(Graph* graph, int src, int dest) {
// 添加从src到dest的边
Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
}
// 创建图
Graph* createGraph(int vertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->numVertices = vertices;
graph->adjLists = (Node**)malloc(vertices * sizeof(Node*));
graph->visited = (int*)malloc(vertices * sizeof(int));
for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
// 打印图
void printGraph(Graph* graph) {
for (int v = 0; v < graph->numVertices; v++) {
Node* temp = graph->adjLists[v];
printf("\n Adjacency list of vertex %d\n head ", v);
while (temp) {
printf("-> %d", temp->data);
temp = temp->next;
}
printf("\n");
}
}
// 队列节点
typedef struct QueueNode {
int data;
struct QueueNode* next;
} QueueNode;
// 队列
typedef struct Queue {
QueueNode *front, *rear;
} Queue;
// 创建队列
Queue* createQueue() {
Queue* q = (Queue*)malloc(sizeof(Queue));
q->front = q->rear = NULL;
return q;
}
// 入队
void enqueue(Queue* q, int data) {
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->data = data;
newNode->next = NULL;
if (q->rear == NULL) {
q->front = q->rear = newNode;
return;
}
q->rear->next = newNode;
q->rear = newNode;
}
// 出队
int dequeue(Queue* q) {
if (q->front == NULL) return -1;
QueueNode* temp = q->front;
int data = temp->data;
q->front = q->front->next;
if (q->front == NULL) q->rear = NULL;
free(temp);
return data;
}
// 检查队列是否为空
int isEmpty(Queue* q) {
return q->front == NULL;
}
// 广度优先遍历
void BFS(Graph* graph, int startVertex) {
Queue* q = createQueue();
graph->visited[startVertex] = 1;
enqueue(q, startVertex);
while (!isEmpty(q)) {
int currentVertex = dequeue(q);
printf("Visited %d\n", currentVertex);
Node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->data;
if (graph->visited[adjVertex] == 0) {
graph->visited[adjVertex] = 1;
enqueue(q, adjVertex);
}
temp = temp->next;
}
}
}
// 栈节点
typedef struct StackNode {
int data;
struct StackNode* next;
} StackNode;
// 栈
typedef struct Stack {
StackNode *top;
} Stack;
// 创建栈
Stack* createStack() {
Stack* s = (Stack*)malloc(sizeof(Stack));
s->top = NULL;
return s;
}
// 压栈
void push(Stack* s, int data) {
StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
newNode->data = data;
newNode->next = s->top;
s->top = newNode;
}
// 弹栈
int pop(Stack* s) {
if (s->top == NULL) return -1;
StackNode* temp = s->top;
int data = temp->data;
s->top = s->top->next;
free(temp);
return data;
}
// 检查栈是否为空
int isEmptyStack(Stack* s) {
return s->top == NULL;
}
// 深度优先遍历
void DFS(Graph* graph, int startVertex) {
Stack* s = createStack();
graph->visited[startVertex] = 1;
push(s, startVertex);
while (!isEmptyStack(s)) {
int currentVertex = pop(s);
printf("Visited %d\n", currentVertex);
Node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->data;
if (graph->visited[adjVertex] == 0) {
graph->visited[adjVertex] = 1;
push(s, adjVertex);
}
temp = temp->next;
}
}
}
int main() {
// 创建图示例
Graph* graph = createGraph(4);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
// 打印图
printGraph(graph);
// 广度优先遍历
printf("BFS starting from vertex 0:\n");
BFS(graph, 0);
// 深度优先遍历
printf("DFS starting from vertex 0:\n");
DFS(graph, 0);
// 释放图内存
for (int i = 0; i < graph->numVertices; i++) {
Node* temp = graph->adjLists[i];
while (temp) {
Node* toDelete = temp;
temp = temp->next;
free(toDelete);
}
}
free(graph->adjLists);
free(graph->visited);
free(graph);
return 0;
}
```
这段代码首先定义了图的数据结构和基本操作，然后实现了BFS和DFS算法。在`main`函数中，创建了一个简单的图，并进行了BFS和DFS遍历。请注意，这个示例代码没有进行错误检查，例如内存分配失败，这在实际应用中是必要的。