六、算法
6.1 排序算法
常见的排序算法有哪些？各自的时间复杂度和空间复杂度是多少？
冒泡排序（Bubble Sort）：
- 基本思想：重复地比较相邻两个元素，如果它们的顺序错误就交换它们；
- 时间复杂度：最好O(n)（已排序），平均O(n²)，最坏O(n²)；
- 空间复杂度：O(1)；
- 稳定性：稳定。
选择排序（Selection Sort）：
- 基本思想：每次从未排序部分选择最小的元素，放到已排序部分的末尾；
- 时间复杂度：最好O(n²)，平均O(n²)，最坏O(n²)；
- 空间复杂度：O(1)；
- 稳定性：不稳定。
插入排序（Insertion Sort）：
- 基本思想：将未排序的元素插入到已排序部分的适当位置；
- 时间复杂度：最好O(n)（已排序），平均O(n²)，最坏O(n²)；
- 空间复杂度：O(1)；
- 稳定性：稳定。
希尔排序（Shell Sort）：
- 基本思想：对插入排序的改进，先比较距离较远的元素，逐步缩小比较的间隔；
- 时间复杂度：取决于增量序列，平均O(n^1.3)，最坏O(n²)；
- 空间复杂度：O(1)；
- 稳定性：不稳定。
归并排序（Merge Sort）：
- 基本思想：分治法，将数组分成两半，分别排序后合并；
- 时间复杂度：最好O(n log n)，平均O(n log n)，最坏O(n log n)；
- 空间复杂度：O(n)；
- 稳定性：稳定。
快速排序（Quick Sort）：
- 基本思想：选择一个基准元素，将数组分为小于基准和大于基准的两部分，递归排序；
- 时间复杂度：最好O(n log n)，平均O(n log n)，最坏O(n²)（有序数组）；
- 空间复杂度：O(log n)（递归栈）；
- 稳定性：不稳定。
堆排序（Heap Sort）：
- 基本思想：将数组构建成最大堆，反复取出堆顶元素；
- 时间复杂度：最好O(n log n)，平均O(n log n)，最坏O(n log n)；
- 空间复杂度：O(1)；
- 稳定性：不稳定。
计数排序（Counting Sort）：
- 基本思想：统计每个元素出现的次数，然后根据次数重建数组；
- 时间复杂度：最好O(n + k)，平均O(n + k)，最坏O(n + k)（k为元素的范围）；
- 空间复杂度：O(k)；
- 稳定性：稳定。
桶排序（Bucket Sort）：
- 基本思想：将元素分配到有限数量的桶中，对每个桶单独排序；
- 时间复杂度：最好O(n + k)，平均O(n + k)，最坏O(n²)（所有元素在一个桶）；
- 空间复杂度：O(n + k)；
- 稳定性：稳定（取决于桶内排序算法）。
基数排序（Radix Sort）：
- 基本思想：按照位（个位、十位等）进行排序，低位排序后再高位排序；
- 时间复杂度：最好O(n * k)，平均O(n * k)，最坏O(n * k)（k为位数）；
- 空间复杂度：O(n + k)；
- 稳定性：稳定。
// 冒泡排序实现 void bubble_sort(std::vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; ++i) { bool swapped = false; for (int j = 0; j < n - i - 1; ++j) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); swapped = true; } } if (!swapped) break; // 优化：如果没有交换，说明已经有序 } } // 快速排序实现 void quick_sort(std::vector<int>& arr, int low, int high) { if (low < high) { // 选择基准元素并分区 int pivot = arr[high]; // 选择最右边的元素作为基准 int i = low - 1; // i指向小于基准的最后一个元素 for (int j = low; j < high; ++j) { if (arr[j] <= pivot) { ++i; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); // 将基准放到正确的位置 int pivot_index = i + 1; // 递归排序左右两部分 quick_sort(arr, low, pivot_index - 1); quick_sort(arr, pivot_index + 1, high); } } // 归并排序实现 void merge(std::vector<int>& arr, int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; // 创建临时数组 std::vector<int> L(n1), R(n2); // 复制数据到临时数组 for (int i = 0; i < n1; ++i) { L[i] = arr[left + i]; } for (int j = 0; j < n2; ++j) { R[j] = arr[mid + 1 + j]; } // 合并临时数组 int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; ++i; } else { arr[k] = R[j]; ++j; } ++k; } // 复制剩余元素 while (i < n1) { arr[k] = L[i]; ++i; ++k; } while (j < n2) { arr[k] = R[j]; ++j; ++k; } } void merge_sort(std::vector<int>& arr, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; // 避免整数溢出 // 递归排序左右两部分 merge_sort(arr, left, mid); merge_sort(arr, mid + 1, right); // 合并 merge(arr, left, mid, right); } } void test_sorting_algorithms() { std::vector<int> arr = {12, 11, 13, 5, 6, 7}; std::vector<int> arr_copy = arr; // 测试冒泡排序 bubble_sort(arr); std::cout << "Bubble Sort result: "; for (int num : arr) std::cout << num << " "; std::cout << std::endl; // 测试快速排序 arr = arr_copy; quick_sort(arr, 0, arr.size() - 1); std::cout << "Quick Sort result: "; for (int num : arr) std::cout << num << " "; std::cout << std::endl; // 测试归并排序 arr = arr_copy; merge_sort(arr, 0, arr.size() - 1); std::cout << "Merge Sort result: "; for (int num : arr) std::cout << num << " "; std::cout << std::endl; }
什么是稳定排序和不稳定排序？举个例子说明。
稳定排序（Stable Sorting）：
- 指在排序过程中，相等元素的相对顺序在排序前后保持不变；
- 即如果两个元素a和b相等（a == b），且在排序前a在b的前面，那么排序后a仍在b的前面。
不稳定排序（Unstable Sorting）：
- 指在排序过程中，相等元素的相对顺序可能会改变；
- 即如果两个元素a和b相等（a == b），且在排序前a在b的前面，排序后a可能在b的后面。
例子说明：
- 假设有一个包含学生信息的数组，每个学生有姓名和分数两个属性；
- 初始数组按照姓名排序：[{“Alice”, 85}, {“Bob”, 90}, {“Charlie”, 85}, {“David”, 95}];
- 如果我们按照分数进行稳定排序，排序后Alice和Charlie的相对顺序保持不变；
- 如果我们按照分数进行不稳定排序，排序后Alice和Charlie的相对顺序可能会改变。
// 稳定排序和不稳定排序的示例 struct Student { std::string name; int score; // 构造函数 Student(std::string n, int s) : name(n), score(s) {} }; // 稳定排序实现（归并排序） void stable_sort_students(std::vector<Student>& students) { if (students.size() <= 1) return; int mid = students.size() / 2; std::vector<Student> left(students.begin(), students.begin() + mid); std::vector<Student> right(students.begin() + mid, students.end()); stable_sort_students(left); stable_sort_students(right); // 合并两个有序数组，保持稳定性 std::vector<Student> merged; size_t i = 0, j = 0; while (i < left.size() && j < right.size()) { if (left[i].score <= right[j].score) { merged.push_back(left[i++]); } else { merged.push_back(right[j++]); } } while (i < left.size()) merged.push_back(left[i++]); while (j < right.size()) merged.push_back(right[j++]); students = merged; } // 不稳定排序实现（选择排序） void unstable_sort_students(std::vector<Student>& students) { int n = students.size(); for (int i = 0; i < n - 1; ++i) { int min_index = i; for (int j = i + 1; j < n; ++j) { if (students[j].score < students[min_index].score) { min_index = j; } } // 直接交换可能破坏稳定性 if (min_index != i) { std::swap(students[i], students[min_index]); } } } void test_stable_vs_unstable_sort() { // 创建学生数组 std::vector<Student> students = { Student("Alice", 85), Student("Bob", 90), Student("Charlie", 85), // 与Alice分数相同 Student("David", 95) }; // 打印原始数组 std::cout << "Original students: " << std::endl; for (const auto& s : students) { std::cout << s.name << ": " << s.score << std::endl; } // 测试稳定排序 std::vector<Student> stable_sorted = students; stable_sort_students(stable_sorted); std::cout << "\nStable sorted by score: " << std::endl; for (const auto& s : stable_sorted) { std::cout << s.name << ": " << s.score << std::endl; } // 输出应为：Alice: 85, Charlie: 85, Bob: 90, David: 95（Alice在Charlie前面） // 测试不稳定排序 std::vector<Student> unstable_sorted = students; unstable_sort_students(unstable_sorted); std::cout << "\nUnstable sorted by score: " << std::endl; for (const auto& s : unstable_sorted) { std::cout << s.name << ": " << s.score << std::endl; } // 输出可能为：Charlie: 85, Alice: 85, Bob: 90, David: 95（Charlie可能在Alice前面） }
如何选择合适的排序算法？
选择排序算法时，需要考虑以下因素：
- 数据规模：
- 小数据量（n < 1000）：插入排序、选择排序等简单算法可能更高效（因为常数因子小）；
- 大数据量（n > 10000）：快速排序、归并排序、堆排序等O(n log n)的算法更合适。
- 数据分布：
- 已排序或接近排序的数据：插入排序（O(n)）、冒泡排序（优化版，O(n)）表现较好；
- 随机分布的数据：快速排序通常表现最好；
- 有大量重复元素的数据：三路快速排序（将数据分为小于、等于、大于基准的三部分）效果更好。
- 内存空间限制：
- 内存空间充足：归并排序、计数排序、桶排序等需要额外空间的算法；
- 内存空间有限：冒泡排序、选择排序、插入排序、堆排序等原地排序算法（空间复杂度O(1)）。
- 排序稳定性要求：
- 需要保持相等元素的相对顺序：归并排序、插入排序、冒泡排序、计数排序、桶排序、基数排序；
- 不需要保持相对顺序：快速排序、选择排序、堆排序、希尔排序。
- 实现复杂度：
- 简单实现：冒泡排序、选择排序、插入排序；
- 复杂实现：快速排序（处理边界情况）、归并排序、堆排序。
- 是否需要外部排序：
- 数据量太大，无法全部加载到内存：需要使用外部排序算法，如多路归并排序。
// 根据不同情况选择排序算法的示例 void sort_according_to_situation(std::vector<int>& arr, bool is_already_sorted = false, bool needs_stable = false) { int n = arr.size(); // 小数据量，直接使用插入排序 if (n < 100) { std::cout << "Using Insertion Sort for small data size." << std::endl; // 插入排序实现 for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = key; } return; } // 已排序或接近排序的数据，使用插入排序 if (is_already_sorted) { std::cout << "Using Insertion Sort for nearly sorted data." << std::endl; // 插入排序实现 for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = key; } return; } // 需要稳定排序 if (needs_stable) { std::cout << "Using Merge Sort for stable sorting." << std::endl; merge_sort(arr, 0, n - 1); // 使用前面实现的归并排序 return; } // 一般情况，使用快速排序 std::cout << "Using Quick Sort for general case." << std::endl; quick_sort(arr, 0, n - 1); // 使用前面实现的快速排序 } void test_sort_selection() { // 测试小数据量 std::vector<int> small_arr = {5, 3, 1, 4, 2}; sort_according_to_situation(small_arr); // 测试已排序数据 std::vector<int> sorted_arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; sort_according_to_situation(sorted_arr, true); // 测试需要稳定排序的情况 std::vector<int> need_stable_arr = {3, 1, 4, 1, 5, 9, 2, 6}; sort_according_to_situation(need_stable_arr, false, true); }- 数据规模：
6.2 查找算法
二分查找的原理？实现二分查找。
二分查找（Binary Search）：
- 原理：在有序数组中，通过不断将搜索范围缩小一半来查找目标值；
- 前提条件：数组必须是有序的（升序或降序）；
- 时间复杂度：O(log n)，远优于线性查找的O(n)；
- 空间复杂度：递归实现为O(log n)（递归栈），迭代实现为O(1)。
实现步骤：
- 初始化左边界left=0和右边界right=n-1（n为数组长度）；
- 当left <= right时，计算中间位置mid = left + (right - left) / 2（避免整数溢出）；
- 比较arr[mid]与目标值target：
- 如果arr[mid] == target，返回mid；
- 如果arr[mid] > target（升序），则target在左半部分，更新right=mid-1；
- 如果arr[mid] < target（升序），则target在右半部分，更新left=mid+1；
- 如果循环结束仍未找到target，返回-1表示未找到。
// 二分查找的迭代实现 int binary_search_iterative(const std::vector<int>& arr, int target) { int left = 0; int right = arr.size() - 1; while (left <= right) { // 计算中间位置（避免整数溢出的写法） int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; // 找到目标，返回索引 } else if (arr[mid] < target) { left = mid + 1; // 目标在右半部分 } else { right = mid - 1; // 目标在左半部分 } } return -1; // 未找到目标 } // 二分查找的递归实现 int binary_search_recursive(const std::vector<int>& arr, int left, int right, int target) { if (left > right) { return -1; // 基本情况：搜索范围为空 } int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; // 找到目标 } else if (arr[mid] < target) { return binary_search_recursive(arr, mid + 1, right, target); // 递归搜索右半部分 } else { return binary_search_recursive(arr, left, mid - 1, target); // 递归搜索左半部分 } } // 二分查找的变体：查找第一个等于目标值的元素 int binary_search_first_occurrence(const std::vector<int>& arr, int target) { int left = 0; int right = arr.size() - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { result = mid; // 记录找到的位置 right = mid - 1; // 继续在左半部分查找 } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } // 二分查找的变体：查找最后一个等于目标值的元素 int binary_search_last_occurrence(const std::vector<int>& arr, int target) { int left = 0; int right = arr.size() - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { result = mid; // 记录找到的位置 left = mid + 1; // 继续在右半部分查找 } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } void test_binary_search() { std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 测试标准二分查找 std::cout << "Index of 5 (iterative): " << binary_search_iterative(arr, 5) << std::endl; // 输出4 std::cout << "Index of 11 (iterative): " << binary_search_iterative(arr, 11) << std::endl; // 输出-1 std::cout << "Index of 7 (recursive): " << binary_search_recursive(arr, 0, arr.size() - 1, 7) << std::endl; // 输出6 // 测试有重复元素的情况 std::vector<int> arr_with_duplicates = {1, 2, 2, 3, 3, 3, 4, 5, 5}; std::cout << "First occurrence of 3: " << binary_search_first_occurrence(arr_with_duplicates, 3) << std::endl; // 输出3 std::cout << "Last occurrence of 3: " << binary_search_last_occurrence(arr_with_duplicates, 3) << std::endl; // 输出5 std::cout << "First occurrence of 5: " << binary_search_first_occurrence(arr_with_duplicates, 5) << std::endl; // 输出7 }
什么是哈希查找？它的优缺点是什么？
哈希查找（Hash Search）：
- 利用哈希表进行查找的算法；
- 通过哈希函数将键（key）映射到表中的一个位置，从而实现快速查找；
- 基本步骤：
- 构建哈希表：将数据元素的键通过哈希函数映射到哈希表中；
- 查找：计算目标键的哈希值，直接在哈希表中查找对应位置。
优点：
- 查找速度快：理想情况下，查找时间复杂度为O(1)；
- 适合大数据量：在数据量很大的情况下，仍能保持较高的查找效率；
- 实现简单：相对于平衡树等数据结构，哈希表的实现较为简单。
缺点：
- 需要额外空间：哈希表需要额外的空间来存储数据和处理冲突；
- 哈希冲突：不同的键可能映射到同一个哈希值，需要额外的处理机制（如链地址法、开放地址法等）；
- 不支持范围查询：哈希表不支持像有序数组那样的范围查询；
- 哈希函数设计：需要设计良好的哈希函数来减少冲突；
- 负载因子：当哈希表的负载因子过高时，性能会下降，需要进行扩容（rehashing）。
// 哈希查找示例（使用STL的unordered_map） void test_hash_search() { // 创建哈希表（使用unordered_map） std::unordered_map<std::string, int> hash_map; // 插入数据 hash_map["apple"] = 5; hash_map["banana"] = 7; hash_map["orange"] = 3; hash_map["grape"] = 10; hash_map["watermelon"] = 15; // 哈希查找 std::string key = "orange"; auto it = hash_map.find(key); if (it != hash_map.end()) { std::cout << "Found " << key << ": " << it->second << std::endl; // 输出：Found orange: 3 } else { std::cout << key << " not found." << std::endl; } // 查找不存在的元素 key = "pear"; it = hash_map.find(key); if (it != hash_map.end()) { std::cout << "Found " << key << ": " << it->second << std::endl; } else { std::cout << key << " not found." << std::endl; // 输出：pear not found. } // 测试哈希冲突（插入可能产生冲突的键） // 这里为了演示，我们使用两个可能产生冲突的键 std::string key1 = "test1"; std::string key2 = "test2"; // 假设与key1冲突 hash_map[key1] = 100; hash_map[key2] = 200; // 检查冲突后的查找是否正常 std::cout << "Found " << key1 << ": " << hash_map[key1] << std::endl; // 应该能找到test1 std::cout << "Found " << key2 << ": " << hash_map[key2] << std::endl; // 应该能找到test2 } // 自定义简单哈希表实现哈希查找 class SimpleHashMap { private: static const int TABLE_SIZE = 100; // 哈希表大小 // 哈希表节点结构 struct Node { std::string key; int value; Node* next; Node(const std::string& k, int v) : key(k), value(v), next(nullptr) {} }; Node* table[TABLE_SIZE]; // 哈希表数组 // 简单的哈希函数 int hash(const std::string& key) const { int hash_value = 0; for (char c : key) { hash_value = (hash_value * 31 + c) % TABLE_SIZE; // 使用简单的多项式哈希 } return hash_value; } public: SimpleHashMap() { // 初始化哈希表为nullptr for (int i = 0; i < TABLE_SIZE; ++i) { table[i] = nullptr; } } ~SimpleHashMap() { // 释放内存 for (int i = 0; i < TABLE_SIZE; ++i) { Node* current = table[i]; while (current) { Node* temp = current; current = current->next; delete temp; } } } // 插入元素 void insert(const std::string& key, int value) { int index = hash(key); // 检查key是否已存在 Node* current = table[index]; while (current) { if (current->key == key) { current->value = value; // 更新已存在的键的值 return; } current = current->next; } // 插入新节点（头插法） Node* new_node = new Node(key, value); new_node->next = table[index]; table[index] = new_node; } // 查找元素 bool search(const std::string& key, int& value) const { int index = hash(key); Node* current = table[index]; while (current) { if (current->key == key) { value = current->value; return true; } current = current->next; } return false; // 未找到 } }; void test_custom_hash_search() { SimpleHashMap hash_map; // 插入数据 hash_map.insert("one", 1); hash_map.insert("two", 2); hash_map.insert("three", 3); // 查找数据 int value; if (hash_map.search("two", value)) { std::cout << "Found 'two': " << value << std::endl; // 输出：Found 'two': 2 } else { std::cout << "'two' not found." << std::endl; } if (!hash_map.search("four", value)) { std::cout << "'four' not found." << std::endl; // 输出：'four' not found. } }
什么是二叉搜索树的查找？它的时间复杂度是多少？
二叉搜索树的查找：
- 利用二叉搜索树的特性进行查找的算法；
- 二叉搜索树的特性：左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值；
- 查找步骤：
- 从根节点开始；
- 如果目标值等于当前节点值，查找成功；
- 如果目标值小于当前节点值，在左子树中递归查找；
- 如果目标值大于当前节点值，在右子树中递归查找；
- 如果到达叶子节点仍未找到，则查找失败。
时间复杂度：
- 最佳情况：O(log n)，当二叉搜索树是平衡的；
- 平均情况：O(log n)，对于随机分布的数据；
- 最坏情况：O(n)，当二叉搜索树退化为链表（例如，插入有序数据时）。
平衡二叉搜索树（如AVL树、红黑树）：
- 确保树的高度始终保持在O(log n)，因此查找的最坏时间复杂度也是O(log n)；
- 适用于需要频繁查找、插入和删除的场景。
// 二叉搜索树的查找实现 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 递归实现二叉搜索树的查找 TreeNode* search_bst_recursive(TreeNode* root, int target) { if (root == nullptr || root->val == target) { return root; // 找到目标或到达叶子节点 } if (target < root->val) { return search_bst_recursive(root->left, target); // 在左子树中查找 } else { return search_bst_recursive(root->right, target); // 在右子树中查找 } } // 迭代实现二叉搜索树的查找 TreeNode* search_bst_iterative(TreeNode* root, int target) { TreeNode* current = root; while (current != nullptr) { if (current->val == target) { return current; // 找到目标 } else if (target < current->val) { current = current->left; // 向左子树移动 } else { current = current->right; // 向右子树移动 } } return nullptr; // 未找到目标 } // 构建一个简单的二叉搜索树 } TreeNode* build_bst() { // 构建的树结构： // 50 // / \ // 30 70 // / \ // 20 40 TreeNode* root = new TreeNode(50); root->left = new TreeNode(30); root->right = new TreeNode(70); root->left->left = new TreeNode(20); root->left->right = new TreeNode(40); return root; } // 释放二叉搜索树的内存 void destroy_bst(TreeNode* root) { if (root) { destroy_bst(root->left); destroy_bst(root->right); delete root; } } void test_bst_search() { TreeNode* root = build_bst(); // 测试递归查找 TreeNode* result1 = search_bst_recursive(root, 40); if (result1) { std::cout << "Found 40 recursively." << std::endl; // 输出：Found 40 recursively. } else { std::cout << "40 not found recursively." << std::endl; } result1 = search_bst_recursive(root, 60); if (result1) { std::cout << "Found 60 recursively." << std::endl; } else { std::cout << "60 not found recursively." << std::endl; // 输出：60 not found recursively. } // 测试迭代查找 TreeNode* result2 = search_bst_iterative(root, 30); if (result2) { std::cout << "Found 30 iteratively." << std::endl; // 输出：Found 30 iteratively. } else { std::cout << "30 not found iteratively." << std::endl; } result2 = search_bst_iterative(root, 80); if (result2) { std::cout << "Found 80 iteratively." << std::endl; } else { std::cout << "80 not found iteratively." << std::endl; // 输出：80 not found iteratively. } // 释放内存 destroy_bst(root); }
6.3 图的算法
深度优先搜索（DFS）和广度优先搜索（BFS）的区别？各适用什么场景？
深度优先搜索（DFS, Depth-First Search）：
- 基本思想：从起始节点出发，尽可能深地搜索图的分支，直到达到叶子节点或无法继续前进时，回溯到上一个节点，继续搜索其他分支；
- 实现方式：可以使用递归（系统栈）或显式栈；
- 访问顺序：类似树的前序遍历；
- 时间复杂度：O(V + E)，其中V是顶点数，E是边数；
- 空间复杂度：O(V)，用于存储访问标记和递归栈；
- 适用场景：
- 连通性问题（如判断图是否连通）；
- 拓扑排序；
- 寻找路径；
- 解决迷宫问题；
- 找出图中的所有路径；
- 检测环。
广度优先搜索（BFS, Breadth-First Search）：
- 基本思想：从起始节点出发，先访问所有相邻节点（一层），然后再依次访问这些节点的相邻节点（下一层），逐层扩展；
- 实现方式：使用队列；
- 访问顺序：类似树的层序遍历；
- 时间复杂度：O(V + E)，其中V是顶点数，E是边数；
- 空间复杂度：O(V)，用于存储访问标记和队列；
- 适用场景：
- 寻找最短路径（无权图）；
- 网络爬虫；
- 社交网络分析（如六度空间理论）；
- 迷宫寻路（最短路径）；
- 广播消息；
- 分层遍历。
// 图的表示（邻接表） class Graph { private: int num_vertices; // 顶点数 std::vector<std::vector<int>> adj_list; // 邻接表 public: Graph(int n) : num_vertices(n) { adj_list.resize(num_vertices); } void add_edge(int from, int to) { adj_list[from].push_back(to); adj_list[to].push_back(from); // 无向图，添加反向边 } // DFS实现（递归） void dfs(int start, std::vector<bool>& visited) { visited[start] = true; // 标记为已访问 std::cout << start << " "; // 访问当前节点 // 访问所有未访问的邻接节点 for (int neighbor : adj_list[start]) { if (!visited[neighbor]) { dfs(neighbor, visited); } } } // 公开的DFS函数 void dfs(int start) { std::vector<bool> visited(num_vertices, false); std::cout << "DFS starting from " << start << ": "; dfs(start, visited); std::cout << std::endl; } // BFS实现 void bfs(int start) { std::vector<bool> visited(num_vertices, false); std::queue<int> q; visited[start] = true; // 标记为已访问 q.push(start); // 入队 std::cout << "BFS starting from " << start << ": "; while (!q.empty()) { int current = q.front(); q.pop(); std::cout << current << " "; // 访问当前节点 // 将所有未访问的邻接节点入队 for (int neighbor : adj_list[current]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } std::cout << std::endl; } // 使用BFS寻找最短路径（无权图） std::vector<int> find_shortest_path(int start, int end) { std::vector<bool> visited(num_vertices, false); std::vector<int> parent(num_vertices, -1); // 记录父节点 std::queue<int> q; visited[start] = true; q.push(start); // BFS遍历，记录父节点 while (!q.empty()) { int current = q.front(); q.pop(); if (current == end) break; // 找到目标节点 for (int neighbor : adj_list[current]) { if (!visited[neighbor]) { visited[neighbor] = true; parent[neighbor] = current; q.push(neighbor); } } } // 重构路径 std::vector<int> path; if (!visited[end]) { return path; // 无法到达 } // 从终点回溯到起点 for (int v = end; v != -1; v = parent[v]) { path.push_back(v); } // 反转路径，使其从起点到终点 std::reverse(path.begin(), path.end()); return path; } }; void test_graph_traversal() { // 创建一个图： // 0 -- 1 -- 3 // | | // 2 -- 4 Graph g(5); g.add_edge(0, 1); g.add_edge(0, 2); g.add_edge(1, 3); g.add_edge(1, 4); g.add_edge(2, 4); // 测试DFS g.dfs(0); // 可能的输出：0 1 3 4 2（具体顺序可能因邻接表的存储顺序而异） // 测试BFS g.bfs(0); // 输出：0 1 2 3 4（按层访问） // 测试最短路径 std::vector<int> path = g.find_shortest_path(0, 3); std::cout << "Shortest path from 0 to 3: "; for (int v : path) { std::cout << v << " "; // 输出：0 1 3 } std::cout << std::endl; path = g.find_shortest_path(2, 3); std::cout << "Shortest path from 2 to 3: "; for (int v : path) { std::cout << v << " "; // 输出：2 0 1 3 或 2 4 1 3（取决于邻接表的顺序） } std::cout << std::endl; }
什么是Dijkstra算法？它的时间复杂度是多少？
Dijkstra算法：
- 用于解决带权有向图或无向图中单源最短路径问题的经典算法；
- 由荷兰计算机科学家Edsger W. Dijkstra于1956年提出；
- 基本思想：
- 维护一个距离数组dist，其中dist[v]表示从起点到顶点v的最短距离估计；
- 初始时，dist[start] = 0，其余顶点的dist值设为无穷大；
- 使用一个优先队列（最小堆）来选择当前距离最小的顶点u；
- 对于顶点u的每个邻接顶点v，尝试通过u更新到v的最短距离：如果dist[u] + weight(u,v) < dist[v]，则更新dist[v]；
- 重复步骤3和4，直到所有顶点都被处理。
时间复杂度：
- 取决于优先队列的实现方式：
- 使用二叉堆（Binary Heap）实现优先队列：O((V + E) log V)，其中V是顶点数，E是边数；
- 使用斐波那契堆（Fibonacci Heap）实现优先队列：O(V log V + E)，但在实际应用中较少使用；
- 使用简单的数组实现（每次线性查找最小距离的顶点）：O(V²)，适用于稠密图。
- 取决于优先队列的实现方式：
限制：Dijkstra算法不能处理负权边，因为负权边可能会导致已经处理过的顶点需要重新处理。
适用场景：
- 寻找带权图中的单源最短路径；
- 网络路由协议；
- 地图导航中的路径规划；
- 机器人路径规划。
// Dijkstra算法实现（使用优先队列优化） void dijkstra(const std::vector<std::vector<std::pair<int, int>>>& graph, int start, std::vector<int>& dist) { int n = graph.size(); dist.assign(n, INT_MAX); // 初始化为无穷大 dist[start] = 0; // 起点到自己的距离为0 // 优先队列：存储（距离，顶点）对，按距离升序排列 // 使用greater<>来创建最小堆 std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq; pq.push({0, start}); while (!pq.empty()) { int u_dist = pq.top().first; int u = pq.top().second; pq.pop(); // 如果当前取出的距离大于已知距离，跳过（已经处理过更优的路径） if (u_dist > dist[u]) { continue; } // 遍历u的所有邻接顶点 for (const auto& edge : graph[u]) { int v = edge.first; // 邻接顶点 int weight = edge.second; // 边的权重 // 尝试通过u更新到v的最短距离 if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.push({dist[v], v}); } } } } // 创建一个带权图并测试Dijkstra算法 void test_dijkstra() { // 创建一个带权图，邻接表表示 // 0 --(2)-- 1 --(4)-- 3 // | | //(1) (3) // | | // 2 --(2)-- 4 --(1)-- 5 int n = 6; // 6个顶点 std::vector<std::vector<std::pair<int, int>>> graph(n); // 添加边（目标顶点，权重） graph[0].emplace_back(1, 2); graph[0].emplace_back(2, 1); graph[1].emplace_back(0, 2); graph[1].emplace_back(3, 4); graph[1].emplace_back(4, 3); graph[2].emplace_back(0, 1); graph[2].emplace_back(4, 2); graph[3].emplace_back(1, 4); graph[4].emplace_back(1, 3); graph[4].emplace_back(2, 2); graph[4].emplace_back(5, 1); graph[5].emplace_back(4, 1); // 测试从顶点0出发的最短路径 std::vector<int> dist; dijkstra(graph, 0, dist); std::cout << "Shortest distances from node 0: " << std::endl; for (int i = 0; i < n; ++i) { std::cout << "To node " << i << ": " << dist[i] << std::endl; } // 输出应为： // To node 0: 0 // To node 1: 2 // To node 2: 1 // To node 3: 6 (0->1->3) // To node 4: 3 (0->2->4) // To node 5: 4 (0->2->4->5) // 测试从顶点2出发的最短路径 dijkstra(graph, 2, dist); std::cout << "\nShortest distances from node 2: " << std::endl; for (int i = 0; i < n; ++i) { std::cout << "To node " << i << ": " << dist[i] << std::endl; } }
什么是拓扑排序？如何实现？
拓扑排序（Topological Sorting）：
- 是一种对有向无环图（DAG, Directed Acyclic Graph）的顶点进行排序的算法；
- 排序后的顶点序列满足：对于图中的每条有向边(u, v)，顶点u在排序结果中都出现在顶点v之前；
- 有向无环图至少有一个拓扑排序；如果图中有环，则无法进行拓扑排序。
实现方法：
- Kahn算法（基于入度）：
- 计算图中所有顶点的入度；
- 将所有入度为0的顶点加入队列；
- 不断从队列中取出顶点u，将其加入结果序列，并减少其所有邻接顶点的入度；
- 如果某个邻接顶点的入度变为0，则将其加入队列；
- 重复步骤3和4，直到队列为空；
- 检查结果序列的长度是否等于顶点数。如果相等，则得到一个拓扑排序；否则，图中存在环。
- DFS算法（基于深度优先搜索）：
- 对图中的每个未访问顶点，进行DFS；
- 在DFS过程中，标记顶点为“正在访问”状态；
- 递归访问其所有邻接顶点；
- 当一个顶点的所有邻接顶点都被访问后，将该顶点标记为“已访问”，并将其加入结果序列；
- 最后，将结果序列反转，得到拓扑排序。
- Kahn算法（基于入度）：
时间复杂度：两种方法的时间复杂度均为O(V + E)，其中V是顶点数，E是边数。
适用场景：
- 任务调度（确定任务的执行顺序）；
- 依赖关系分析；
- 编译器中的依赖解析；
- 构建系统中的目标构建顺序。
// 拓扑排序实现 // Kahn算法实现拓扑排序 std::vector<int> topological_sort_kahn(const std::vector<std::vector<int>>& graph) { int n = graph.size(); std::vector<int> in_degree(n, 0); // 存储每个顶点的入度 std::vector<int> result; // 存储拓扑排序结果 // 计算每个顶点的入度 for (int u = 0; u < n; ++u) { for (int v : graph[u]) { in_degree[v]++; } } // 将所有入度为0的顶点加入队列 std::queue<int> q; for (int i = 0; i < n; ++i) { if (in_degree[i] == 0) { q.push(i); } } // 执行拓扑排序 while (!q.empty()) { int u = q.front(); q.pop(); result.push_back(u); // 减少所有邻接顶点的入度 for (int v : graph[u]) { in_degree[v]--; if (in_degree[v] == 0) { q.push(v); } } } // 检查是否存在环 if (result.size() != n) { return {}; // 图中存在环，无法进行拓扑排序 } return result; } // DFS算法实现拓扑排序 bool dfs_topo(int u, const std::vector<std::vector<int>>& graph, std::vector<bool>& visited, std::vector<bool>& rec_stack, std::vector<int>& result) { visited[u] = true; rec_stack[u] = true; // 标记为正在访问（递归栈中） // 访问所有邻接顶点 for (int v : graph[u]) { if (!visited[v]) { if (!dfs_topo(v, graph, visited, rec_stack, result)) { return false; // 发现环 } } else if (rec_stack[v]) { return false; // 发现环（回边） } } rec_stack[u] = false; // 回溯时标记为不在递归栈中 result.push_back(u); // 将顶点加入结果（后序遍历） return true; } std::vector<int> topological_sort_dfs(const std::vector<std::vector<int>>& graph) { int n = graph.size(); std::vector<bool> visited(n, false); std::vector<bool> rec_stack(n, false); // 用于检测环 std::vector<int> result; // 对每个未访问的顶点进行DFS for (int i = 0; i < n; ++i) { if (!visited[i]) { if (!dfs_topo(i, graph, visited, rec_stack, result)) { return {}; // 图中存在环，无法进行拓扑排序 } } } // DFS得到的是逆序的拓扑排序，需要反转 std::reverse(result.begin(), result.end()); return result; } // 创建一个有向无环图并测试拓扑排序 void test_topological_sort() { // 创建一个DAG： // 0 --> 1 --> 3 // | | // v v // 2 --> 4 int n = 5; std::vector<std::vector<int>> graph(n); graph[0].push_back(1); graph[0].push_back(2); graph[1].push_back(3); graph[1].push_back(4); graph[2].push_back(4); // 测试Kahn算法 std::vector<int> result_kahn = topological_sort_kahn(graph); std::cout << "Topological sort using Kahn's algorithm: "; for (int v : result_kahn) { std::cout << v << " "; // 可能的输出：0 1 2 3 4 或 0 2 1 4 3 等 } std::cout << std::endl; // 测试DFS算法 std::vector<int> result_dfs = topological_sort_dfs(graph); std::cout << "Topological sort using DFS: "; for (int v : result_dfs) { std::cout << v << " "; // 可能的输出：0 2 1 4 3 或 0 1 3 2 4 等 } std::cout << std::endl; // 测试有环的图 // 创建一个有环的图：0 --> 1 --> 2 --> 0 std::vector<std::vector<int>> cyclic_graph(3); cyclic_graph[0].push_back(1); cyclic_graph[1].push_back(2); cyclic_graph[2].push_back(0); std::vector<int> cyclic_result = topological_sort_kahn(cyclic_graph); if (cyclic_result.empty()) { std::cout << "Cyclic graph: Topological sort is not possible." << std::endl; } }