数据结构与算法-图论-DFS/BFS

图搜索算法在数据结构与算法领域中非常关键，用于在图形数据结构中搜索节点或路径。图是由节点（也称为顶点）以及连接这些节点的边组成的。在本文中，我们将详细探讨两种基础的图搜索算法：深度优先搜索（DFS）和广度优先搜索（BFS），并提供相应的C语言代码示例。

1.深度优先搜索（DFS）

深度优先搜索（DFS）是一种遍历或搜索树或图的算法。DFS 探索尽可能深的分支路径，直到无法继续，然后回溯以探索未被访问的路径。

特点

  • 使用栈实现，可以是显式的数据结构栈，或者利用递归调用的隐式栈。
  • 常用于路径搜索，解决连通性问题和排序问题。

C 语言代码示例

假设图以邻接表形式给出，这里使用结构体和指针来定义图的结构。

实现一个完整的深度优先搜索（DFS）算法，我们需要添加图的创建、边的添加以及DFS本身的实现。以下代码段将完成这些部分，实现图的创建、添加边，并利用DFS遍历图：

#include <stdio.h>
#include <stdlib.h>

// 定义图的节点
typedef struct node {
    int vertex;
    struct node* next;
} Node;

// 定义图结构
typedef struct {
    int numVertices;
    Node** adjLists;
    int* visited;
} Graph;

// 创建节点
Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->visited = malloc(vertices * sizeof(int));

    int i;
    for (i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    // 添加从src到dest的边
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 由于是无向图，添加从dest到src的边
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 深度优先搜索实现
void DFS(Graph* graph, int vertex) {
    Node* adjList = graph->adjLists[vertex];
    Node* temp = adjList;

    graph->visited[vertex] = 1;
    printf("已访问 %d\n", vertex);

    while (temp != NULL) {
        int connectedVertex = temp->vertex;
        if (graph->visited[connectedVertex] == 0) {
            DFS(graph, connectedVertex);
        }
        temp = temp->next;
    }
}

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 4);
    addEdge(graph, 3, 5);
    addEdge(graph, 4, 5);

    DFS(graph, 0);  // 从顶点0开始深度优先搜索

    return 0;
}

代码说明

  1. 图的结构：使用邻接表来表示图，其中每个节点包含顶点编号和指向下一个邻接顶点的指针。
  2. 创建图和节点：提供函数来创建图和其节点。
  3. 添加边：因为是无向图，所以每添加一个方向的边时，也要添加反方向的边。
  4. DFS函数：使用递归实现深度优先搜索。开始时，标记当前节点为已访问，并递归地访问所有未被访问的邻接节点。

这段代码能够遍历给定图的所有顶点，显示每个访问的顶点。这是深度优先搜索常见的用法，可以用于检测图的连通性、查找图中的路径等。

2. 广度优先搜索（BFS）

广度优先搜索（BFS）是另一种图的遍历算法，它从根节点开始，逐层遍历图中的所有节点，先访问近邻节点，再访问更远的节点。

特点

  • 使用队列实现。
  • 常用于找到最短路径或任何层次遍历的场景。

C 语言代码示例

基于上面的图结构，我们可以实现 BFS：

以下是完整的广度优先搜索（BFS）的C语言实现，包括定义图结构、队列的操作函数（入队、出队、判断是否为空）以及广度优先搜索的具体实现。我们将继续从之前的代码段扩展，完善队列的操作和图的遍历逻辑。

C 语言代码示例

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 定义队列结构
typedef struct queue {
    int items[100];
    int front;
    int rear;
} Queue;

