题目描述
传递悄悄话
在一个由 n 个节点组成的无向图中,节点编号从 0 到 n-1。图中的边表示两个人可以直接传递悄悄话。
给定一个 n 节点的无向图(用邻接矩阵 graph 表示)和一个起始节点 start,你需要找到从起始节点出发,经过 k 个节点后,能到达的所有节点,并返回这些节点的编号。
输入:
- n:节点数量(整数)
- graph:邻接矩阵,表示无向图(二维数组,graph[i][j] 为 1 表示节点 i 和节点 j 之间有边,为 0 表示没有边)
- start:起始节点编号(整数)
- k:经过的节点数量(整数)
输出:
- 返回一个整数列表,表示从起始节点 start 出发,经过 k 个节点后能到达的所有节点编号。
注意:
- 路径可以重复经过某些节点,但每经过一个节点,步数 k 都要减一。
- 图中没有重边和自环。
思路分析
这是一个典型的图遍历问题,可以使用广度优先搜索(BFS)或者深度优先搜索(DFS)来解决。
- 初始化:
- 创建一个队列(对于BFS)或栈(对于DFS)来存储当前正在处理的节点。
- 创建一个集合(Set)来记录已经访问过的节点,防止重复访问。
- 创建一个结果列表(List)来存储最终的结果。
- 开始遍历:
- 将起始节点加入队列或