企业官网建设流程全解析

相关推荐阅读

• 【2026华为OD机考】最新套题持续更新【完全原创题解 | 详细考点分类 | 不断更新题目 | 六种主流语言Py+Java+Cpp+C+Js+Go】
• 【2026年华为OD机考最新政策】2026年新规改革最新变化 | 学习策略 | 考试时间 | 出题形式 | 输入形式 | 考前流程 | 双机位摆放
• 【华为OD机考正在更新】2025年双机位A卷真题【完全原创题解 | 详细考点分类 | 不断更新题目 | 六种主流语言Py+Java+Cpp+C+Js+Go】
• 【华为OD机考】2025C+2025B+2024E+D卷真题【完全原创题解 | 详细考点分类 | 不断更新题目】
• 【华为OD笔试】双机位A+2025C+2025B+2024E+D卷真题机考套题汇总【真实反馈，不断更新，限时免费】
• 【华为OD笔试】2024E+D卷命题规律解读【分析500+场OD笔试考点总结】
• 【华为OD流程】性格测试选项+注意事项

题目练习网址：【DFS】20260906-图的遍历

题目描述与示例
给定一个无向图，顶点编号从 1 到 n；从顶点 1 出发，进行深度优先搜索（DFS），当某个顶点有多个邻接点时，按照编号从小到大的顺序依次访问，输出遍历过程中访问顶点的顺序。

1 <= n <= 100，0 <= m <= 100。若不连通，DFS 从顶点 1 出发无法遍历所有顶点，输出只包含可达顶点。输入保证没有自环如 (i, i)，即顶点到自身的边；同时输入保证不会有多条相同的边，如 (1, 2) 出现两次。

输入描述
整数 n, m：表示顶点数和边数；
二维数组 graph：每个元素有两个整数 u, v，表示 u 和 v 之间有一条无向边

输出描述
数组：数组元素表示深度优先搜索访问顶点的顺序（从 1 开始）

示例一

输入

6 5
1 2
1 3
2 4
3 5
3 6

输出

1,2,4,3,5,6

说明
从 1 出发，邻接点有 {2,3}，选小的 2
从 2 出发，邻接点有 {1,4}，1 已访问，选 4
4 没有未访问邻接点，回溯到 2，回溯到 1，下一个未访问的是 3
从 3 出发，邻接点有 {1,5,6}，1 已访问，选小的 5
5 没有未访问邻接点，回溯到 3，下一个未访问的是 6；6 结束，遍历完成。最终访问顺序为 [1,2,4,3,5,6]。

示例二
输入

5 2
1 2
3 4

输出
1,2

说明
从 1 出发，邻接点有 {2}，选 2
从 2 出发，邻接点有 {1}，1 已访问，没有未访问邻接点，回溯到 1
1 没有其他未访问邻接点，遍历结束。顶点 3、4、5 与 1 不连通，无法到达，因此不输出。最终访问顺序为 [1,2]。

解题思路
DFS板子题，直接套DFS解法的模板即可。

有几个小地方需要注意。

1. 邻接表的构建
   容易发现，顶点编号从 1 开始，n 结束。
   所以邻接表开 n+1 的长度，下标 0 不用，这样可以直接用 adj[u] 访问顶点 u 的邻接点，代码更直观。
   当然这个地方也可以使用哈希表来储存。
   self.ans = [] # 存储最终访问顺序
   self.adj = [[] for _ in range(n + 1)] # 邻接表，下标0闲置，直接用1~n
   self.visited = [] # 先占位，后面再初始化

for u, v in graph:
self.adj[u].append(v) # u的邻接点加入v
self.adj[v].append(u) # v的邻接点加入u，无向图双向添加

2. 排序邻接列表
   题目要求，当某个顶点有多个邻接点时，按照编号从小到大的顺序依次访问。
   所以我们在构建完邻接表之后，要对邻接表中每一个点的所有近邻点按照编号进行排序。
   for i in range(1, n + 1):
   self.adj[i].sort()

这是本题的关键步骤。排序后，后面DFS时 for neighbor in self.adj[start] 自然就是从小到大遍历，无需在DFS内部再做判断。

