深入探索图算法:用C语言实现BFS和DFS

这篇具有很好参考价值的文章主要介绍了深入探索图算法:用C语言实现BFS和DFS。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

深入探索图算法:用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语言实现的示例代码,您可以更好地理解这两种算法的工作原理和用途。图算法在社交网络分析、路径规划、游戏开发等领域具有广泛的应用,深入理解这些算法将有助于您解决各种实际问题。

希望本文对您学习图算法和C语言编程有所帮助!如果您有任何问题或建议,请随时在评论区留言。文章来源地址https://www.toymoban.com/news/detail-654827.html

到了这里,关于深入探索图算法:用C语言实现BFS和DFS的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包