// 创建队列
Queue* createQueue() {
    Queue* q = malloc(sizeof(Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

// 检查队列是否为空
bool isEmpty(Queue* q) {
    if(q->rear == -1)
        return true;
    else
        return false;
}

// 入队
void enqueue(Queue* q, int value) {
    if(q->rear == 99)
        printf("队列已满.\n");
    else {
        if(q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

// 出队
int dequeue(Queue* q) {
    int item;
    if(isEmpty(q)) {
        printf("队列为空.\n");
        item = -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if(q->front > q->rear) {
            q->front = -1;
            q->rear = -1;
        }
    }
    return item;
}

typedef struct node {
    int vertex;
    struct node* next;
} Node;

typedef struct {
    int numVertices;
    Node** adjLists;
    int* visited;
} Graph;

Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->visited = malloc(vertices * sizeof(int));
    
    for(int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void BFS(Graph* graph, int startVertex) {
    Queue* queue = createQueue();
    
    graph->visited[startVertex] = 1;
    enqueue(queue, startVertex);
    
    while(!isEmpty(queue)) {
        int currentVertex = dequeue(queue);
        printf("已访问 %d\n", currentVertex);
        
        Node* temp = graph->adjLists[currentVertex];
        
        while(temp) {
            int adjVertex = temp->vertex;
            
            if(graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                enqueue(queue, adjVertex);
            }
            temp = temp->next;
        }
    }
}

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 5);

    BFS(graph, 0);

    return 0;
}

说明

这段代码首先定义了一个图和一个队列，然后实现了广度优先搜索（BFS）。在BFS中，我们首先将起始顶点放入队列，并标记为已访问。然后，我们依次从队列中取出顶点，并访问其所有未访问的邻接点，将它们加入队列并标记为已访问。这个过程重复进行，直到队列为空。通过这种方式，BFS可以按层次访问图中的所有顶点。

在实际生活应用中，深度优先搜索（DFS）可用于解决如解迷宫问题。这个案例使用深度优先搜索算法探索从迷宫的入口到出口的路径。迷宫可以视为一个由格子组成的网格，其中一些格子是可通过的，而其他格子则可能被墙阻挡。

3. C 语言实现 DFS 解迷宫

以下是用C语言实现的迷宫探索代码。我们将使用深度优先搜索来尝试每一条可能的路径，直到找到出口。如果找到出口，我们将打印出一条路径。

C语言代码示例

#include <stdio.h>
#include <stdbool.h>

#define ROW 5
#define COL 5

// 迷宫地图，0可走，1不可走
int maze[ROW][COL] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0}
};

// 访问标记
int visited[ROW][COL] = {0};

// 移动方向（上下左右）
int moveX[4] = {0, 0, -1, 1};
int moveY[4] = {-1, 1, 0, 0};

// 检查当前位置是否合法
bool isValid(int x, int y) {
    if (x < 0 || x >= ROW || y < 0 || y >= COL) return false;
    if (maze[x][y] == 1 || visited[x][y] == 1) return false;
    return true;
}

// DFS搜索迷宫路径
bool dfs(int x, int y) {
    // 如果达到右下角出口
    if (x == ROW - 1 && y == COL - 1) {
        visited[x][y] = 1;
        return true;
    }

    // 检查当前位置是否可走
    if (isValid(x, y)) {
        visited[x][y] = 1;  // 标记为已访问

        // 尝试每一个方向
        for (int i = 0; i < 4; i++) {
            int nextX = x + moveX[i];
            int nextY = y + moveY[i];
            if (dfs(nextX, nextY)) return true;
        }

        visited[x][y] = 0;  // 回溯，标记为未访问
    }
    return false;
}

void printPath() {
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            printf("%d ", visited[i][j]);
        }
        printf("\n");
    }
}

int main() {
    if (dfs(0, 0)) {
        printf("找到了通往出口的路径:\n");
        printPath();
    } else {
        printf("没有找到通往出口的路径.\n");
    }
    return 0;
}

说明

上述代码定义了一个5x5的迷宫和一个相应的访问数组。DFS函数尝试从入口（0,0）开始探索，使用一个递归方法来尝试所有可能的路径。如果找到一条到达出口（ROW-1, COL-1）的路径，该函数将返回true，并通过visited数组标记路径。

此代码还包括一个printPath函数，用于打印出到达终点的路径。这个解决方案可以直接应用于任何通过二维网格模拟的迷宫探索问题，非常适合需要路径查找的

4.C 语言实现 BFS 解迷宫

在生活中应用图搜索算法的一个常见场景是地图导航系统，如何在城市道路网中找到两点之间的最短路径。在这个实例中，我们将使用广度优先搜索（BFS）来模拟在城市的道路网络中寻找从一个地点到另一个地点的最短路径的情况。

在C语言中实现这样的模型，我们首先需要设置一个城市的道路网络图，然后使用 BFS 算法来找出两点之间的最短路径。

定义城市地图道路网络

我们首先定义一个图结构来表示城市中的路口（节点）和道路（边），然后实现 BFS 搜索找到最短路径。

C 语言代码示例

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct node {
    int vertex;
    struct node* next;
} Node;

typedef struct {
    int numVertices;
    Node** adjLists;
    int* visited;
    int* distance;  // 用于存储起点到每个顶点的距离
} Graph;

Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return 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));
    graph->distance = (int*)malloc(vertices * sizeof(int));

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
        graph->distance[i] = INT_MAX;
    }
    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void BFS(Graph* graph, int startVertex) {
    int queue[1000], front = 0, rear = -1;

    graph->visited[startVertex] = 1;
    graph->distance[startVertex] = 0;
    queue[++rear] = startVertex;

    while (front <= rear) {
        int currentVertex = queue[front++];
        Node* temp = graph->adjLists[currentVertex];

        while (temp) {
            int adjVertex = temp->vertex;

            if (graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                graph->distance[adjVertex] = graph->distance[currentVertex] + 1; // 计算距离
                queue[++rear] = adjVertex;
            }
            temp = temp->next;
        }
    }
}