3. DFS初始化
   根据示例2可以看出，题目只需要从顶点1出发进行遍历。
   即使整个无向图并不完全连通，DFS 从顶点 1 出发无法遍历所有顶点，也要输出所有可达顶点。
   self.dfs(1) # 从顶点1出发，题目固定要求

其他内容就是常规的DFS模板。

代码
Python
from typing import List

class Solution:
def dfs(self, start: int) -> None:
“”"
深度优先搜索的核心递归函数，作为Solution类的成员函数实现。
容易发现，递归三要素：
1. 终止条件：当前顶点已访问过，直接返回（实际上层已判断，这里可省略）
2. 处理当前节点：标记访问，加入结果
3. 递归访问邻接点：按排序后的顺序，逐个访问未访问的邻接点
“”"
# 标记当前顶点已访问
self.visited[start] = True

# 将当前顶点加入访问顺序结果 self.ans.append(start) # 遍历当前顶点的所有邻接点，由于已排序，自然按从小到大顺序 for neighbor in self.adj[start]: # 注意到，只有未访问的邻接点才需要递归深入 if not self.visited[neighbor]: # 递归访问该邻接点，回溯时会自动回到这里继续下一个邻接点 self.dfs(neighbor) def dfsTraversal(self, n: int, m: int, graph: List[List[int]]) -> List[int]: """ 这是一个非常典型的无向图深度优先搜索问题，核心要求是邻接点按编号从小到大访问。 容易想到，我们需要： 1. 构建邻接表存储图结构 2. 对每个顶点的邻接列表进行排序，保证DFS时从小到大选取 3. 使用visited数组标记访问状态，避免重复访问 4. 从顶点1出发进行DFS，只输出可达顶点 时间复杂度：O(n + m log m)，主要来自排序邻接表；空间复杂度：O(n + m) """ # 初始化答案数组，用于存储DFS访问顺序，确保多次调用不会相互影响 self.ans = [] # 初始化邻接表，用于存储图结构，注意顶点编号从1到n，我们开n+1的空间，下标0闲置 self.adj = [[] for _ in range(n + 1)] # 初始化visited数组，记录每个顶点是否已被访问 self.visited = [] # 遍历每条边，构建无向图的邻接表 for u, v in graph: self.adj[u].append(v) # u的邻接点加入v self.adj[v].append(u) # v的邻接点加入u，无向图双向添加 # 对每个顶点的邻接列表排序，保证DFS时按编号从小到大访问 # 这是本题的关键约束，必须满足 for i in range(1, n + 1): self.adj[i].sort() # 初始化visited数组，记录每个顶点是否已被访问 self.visited = [False] * (n + 1) # 从顶点1出发开始DFS，题目固定要求 # 换句话说，即使1号顶点没有邻接点，也要输出[1] self.dfs(1) # 返回DFS访问顺序，只包含从1出发可达的顶点 return self.ans

ifname== “main”:
import sys
input = sys.stdin.readline

line = input().strip() while line == '': line = input().strip() n, m = map(int, line.split()) graph = [] for _ in range(m): line = input().strip() while line == '': line = input().strip() u, v = map(int, line.split()) graph.append([u, v]) sol = Solution() result = sol.dfsTraversal(n, m, graph) print(','.join(map(str, result)))

Java
import java.util.*;

