深入探索图算法:用C语言实现BFS和DFS
图算法是计算机科学中一个重要且有趣的领域,它们在解决许多现实世界的问题时发挥着关键作用。本篇博客将介绍两种常见的图算法:广度优先搜索(BFS)和深度优先搜索(DFS),并提供在C语言中的实现示例。
广度优先搜索(BFS)
广度优先搜索是一种用于图遍历的算法,它从起始节点开始逐层遍历图的节点,直到找到目标节点或遍历完整个图。下面是BFS算法的C语言实现示例:
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct {
int data[MAX_VERTICES];
int front, rear;
} Queue;
void initQueue(Queue *q) {
q->front = q->rear = -1;
}
bool isEmpty(Queue *q) {
return q->front == -1;
}
void enqueue(Queue *q, int value) {
if (isEmpty(q)) {
q->front = q->rear = 0;
} else {
q->rear++;
}
q->data[q->rear] = value;
}
int dequeue(Queue *q) {
int value = q->data[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1;
} else {
q->front++;
}
return value;
}
void BFS(int graph[MAX_VERTICES][MAX_VERTICES], int vertices, int start) {
bool visited[MAX_VERTICES] = { false };
Queue q;
initQueue(&q);
visited[start] = true;
enqueue(&q, start);
while (!isEmpty(&q)) {
int vertex = dequeue(&q);
printf("%d ", vertex);
for (int i = 0; i < vertices; i++) {
if (graph[vertex][i] && !visited[i]) {
visited[i] = true;
enqueue(&q, i);
}
}
}
}
int main() {
int vertices, edges, start;
printf("Enter the number of vertices: ");
scanf("%d", &vertices);
printf("Enter the number of edges: ");
scanf("%d", &edges);
int graph[MAX_VERTICES][MAX_VERTICES] = { 0 };
printf("Enter the edges (format: u v):\n");
for (int i = 0; i < edges; i++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u][v] = graph[v][u] = 1;
}
printf("Enter the starting vertex: ");
scanf("%d", &start);
printf("BFS traversal starting from vertex %d: ", start);
BFS(graph, vertices, start);
return 0;
}
深度优先搜索(DFS)
深度优先搜索是另一种图遍历算法,它沿着图的深度尽可能远地探索节点,然后回溯到之前的节点继续探索。下面是DFS算法的C语言实现示例:
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct {
int data[MAX_VERTICES];
int top;
} Stack;
void initStack(Stack *s) {
s->top = -1;
}
bool isEmpty(Stack *s) {
return s->top == -1;
}
void push(Stack *s, int value) {
s->data[++s->top] = value;
}
int pop(Stack *s) {
return s->data[s->top--];
}
void DFS(int graph[MAX_VERTICES][MAX_VERTICES], int vertices, int vertex, bool visited[MAX_VERTICES]) {
printf("%d ", vertex);
visited[vertex] = true;
for (int i = 0; i < vertices; i++) {
if (graph[vertex][i] && !visited[i]) {
DFS(graph, vertices, i, visited);
}
}
}
int main() {
int vertices, edges, start;
printf("Enter the number of vertices: ");
scanf("%d", &vertices);
printf("Enter the number of edges: ");
scanf("%d", &edges);
int graph[MAX_VERTICES][MAX_VERTICES] = { 0 };
printf("Enter the edges (format: u v):\n");
for (int i = 0; i < edges; i++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u][v] = graph[v][u] = 1;
}
printf("Enter the starting vertex: ");
scanf("%d", &start);
bool visited[MAX_VERTICES] = { false };
printf("DFS traversal starting from vertex %d: ", start);
DFS(graph, vertices, start, visited);
return 0;
}
总结
本篇博客介绍了图算法中的两个重要概念:广度优先搜索(BFS)和深度优先搜索(DFS)。通过C语言实现的示例代码,您可以更好地理解这两种算法的工作原理和用途。图算法在社交网络分析、路径规划、游戏开发等领域具有广泛的应用,深入理解这些算法将有助于您解决各种实际问题。文章来源:https://www.toymoban.com/news/detail-654827.html
希望本文对您学习图算法和C语言编程有所帮助!如果您有任何问题或建议,请随时在评论区留言。文章来源地址https://www.toymoban.com/news/detail-654827.html
到了这里,关于深入探索图算法:用C语言实现BFS和DFS的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!