int main() {
    Graph* graph = createGraph(8); // 假设城市有8个重要交叉路口
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 3);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 5);
    addEdge(graph, 3, 4);
    addEdge(graph, 4, 5);
    addEdge(graph, 5, 6);
    addEdge(graph, 6, 7);

    BFS(graph, 0);  // 从路口0开始搜索

    printf("从0到7的最短路径是%d步.\n", graph->distance[7]);

    return 0;
}

说明

在上面的代码中，我们构建了一个模拟的城市道路网络，并通过广度优先搜索算法找到从节点 0 到节点 7 的最短路径。每个节点代表一个路口，每条边代表两个路口之间的直接道路。distance 数组用于存储从起始点到图中每个其他顶点的最短路径长度。

这种类型的实现在现实世界的导航

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/579452.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

TCP/IP协议族中的TCP（二）：解析其关键特性与机制

TCP/IP协议族中的TCP（二）：解析其关键特性与机制

⭐小白苦学IT的博客主页⭐ ⭐初学者必看&#xff1a;Linux操作系统入门⭐ ⭐代码仓库&#xff1a;Linux代码仓库⭐ ❤关注我一起讨论和学习Linux系统 滑动窗口 在前面我们讨论了确认应答策略, 对每一个发送的数据段, 都要给一个ACK确认应答. 收到ACK后再发送下一个数据段.这样…
阅读更多...
【Python】#5 基础文件IO详解

【Python】#5 基础文件IO详解

文章目录 一、文件概述二、文件操作1.文件的打开与关闭2. 文件的读写2.1 读取2.2 写入tips:CSV与JSON文件 一些文件操作小实验《清明》文本写入与读取《红楼梦》人物出现统计&#xff08;部分文本&#xff09; 一、文件概述 文件是数据的集合和抽象&#xff0c;类似&#xff0…
阅读更多...
如何增强交友、婚恋平台、金融等平台的安全性

如何增强交友、婚恋平台、金融等平台的安全性

运营商二要素核验是一种数字身份验证方法&#xff0c;主要使用用户的手机号码和姓名作为核验要素。这两个要素被认为是最基本的用户身份信息&#xff0c;通过运营商的数据库来核实其真实性。 在实际操作中&#xff0c;用户需要提供手机号码和姓名进行验证。应用系统会调用接口…
阅读更多...
全面了解俄罗斯的VK开户和Yandex投放及内容运营

全面了解俄罗斯的VK开户和Yandex投放及内容运营