public class Solution {
// 存储DFS访问顺序的结果数组
private List ans;
// 邻接表，存储图结构
private List<List> adj;
// 访问标记数组
private boolean[] visited;

/** * 深度优先搜索的核心递归函数，作为Solution类的成员函数实现。 * 容易发现，递归三要素： * 1. 终止条件：当前顶点已访问过，直接返回（实际上层已判断，这里可省略） * 2. 处理当前节点：标记访问，加入结果 * 3. 递归访问邻接点：按排序后的顺序，逐个访问未访问的邻接点 */ private void dfs(int start) { // 标记当前顶点已访问 visited[start] = true; // 将当前顶点加入访问顺序结果 ans.add(start); // 遍历当前顶点的所有邻接点，由于已排序，自然按从小到大顺序 for (int neighbor : adj.get(start)) { // 注意到，只有未访问的邻接点才需要递归深入 if (!visited[neighbor]) { // 递归访问该邻接点，回溯时会自动回到这里继续下一个邻接点 dfs(neighbor); } } } /** * 这是一个非常典型的无向图深度优先搜索问题，核心要求是邻接点按编号从小到大访问。 * 容易想到，我们需要： * 1. 构建邻接表存储图结构 * 2. 对每个顶点的邻接列表进行排序，保证DFS时从小到大选取 * 3. 使用visited数组标记访问状态，避免重复访问 * 4. 从顶点1出发进行DFS，只输出可达顶点 * * 时间复杂度：O(n + m log m)，主要来自排序邻接表；空间复杂度：O(n + m) */ public List<Integer> dfsTraversal(int n, int m, List<List<Integer>> graph) { // 初始化答案数组，用于存储DFS访问顺序，确保多次调用不会相互影响 ans = new ArrayList<>(); // 初始化邻接表，用于存储图结构，注意顶点编号从1到n，我们开n+1的空间，下标0闲置 adj = new ArrayList<>(); for (int i = 0; i <= n; i++) { adj.add(new ArrayList<>()); } // 遍历每条边，构建无向图的邻接表 for (List<Integer> edge : graph) { int u = edge.get(0); int v = edge.get(1); adj.get(u).add(v); // u的邻接点加入v adj.get(v).add(u); // v的邻接点加入u，无向图双向添加 } // 对每个顶点的邻接列表排序，保证DFS时按编号从小到大访问 // 这是本题的关键约束，必须满足 for (int i = 1; i <= n; i++) { Collections.sort(adj.get(i)); } // 初始化visited数组，记录每个顶点是否已被访问 visited = new boolean[n + 1]; // 从顶点1出发开始DFS，题目固定要求 // 换句话说，即使1号顶点没有邻接点，也要输出[1] dfs(1); // 返回DFS访问顺序，只包含从1出发可达的顶点 return ans; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String line = scanner.nextLine().trim(); while (line.isEmpty()) { line = scanner.nextLine().trim(); } String[] parts = line.split("\\s+"); int n = Integer.parseInt(parts[0]); int m = Integer.parseInt(parts[1]); List<List<Integer>> graph = new ArrayList<>(); for (int i = 0; i < m; i++) { line = scanner.nextLine().trim(); while (line.isEmpty()) { line = scanner.nextLine().trim(); } parts = line.split("\\s+"); int u = Integer.parseInt(parts[0]); int v = Integer.parseInt(parts[1]); List<Integer> edge = new ArrayList<>(); edge.add(u); edge.add(v); graph.add(edge); } Solution sol = new Solution(); List<Integer> result = sol.dfsTraversal(n, m, graph); StringBuilder sb = new StringBuilder(); for (int i = 0; i < result.size(); i++) { if (i > 0) { sb.append(","); } sb.append(result.get(i)); } System.out.println(sb.toString()); scanner.close(); }

}
C++
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
// 深度优先搜索的核心递归函数，作为Solution类的成员函数实现。
// 容易发现，递归三要素：
// 1. 终止条件：当前顶点已访问过，直接返回（实际上层已判断，这里可省略）
// 2. 处理当前节点：标记访问，加入结果
// 3. 递归访问邻接点：按排序后的顺序，逐个访问未访问的邻接点
void dfs(int start) {
// 标记当前顶点已访问
visited[start] = true;

// 将当前顶点加入访问顺序结果 ans.push_back(start); // 遍历当前顶点的所有邻接点，由于已排序，自然按从小到大顺序 for (int neighbor : adj[start]) { // 注意到，只有未访问的邻接点才需要递归深入 if (!visited[neighbor]) { // 递归访问该邻接点，回溯时会自动回到这里继续下一个邻接点 dfs(neighbor); } } } // 这是一个非常典型的无向图深度优先搜索问题，核心要求是邻接点按编号从小到大访问。 // 容易想到，我们需要： // 1. 构建邻接表存储图结构 // 2. 对每个顶点的邻接列表进行排序，保证DFS时从小到大选取 // 3. 使用visited数组标记访问状态，避免重复访问 // 4. 从顶点1出发进行DFS，只输出可达顶点 // // 时间复杂度：O(n + m log m)，主要来自排序邻接表；空间复杂度：O(n + m) vector<int> dfsTraversal(int n, int m, vector<vector<int>>& graph) { // 初始化答案数组，用于存储DFS访问顺序，确保多次调用不会相互影响 ans.clear(); // 初始化邻接表，用于存储图结构，注意顶点编号从1到n，我们开n+1的空间，下标0闲置 adj.assign(n + 1, vector<int>()); // 初始化visited数组，记录每个顶点是否已被访问 visited.assign(n + 1, false); // 遍历每条边，构建无向图的邻接表 for (auto& edge : graph) { int u = edge[0]; int v = edge[1]; adj[u].push_back(v); // u的邻接点加入v adj[v].push_back(u); // v的邻接点加入u，无向图双向添加 } // 对每个顶点的邻接列表排序，保证DFS时按编号从小到大访问 // 这是本题的关键约束，必须满足 for (int i = 1; i <= n; i++) { sort(adj[i].begin(), adj[i].end()); } // 从顶点1出发开始DFS，题目固定要求 // 换句话说，即使1号顶点没有邻接点，也要输出[1] dfs(1); // 返回DFS访问顺序，只包含从1出发可达的顶点 return ans; }

private:
vector ans;
vector<vector> adj;
vector visited;
};

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

string line; getline(cin, line); while (line == "") { getline(cin, line); } stringstream ss(line); int n, m; ss >> n >> m; vector<vector<int>> graph; for (int i = 0; i < m; i++) { getline(cin, line); while (line == "") { getline(cin, line); } stringstream edge_ss(line); int u, v; edge_ss >> u >> v; graph.push_back({u, v}); } Solution sol; vector<int> result = sol.dfsTraversal(n, m, graph); for (int i = 0; i < result.size(); i++) { if (i > 0) { cout << ","; } cout << result[i]; } cout << endl; return 0;

}
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 以下内容为LeetCode核心代码模式转为ACM模式所需代码
// 请在algomooc oj上直接使用，在实际考试中无需编写

