力扣面试题 37 - 节点间通路

embedded/2024/12/28 19:17:57/

题目:

节点间通路。给定有向图,设计一个算法,找出两个节点之间是否存在一条路径。

示例 1:

 输入:n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
 输出:true

示例 2:

 输入:n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
 输出:true

提示:

  1. 节点数量n在[0, 1e5]范围内。
  2. 节点编号大于等于 0 小于 n。
  3. 图中可能存在自环和平行边。

思路:

  1. 将图采用邻接表的方式存储,这样可以节省存储空间并提高查找效率。
  2. 使用深度优先搜索(DFS)或广度优先搜索(BFS)来判断从起始节点 start 是否能够到达目标节点 target

C代码如下:

// 动态数组实现
typedef struct {int *data;int size;int capacity;
} Vector;void vectorInit(Vector *vec) {vec->data = (int *)malloc(4 * sizeof(int));vec->size = 0;vec->capacity = 4;
}void vectorPushBack(Vector *vec, int value) {if (vec->size == vec->capacity) {vec->capacity *= 2;vec->data = (int *)realloc(vec->data, vec->capacity * sizeof(int));}vec->data[vec->size++] = value;
}void vectorFree(Vector *vec) {free(vec->data);
}// DFS 搜索函数
bool dfs(Vector *adjList, int *visited, int current, int target) {if (current == target) return true;visited[current] = 1;Vector *neighbors = &adjList[current];for (int i = 0; i < neighbors->size; i++) {int next = neighbors->data[i];if (!visited[next] && dfs(adjList, visited, next, target)) {return true;}}return false;
}bool findWhetherExistsPath(int n, int **graph, int graphSize, int *graphColSize, int start, int target) {// 构建邻接表Vector *adjList = (Vector *)malloc(n * sizeof(Vector));for (int i = 0; i < n; i++) {vectorInit(&adjList[i]);}for (int i = 0; i < graphSize; i++) {int u = graph[i][0];int v = graph[i][1];vectorPushBack(&adjList[u], v);}// 初始化访问标记数组int *visited = (int *)calloc(n, sizeof(int));// 执行 DFS 搜索bool result = dfs(adjList, visited, start, target);// 释放内存for (int i = 0; i < n; i++) {vectorFree(&adjList[i]);}free(adjList);free(visited);return result;
}


http://www.ppmy.cn/embedded/149532.html

相关文章

FreeSwitch中启用WebRTC

在FreeSwitch中启用WebRTC需要进行一系列配置。以下是详细的步骤&#xff1a; 1. 安装必要的依赖&#xff1a; 确保安装了支持WebRTC的依赖库&#xff0c;如libsrtp。 2. 配置SIP Profile&#xff1a; 编辑 conf/sip_profiles/internal.xml 文件&#xff0c;添加或修改以下内…

《人工智能如何加速药物研发进程:从新药发现到临床试验的突破》

在当今医药领域&#xff0c;药物研发的复杂性和高成本使得新药的推出面临诸多挑战。而人工智能&#xff08;AI&#xff09;正以其强大的能力为药物研发带来新的契机&#xff0c;助力加速新药发现和临床试验过程。 新药发现阶段 靶点识别与筛选 药物研发的第一步是确定药物作…

面向对象的设计原则与设计模式

目的 设计模式的目的是提高代码的重用性&#xff0c;可读性、可扩展性、可靠性&#xff0c;使程序呈现高内聚&#xff0c;低耦合的特性 原则 单一职责原则 假设有一个class负责两个职责&#xff0c;一旦发生需求变更&#xff0c;修改其中一个职责的逻辑代码&#xff0c;有可能…

机器视觉检测相机基础知识 | 颜色 | 光源 | 镜头 | 分辨率 / 精度 / 公差

注&#xff1a;本文为 “keyence 视觉沙龙中机器视觉检测基础知识” 文章合辑。 机器视觉检测基础知识&#xff08;一&#xff09;颜色篇 视觉检测硬件构成的基本部分包括&#xff1a;处理器、相机、镜头、光源。 其中&#xff0c;和光源相关的最重要的两个参数就是光源颜色和…

利用AI进行系统性能优化:智能运维的新时代

在现代信息技术环境中&#xff0c;系统性能优化是确保计算资源高效利用、提升系统稳定性和用户体验的关键环节。传统的性能优化方法依赖于人工经验和手动调试&#xff0c;难以应对复杂多变的系统环境和动态工作负载。随着人工智能&#xff08;AI&#xff09;技术的快速发展&…

低代码配置式组态软件-BY组态

随着物联网、大数据等技术高速发展&#xff0c;我们逐步向数字化、可视化的人工智能&#xff08;AI&#xff09;时代的方向不断迈进。智能时代是工业 4.0 时代&#xff0c;我国工业领域正努力从“制造”迈向“智造”的新跨越。 什么是组态软件&#xff1f; 组态软件&#xff…

24. 解密犯罪时间

题目描述 警察在侦破一个案件时&#xff0c;得到了线人给出的可能犯罪时间&#xff0c;形如“HH:MM”表示的时刻。根据警察和线人的约定&#xff0c;为了隐蔽&#xff0c;该时间是修改过的&#xff0c;解密规则为:利用当前出现过的数字&#xff0c;构造下一个距离当前时间最近的…

RAGFlow 基于深度文档理解构建的开源 RAG引擎 - 安装部署

RAGFlow 基于深度文档理解构建的开源 RAG引擎 - 安装部署 flyfish 1. 确保 vm.max_map_count ≥ 262144 这是指要调整Linux内核参数vm.max_map_count&#xff0c;以确保其值至少为262144。这个参数控制着进程可以映射的最大内存区域数量。对于某些应用程序&#xff08;如Ela…