俄罗斯的VKontakte&#xff08;简称VK&#xff09;和Yandex是两个重要的在线平台&#xff0c;对于希望在俄罗斯市场进行推广的企业来说&#xff0c;了解如何在这些平台上开户和投放广告以及内容运营是非常关键的。 俄罗斯vk广告如何开户&#xff1f; 通过上海上弦进行俄罗斯V…
阅读更多...
手写一个RNN前向传播以及反向传播

手写一个RNN前向传播以及反向传播

前向传播 根据公式 st tanh (Uxt Wst-1 ba) ot softmax(Vst by ) m 3 词的个数 n 5 import numpy as np import tensorflow as tf # 单个cell 的前向传播过程 # 两个输入&#xff0c;x_t&#xff0c;s_prev,parameters def rnn_cell_forward(x_t,s_prev,parameter…
阅读更多...
每日OJ题_DFS回溯剪枝⑧_力扣494. 目标和

每日OJ题_DFS回溯剪枝⑧_力扣494. 目标和

目录 力扣494. 目标和 解析代码&#xff08;path设置成全局&#xff09; 解析代码&#xff08;path设置全局&#xff09; 力扣494. 目标和 494. 目标和 难度 中等 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 或 - &#xff0c;然后串联…
阅读更多...
SpringBoot + Vue实现Github第三方登录

SpringBoot + Vue实现Github第三方登录

前言&#xff1a;毕业设计终于好了&#xff0c;希望能有空多写几篇 1. 获取Github账号的Client ID和Client secrets 首先点击这个链接进入Github的OAuth Apps页面&#xff0c;页面展示如下&#xff1a; 之后我们可以创建一个新的apps: 填写资料&#xff1a; 创建之后就可以获…
阅读更多...
WebGIS面试题（第六期）-GeoServer

WebGIS面试题（第六期）-GeoServer

WebGIS面试题&#xff08;第六期&#xff09; 以下题目仅为部分题目&#xff0c;全部题目在公众号 {GISer世界} &#xff0c;答案仅供参考!!! 因为本人之前做过相关项目用到了GeoServer&#xff0c;因此在简历上写了熟悉GeoServer。所以在相关面试中都有问到&#xff0c;所以我…
阅读更多...
【项目】仿muduo库One Thread One Loop式主从Reactor模型实现高并发服务器（Http板块）

【项目】仿muduo库One Thread One Loop式主从Reactor模型实现高并发服务器（Http板块）

【项目】仿muduo库One Thread One Loop式主从Reactor模型实现高并发服务器&#xff08;Http板块&#xff09; 一、思路图二、Util板块1、Splite板块&#xff08;分词&#xff09;&#xff08;1&#xff09;代码&#xff08;2&#xff09;测试及测试结果i、第一种测试ii、第二种…
阅读更多...
[论文阅读] 3D感知相关论文简单摘要

[论文阅读] 3D感知相关论文简单摘要

Adaptive Fusion of Single-View and Multi-View Depth for Autonomous Driving 提出了一个单、多视图融合深度估计系统&#xff0c;它自适应地集成了高置信度的单视图和多视图结果 动态选择两个分支之间的高置信度区域执行融合 提出了一个双分支网络&#xff0c;即一个以单…
阅读更多...
查看笔记本电池容量/健康状态

查看笔记本电池容量/健康状态

1. 打开命令行提示符 快捷键“win R”后输入“cmd” 2. 在命令提示符中输入命令 “powercfg /batteryreport" 并回车 3. 查看文件 最后就可以看到笔记本的电池使用报告了
阅读更多...
Promises: JavaScript异步编程的救星

Promises: JavaScript异步编程的救星

Promises: JavaScript异步编程的救星 Promises&#xff08;承诺&#xff09;是JavaScript中处理异步操作的一种机制&#xff0c;它提供了一种更优雅和可读性更高的方式来处理异步代码。Promises的实现原理基于一种称为"Promise/A"规范的约定&#xff0c;该规范定义了…
阅读更多...
[蓝桥杯2024]-Reverse:rc4解析（对称密码rc4）

[蓝桥杯2024]-Reverse:rc4解析（对称密码rc4）