typedef struct {
int* ans;
int ans_count;
int ans_capacity;
int** adj;
int* adj_counts;
int* adj_capacities;
int adj_size;
int* visited;
int visited_size;
} Solution;

void solution_init(Solution* sol) {
sol->ans = NULL;
sol->ans_count = 0;
sol->ans_capacity = 0;
sol->adj = NULL;
sol->adj_counts = NULL;
sol->adj_capacities = NULL;
sol->adj_size = 0;
sol->visited = NULL;
sol->visited_size = 0;
}

void solution_free(Solution* sol) {
if (sol->ans != NULL) {
free(sol->ans);
sol->ans = NULL;
}
if (sol->adj != NULL) {
for (int i = 0; i < sol->adj_size; i++) {
if (sol->adj[i] != NULL) {
free(sol->adj[i]);
sol->adj[i] = NULL;
}
}
free(sol->adj);
sol->adj = NULL;
}
if (sol->adj_counts != NULL) {
free(sol->adj_counts);
sol->adj_counts = NULL;
}
if (sol->adj_capacities != NULL) {
free(sol->adj_capacities);
sol->adj_capacities = NULL;
}
if (sol->visited != NULL) {
free(sol->visited);
sol->visited = NULL;
}
}

void ans_push_back(Solution* sol, int val) {
if (sol->ans_count >= sol->ans_capacity) {
int new_capacity = sol->ans_capacity == 0 ? 4 : sol->ans_capacity * 2;
int* new_ans = (int*)realloc(sol->ans, new_capacity * sizeof(int));
sol->ans = new_ans;
sol->ans_capacity = new_capacity;
}
sol->ans[sol->ans_count++] = val;
}

void adj_push_back(Solution* sol, int u, int v) {
if (sol->adj_counts[u] >= sol->adj_capacities[u]) {
int new_capacity = sol->adj_capacities[u] == 0 ? 4 : sol->adj_capacities[u] * 2;
int* new_adj = (int*)realloc(sol->adj[u], new_capacity * sizeof(int));
sol->adj[u] = new_adj;
sol->adj_capacities[u] = new_capacity;
}
sol->adj[u][sol->adj_counts[u]++] = v;
}

int compare_int(const void* a, const void* b) {
return ((int)a -(int)b);
}

