代码随想录算法训练营第五十五天|Day55 图论

ops/2024/11/24 15:47:21/

寻找存在的路径

https://www.programmercarl.com/kamacoder/0107.%E5%AF%BB%E6%89%BE%E5%AD%98%E5%9C%A8%E7%9A%84%E8%B7%AF%E5%BE%84.html

思路

#include <stdio.h>
#include <stdlib.h>#define MAX_NODES 101// 邻接表的节点结构
typedef struct Node {int vertex;struct Node* next;
} Node;// 图的邻接表
typedef struct Graph {Node* adjacencyList[MAX_NODES];
} Graph;// 初始化图
void initGraph(Graph* graph) {for (int i = 1; i < MAX_NODES; i++) {graph->adjacencyList[i] = NULL;}
}// 创建邻接表节点
Node* createNode(int vertex) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->vertex = vertex;newNode->next = NULL;return newNode;
}// 添加边
void addEdge(Graph* graph, int src, int dest) {// 添加从 src 到 dest 的边Node* newNode = createNode(dest);newNode->next = graph->adjacencyList[src];graph->adjacencyList[src] = newNode;// 添加从 dest 到 src 的边 (无向图)newNode = createNode(src);newNode->next = graph->adjacencyList[dest];graph->adjacencyList[dest] = newNode;
}// DFS 函数
int dfs(Graph* graph, int visited[], int current, int destination) {if (current == destination) {return 1; // 找到目标}visited[current] = 1; // 标记当前节点为已访问Node* temp = graph->adjacencyList[current];while (temp != NULL) {int vertex = temp->vertex;if (!visited[vertex]) { // 如果未访问,递归 DFSif (dfs(graph, visited, vertex, destination)) {return 1;}}temp = temp->next;}return 0; // 没有找到目标
}int main() {int n, m;scanf("%d %d", &n, &m); // 输入节点数和边数Graph graph;initGraph(&graph);// 输入边信息for (int i = 0; i < m; i++) {int s, t;scanf("%d %d", &s, &t);addEdge(&graph, s, t);}int source, destination;scanf("%d %d", &source, &destination); // 输入起点和终点int visited[MAX_NODES] = {0}; // 访问标记数组// 调用 DFS 检查路径if (dfs(&graph, visited, source, destination)) {printf("1\n"); // 存在路径} else {printf("0\n"); // 不存在路径}return 0;
}

学习反思

代码是一个使用邻接表实现的图的深度优先搜索算法。代码首先定义了邻接表的节点结构和图的结构。然后通过initGraph函数初始化图,createNode函数创建节点,addEdge函数添加边。接着定义了DFS函数,用于递归地进行深度优先搜索。在主函数中,首先读取节点数和边数,然后根据输入添加边信息。接着读取起点和终点,然后定义一个访问标记数组,最后调用DFS函数检查是否存在路径,并输出结果。这段代码使用了递归的深度优先搜索算法来检查图中是否存在路径。它通过访问标记数组来标记已经访问过的节点,避免重复访问。在DFS函数中,当当前节点等于目标节点时,返回1表示找到路径;否则,递归地访问当前节点的邻接节点,直到找到路径或遍历完所有邻接节点。最后,根据DFS函数的返回值,输出是否存在路径。这段代码的时间复杂度为O(V+E),其中V为节点数,E为边数。因为在最坏情况下,每个节点都需要遍历一次,并且每个节点的邻接节点都需要遍历一次。空间复杂度为O(V),因为需要一个访问标记数组来记录节点的访问状态。总的来说,这段代码使用邻接表实现了图的深度优先搜索算法。可以用于检查图中是否存在路径。


http://www.ppmy.cn/ops/136331.html

相关文章

设计模式-创建型-建造者模式

1.概念 建造者设计模式&#xff08;Builder Design Pattern&#xff09;是一种创建型设计模式&#xff0c;它通过将一个复杂对象的构建过程与它的表示分离&#xff0c;使得同样的构建过程可以创建不同的表示。 2.作用 用于简化对复杂对象的创建 3.应用场景 当我们有一个非…

从 HTML 到 CSS:开启网页样式之旅(二)—— 深入探索 CSS 选择器的奥秘

从 HTML 到 CSS&#xff1a;开启网页样式之旅&#xff08;二&#xff09;—— 深入探索 CSS 选择器的奥秘 前言一、CSS基本选择器1. 通配选择器2. 元素选择器3. 类选择器4. id选择器5.基本选择器总结 二、CSS复合选择器1. 后代选择器2. 子选择器3. 相邻兄弟选择器4.交集选择器5…

Spring框架深度剖析:特性、安全与优化

文章目录 Spring框架简介主要特性1. 依赖注入&#xff08;Dependency Injection, DI&#xff09;2. 面向切面编程&#xff08;Aspect-Oriented Programming, AOP&#xff09;3. 声明式事务管理4. 强大的MVC框架5. 集成测试支持6. 多种数据访问技术的支持 安全性1. 认证&#xf…

网络安全-企业环境渗透2-wordpress任意文件读FFmpeg任意文件读

一、 实验名称 企业环境渗透2 二、 实验目的 【实验描述】 操作机的操作系统是kali 进入系统后默认是命令行界面 输入startx命令即可打开图形界面。 所有需要用到的信息和工具都放在了/home/Hack 目录下。 本实验的任务是通过外网的两个主机通过代理渗透到内网的两个主机。…

鸿蒙NEXT开发案例:数字转中文大小写

【引言】 本应用的主要功能是将用户输入的数字转换为中文的小写、大写及大写金额形式。用户可以在输入框中输入任意数字&#xff0c;点击“示例”按钮可以快速填充预设的数字&#xff0c;点击“清空”按钮则会清除当前输入。转换结果显示在下方的结果区域&#xff0c;每个结果…

Android mk/bp构建工具介绍

零. 前言 由于Bluedroid的介绍文档有限&#xff0c;以及对Android的一些基本的知识需要了(Android 四大组件/AIDL/Framework/Binder机制/JNI/HIDL等)&#xff0c;加上需要掌握的语言包括Java/C/C等&#xff0c;加上网络上其实没有一个完整的介绍Bluedroid系列的文档&#xff0…

SpringBoot整合RabbitMQ应用

本文主要介绍SpringBoot中如何使用RabbitMQ&#xff0c;相关概念及基础使用参考RabbitMQ简单使用 常用配置及方法 展示rabbitmq各个模式在springboot中如何使用之前&#xff0c;先介绍rabbitmq在springboot中的一些常用配置及方法&#xff1a; 注册队列 //使用配置类以bean…

国外云计算服务器租用攻略

国外云计算服务器租用需综合考虑服务商信誉、性能配置、价格性价比、合规性与法律风险、技术支持等因素。首先明确业务需求&#xff0c;选择正规、技术实力强的服务商&#xff0c;并考虑地理位置以优化访问速度。其次&#xff0c;根据需求选择合适的CPU、内存、存储和带宽配置&…