无壳 查看ida 这里应该运行就可以得flag&#xff0c;但是这个程序不能直接点击运行 按照伪代码写exp 完整exp&#xff1a; keylist(gamelab) content[0xB6,0x42,0xB7,0xFC,0xF0,0xA2,0x5E,0xA9,0x3D,0x29,0x36,0x1F,0x54,0x29,0x72,0xA8, 0x63,0x32,0xF2,0x44,0x8B,0x85,0x…
阅读更多...
visual studio2022,开发CMake项目添加rabbitmq库，连接到远程计算机并进行开发于调试

visual studio2022,开发CMake项目添加rabbitmq库，连接到远程计算机并进行开发于调试

1.打开visual studio installer 。安装“用于 Windows 的 C CMake 工具” 2.新建CMake项目 3.点击VS的“工具”—>"选项“—>“跨平台”—>”连接管理器“,添加远程计算机。用来将VS编辑的代码传到服务器进行编译–连接—运行&#xff08;调试&#xff09;。 …
阅读更多...
BIO、NIO与AIO

BIO、NIO与AIO

一 BIO 同步并阻塞(传统阻塞型)&#xff0c;服务器实现模式为一个连接一个线程&#xff0c;即客户端有连接请求时服务器端就需要启动一个线程进行处理. BIO&#xff08;Blocking I/O&#xff0c;阻塞I/O&#xff09;模式是一种网络编程中的I/O处理模式。在BIO模式中&#xf…
阅读更多...
鸿蒙内核源码分析(任务调度篇) | 任务是内核调度的单元

鸿蒙内核源码分析(任务调度篇) | 任务是内核调度的单元

任务即线程 在鸿蒙内核中&#xff0c;广义上可理解为一个任务就是一个线程 官方是怎么描述线程的 基本概念 从系统的角度看&#xff0c;线程是竞争系统资源的最小运行单元。线程可以使用或等待CPU、使用内存空间等系统资源&#xff0c;并独立于其它线程运行。 鸿蒙内核每个…
阅读更多...
[蓝桥杯2024]-PWN:fd解析（命令符转义，标准输出重定向）

[蓝桥杯2024]-PWN:fd解析（命令符转义，标准输出重定向）

查看保护 查看ida 这里有一次栈溢出&#xff0c;并且题目给了我们system函数。 这里的知识点没有那么复杂 完整exp&#xff1a; from pwn import* pprocess(./pwn) pop_rdi0x400933 info0x601090 system0x400778payloadb"ca\\t flag 1>&2" print(len(paylo…
阅读更多...
SAP PP学习笔记07 - 作业手顺（工艺路线Routing）

SAP PP学习笔记07 - 作业手顺（工艺路线Routing）

上一章讲了BOM的相关知识。 SAP PP学习笔记07 - 简单BOM&#xff0c;派生BOM&#xff0c;多重BOM&#xff0c;批量修改工具 CEWB_sap半成品有多个bom-CSDN博客 本章来讲作业手顺&#xff08;工艺路线Routing&#xff09;的相关知识。 1&#xff0c;作业手顺(工艺路线 Routing…
阅读更多...
四、线段、矩形、圆、椭圆、自定义多边形、边缘轮廓和文本绘制（OpenCvSharp）

四、线段、矩形、圆、椭圆、自定义多边形、边缘轮廓和文本绘制（OpenCvSharp）

功能实现&#xff1a; 对指定图片上进行绘制线段、矩形、圆、椭圆、自定义多边形、边缘轮廓以及自定义文本 一、布局 用到了一个pictureBox和八个button 二、引入命名空间 using System; using System.Collections.Generic; using System.Drawing; using System.Windows.F…
阅读更多...
Dockerfile镜像构建实战

Dockerfile镜像构建实战

一、构建Apache镜像 cd /opt/ #建立工作目录 mkdir /opt/apache cd apache/vim Dockerfile #基于的基础镜像 FROM centos:7 #维护镜像的用户信息 MAINTAINER this is apache image <cyj> #镜像操作指令安装Apache软件 RUN yum install -y httpd #开启80端口 EXPOSE 80 #…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站