// 深度优先搜索的核心递归函数，作为Solution结构体的成员函数实现。
// 容易发现，递归三要素：
// 1. 终止条件：当前顶点已访问过，直接返回（实际上层已判断，这里可省略）
// 2. 处理当前节点：标记访问，加入结果
// 3. 递归访问邻接点：按排序后的顺序，逐个访问未访问的邻接点
void dfs(Solution* sol, int start) {
// 标记当前顶点已访问
sol->visited[start] = 1;

// 将当前顶点加入访问顺序结果 ans_push_back(sol, start); // 遍历当前顶点的所有邻接点，由于已排序，自然按从小到大顺序 for (int i = 0; i < sol->adj_counts[start]; i++) { int neighbor = sol->adj[start][i]; // 注意到，只有未访问的邻接点才需要递归深入 if (!sol->visited[neighbor]) { // 递归访问该邻接点，回溯时会自动回到这里继续下一个邻接点 dfs(sol, neighbor); } }

}

// 这是一个非常典型的无向图深度优先搜索问题，核心要求是邻接点按编号从小到大访问。
// 容易想到，我们需要：
// 1. 构建邻接表存储图结构
// 2. 对每个顶点的邻接列表进行排序，保证DFS时从小到大选取
// 3. 使用visited数组标记访问状态，避免重复访问
// 4. 从顶点1出发进行DFS，只输出可达顶点
//
// 时间复杂度：O(n + m log m)，主要来自排序邻接表；空间复杂度：O(n + m)
int* dfs_traversal(Solution* sol, int n, int m, int** graph, int* out_count) {
// 初始化答案数组，用于存储DFS访问顺序，确保多次调用不会相互影响
sol->ans_count = 0;
// 初始化邻接表，用于存储图结构，注意顶点编号从1到n，我们开n+1的空间，下标0闲置
sol->adj_size = n + 1;
sol->adj = (int**)malloc(sol->adj_size * sizeof(int*));
sol->adj_counts = (int*)malloc(sol->adj_size * sizeof(int));
sol->adj_capacities = (int*)malloc(sol->adj_size * sizeof(int));
for (int i = 0; i < sol->adj_size; i++) {
sol->adj[i] = NULL;
sol->adj_counts[i] = 0;
sol->adj_capacities[i] = 0;
}
// 初始化visited数组，记录每个顶点是否已被访问
sol->visited_size = n + 1;
sol->visited = (int*)malloc(sol->visited_size * sizeof(int));
for (int i = 0; i < sol->visited_size; i++) {
sol->visited[i] = 0;
}

// 遍历每条边，构建无向图的邻接表 for (int i = 0; i < m; i++) { int u = graph[i][0]; int v = graph[i][1]; adj_push_back(sol, u, v); // u的邻接点加入v adj_push_back(sol, v, u); // v的邻接点加入u，无向图双向添加 } // 对每个顶点的邻接列表排序，保证DFS时按编号从小到大访问 // 这是本题的关键约束，必须满足 for (int i = 1; i <= n; i++) { qsort(sol->adj[i], sol->adj_counts[i], sizeof(int), compare_int); } // 从顶点1出发开始DFS，题目固定要求 // 换句话说，即使1号顶点没有邻接点，也要输出[1] dfs(sol, 1); // 返回DFS访问顺序，只包含从1出发可达的顶点 *out_count = sol->ans_count; int* result = (int*)malloc(sol->ans_count * sizeof(int)); for (int i = 0; i < sol->ans_count; i++) { result[i] = sol->ans[i]; } return result;

}

int main() {
char line[1024];
if (fgets(line, sizeof(line), stdin) == NULL) {
return 0;
}
while (line[0] == ‘\n’ || line[0] == ‘\r’ || line[0] == ‘\0’) {
if (fgets(line, sizeof(line), stdin) == NULL) {
return 0;
}
}
int len = strlen(line);
while (len > 0 && (line[len - 1] == ‘\n’ || line[len - 1] == ‘\r’)) {
line[len - 1] = ‘\0’;
len–;
}

int n = atoi(strtok(line, " ")); int m = atoi(strtok(NULL, " ")); int** graph = (int**)malloc(m * sizeof(int*)); for (int i = 0; i < m; i++) { graph[i] = (int*)malloc(2 * sizeof(int)); if (fgets(line, sizeof(line), stdin) == NULL) { return 0; } while (line[0] == '\n' || line[0] == '\r' || line[0] == '\0') { if (fgets(line, sizeof(line), stdin) == NULL) { return 0; } } len = strlen(line); while (len > 0 && (line[len - 1] == '\n' || line[len - 1] == '\r')) { line[len - 1] = '\0'; len--; } graph[i][0] = atoi(strtok(line, " ")); graph[i][1] = atoi(strtok(NULL, " ")); } Solution sol; solution_init(&sol); int result_count; int* result = dfs_traversal(&sol, n, m, graph, &result_count); for (int i = 0; i < result_count; i++) { if (i > 0) { printf(","); } printf("%d", result[i]); } printf("\n"); for (int i = 0; i < m; i++) { free(graph[i]); graph[i] = NULL; } free(graph); graph = NULL; free(result); result = NULL; solution_free(&sol); return 0;

}
Node JavaScript
class Solution {
// 存储DFS访问顺序的结果数组
constructor() {
this.ans = [];
// 邻接表，存储图结构
this.adj = [];
// 访问标记数组
this.visited = [];
}

/** * 深度优先搜索的核心递归函数，作为Solution类的成员函数实现。 * 容易发现，递归三要素： * 1. 终止条件：当前顶点已访问过，直接返回（实际上层已判断，这里可省略） * 2. 处理当前节点：标记访问，加入结果 * 3. 递归访问邻接点：按排序后的顺序，逐个访问未访问的邻接点 */ dfs(start) { // 标记当前顶点已访问 this.visited[start] = true; // 将当前顶点加入访问顺序结果 this.ans.push(start); // 遍历当前顶点的所有邻接点，由于已排序，自然按从小到大顺序 for (let neighbor of this.adj[start]) { // 注意到，只有未访问的邻接点才需要递归深入 if (!this.visited[neighbor]) { // 递归访问该邻接点，回溯时会自动回到这里继续下一个邻接点 this.dfs(neighbor); } } } /** * 这是一个非常典型的无向图深度优先搜索问题，核心要求是邻接点按编号从小到大访问。 * 容易想到，我们需要： * 1. 构建邻接表存储图结构 * 2. 对每个顶点的邻接列表进行排序，保证DFS时从小到大选取 * 3. 使用visited数组标记访问状态，避免重复访问 * 4. 从顶点1出发进行DFS，只输出可达顶点 * * 时间复杂度：O(n + m log m)，主要来自排序邻接表；空间复杂度：O(n + m) */ dfsTraversal(n, m, graph) { // 初始化答案数组，用于存储DFS访问顺序，确保多次调用不会相互影响 this.ans = []; // 初始化邻接表，用于存储图结构，注意顶点编号从1到n，我们开n+1的空间，下标0闲置 this.adj = []; for (let i = 0; i <= n; i++) { this.adj.push([]); } // 遍历每条边，构建无向图的邻接表 for (let edge of graph) { let u = edge[0]; let v = edge[1]; this.adj[u].push(v); // u的邻接点加入v this.adj[v].push(u); // v的邻接点加入u，无向图双向添加 } // 对每个顶点的邻接列表排序，保证DFS时按编号从小到大访问 // 这是本题的关键约束，必须满足 for (let i = 1; i <= n; i++) { this.adj[i].sort((a, b) => a - b); } // 初始化visited数组，记录每个顶点是否已被访问 this.visited = new Array(n + 1).fill(false); // 从顶点1出发开始DFS，题目固定要求 // 换句话说，即使1号顶点没有邻接点，也要输出[1] this.dfs(1); // 返回DFS访问顺序，只包含从1出发可达的顶点 return this.ans; }

}

function main() {
const readline = require(‘readline’);
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

const lines = []; rl.on('line', (line) => { lines.push(line.trim()); }); rl.on('close', () => { let idx = 0; while (idx < lines.length && lines[idx] === '') { idx++; } let parts = lines[idx].split(/\s+/); let n = parseInt(parts[0]); let m = parseInt(parts[1]); idx++; let graph = []; for (let i = 0; i < m; i++) { while (idx < lines.length && lines[idx] === '') { idx++; } parts = lines[idx].split(/\s+/); let u = parseInt(parts[0]); let v = parseInt(parts[1]); let edge = [u, v]; graph.push(edge); idx++; } let sol = new Solution(); let result = sol.dfsTraversal(n, m, graph); console.log(result.join(',')); });

}

main();
Go
package main

import (
“bufio”
“fmt”
“os”
“sort”
“strconv”
“strings”
)

// 存储DFS访问顺序的结果数组
var ans []int
// 邻接表，存储图结构
var adj [][]int
// 访问标记数组
var visited []bool

/**

• 深度优先搜索的核心递归函数，作为Solution类的成员函数实现。
• 容易发现，递归三要素：
• 1. 终止条件：当前顶点已访问过，直接返回（实际上层已判断，这里可省略）
• 2. 处理当前节点：标记访问，加入结果

• 3. 递归访问邻接点：按排序后的顺序，逐个访问未访问的邻接点
     */
     func dfs(start int) {
     // 标记当前顶点已访问
     visited[start] = true

     // 将当前顶点加入访问顺序结果
     ans = append(ans, start)

     // 遍历当前顶点的所有邻接点，由于已排序，自然按从小到大顺序
     for _, neighbor := range adj[start] {
     // 注意到，只有未访问的邻接点才需要递归深入
     if !visited[neighbor] {
     // 递归访问该邻接点，回溯时会自动回到这里继续下一个邻接点
     dfs(neighbor)
     }
     }
     }

/**

• 这是一个非常典型的无向图深度优先搜索问题，核心要求是邻接点按编号从小到大访问。

• 容易想到，我们需要：

• 1. 构建邻接表存储图结构
• 2. 对每个顶点的邻接列表进行排序，保证DFS时从小到大选取
• 3. 使用visited数组标记访问状态，避免重复访问
• 4. 从顶点1出发进行DFS，只输出可达顶点

• 时间复杂度：O(n + m log m)，主要来自排序邻接表；空间复杂度：O(n + m)
  */
  func dfsTraversal(n int, m int, graph [][]int) []int {
  // 初始化答案数组，用于存储DFS访问顺序，确保多次调用不会相互影响
  ans = []int{}
  // 初始化邻接表，用于存储图结构，注意顶点编号从1到n，我们开n+1的空间，下标0闲置
  adj = make([][]int, n+1)

  // 遍历每条边，构建无向图的邻接表 for _, edge := range graph { u := edge[0] v := edge[1] adj[u] = append(adj[u], v) // u的邻接点加入v adj[v] = append(adj[v], u) // v的邻接点加入u，无向图双向添加 } // 对每个顶点的邻接列表排序，保证DFS时按编号从小到大访问 // 这是本题的关键约束，必须满足 for i := 1; i <= n; i++ { sort.Ints(adj[i]) } // 初始化visited数组，记录每个顶点是否已被访问 visited = make([]bool, n+1) // 从顶点1出发开始DFS，题目固定要求 // 换句话说，即使1号顶点没有邻接点，也要输出[1] dfs(1) // 返回DFS访问顺序，只包含从1出发可达的顶点 return ans

}

func main() {
scanner := bufio.NewScanner(os.Stdin)

var line string for scanner.Scan() { line = strings.TrimSpace(scanner.Text()) if line != "" { break } } parts := strings.Fields(line) n, _ := strconv.Atoi(parts[0]) m, _ := strconv.Atoi(parts[1]) graph := make([][]int, 0, m) for i := 0; i < m; i++ { for scanner.Scan() { line = strings.TrimSpace(scanner.Text()) if line != "" { break } } parts = strings.Fields(line) u, _ := strconv.Atoi(parts[0]) v, _ := strconv.Atoi(parts[1]) edge := []int{u, v} graph = append(graph, edge) } result := dfsTraversal(n, m, graph) var sb strings.Builder for i := 0; i < len(result); i++ { if i > 0 { sb.WriteString(",") } sb.WriteString(strconv.Itoa(result[i])) } fmt.Println(sb.String())

}

时空复杂度
时间复杂度：O(n)。
空间复杂度：O(n)。

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务1000+同学成功上岸！

• 课程讲师为全网200w+粉丝编程博主@吴师兄学算法以及小红书头部编程博主@闭着眼睛学数理化

• 90+天陪伴式学习，100+直播课时，300+动画图解视频，500+LeetCode经典题，500+华为OD真题/大厂真题，还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