5天速成数据结构与算法-Day2
|
数据结构,算法
|
51

2711 字
|
1 小时
本文最后更新于22 天前，其中的信息可能已经过时，如有错误请发送邮件到big_fw@foxmail.com

5天速成数据结构与算法-Day2

图论算法

BFS

介绍

广度优先搜索(Breadth-First Search, BFS)是一种图遍历算法，它从图的某一顶点开始，先访问该顶点的所有相邻顶点，然后再按照同样的方式访问这些相邻顶点的相邻顶点，层层推进，直到访问完图中所有可达顶点。BFS的特点是”先进先出”，即优先访问距离起始顶点最近的顶点。

算法步骤

  1. 选择图中的一个起始顶点，将其标记为已访问，并放入队列中
  2. 从队列中取出队首顶点，访问该顶点
  3. 将该顶点的所有未访问过的相邻顶点标记为已访问，并放入队列中
  4. 重复步骤2和3，直到队列为空

算法实现

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
​
class BFSGraphTraversal {
private:
    // 邻接表表示的图
    std::unordered_map<int, std::vector<int>> graph;
​
public:
    // 添加顶点
    void addVertex(int vertex) {
        if (graph.find(vertex) == graph.end()) {
            graph[vertex] = std::vector<int>();
        }
    }
    
    // 添加边
    void addEdge(int v1, int v2) {
        if (graph.find(v1) == graph.end()) {
            addVertex(v1);
        }
        if (graph.find(v2) == graph.end()) {
            addVertex(v2);
        }
        
        graph[v1].push_back(v2);
        // 对于无向图，需要添加反向边
        // graph[v2].push_back(v1);
    }
    
    // BFS遍历
    void bfs(int startVertex) {
        if (graph.find(startVertex) == graph.end()) {
            std::cout << "起始顶点不存在" << std::endl;
            return;
        }
        
        // 记录已访问的顶点
        std::unordered_set<int> visited;
        // 队列用于BFS
        std::queue<int> queue;
        
        // 将起始顶点标记为已访问并入队
        visited.insert(startVertex);
        queue.push(startVertex);
        
        while (!queue.empty()) {
            // 出队并访问
            int currentVertex = queue.front();
            queue.pop();
            std::cout << currentVertex << " ";
            
            // 获取当前顶点的所有邻接顶点
            std::vector<int> neighbors;
            if (graph.find(currentVertex) != graph.end()) {
                neighbors = graph[currentVertex];
            }
            
            // 对每个未访问的邻接顶点，标记为已访问并入队
            for (int neighbor : neighbors) {
                if (visited.find(neighbor) == visited.end()) {
                    visited.insert(neighbor);
                    queue.push(neighbor);
                }
            }
        }
    }
};

Kruskal最小生成树算法

介绍

Kruskal算法是一种用于带权无向图的最小生成树算法，该算法基于贪心策略，通过选择权值最小的边构建最小生成树。

最小生成树是图中连接所有顶点的一个子图，它是一棵树（无环连通图），且所有边的权重总和最小。

算法步骤

  1. 将图中所有边按权重从小到大排序
  2. 创建一个森林（每个顶点初始时是一棵独立的树）
  3. 按排序后的顺序处理每条边(u, v)：
    • 如果顶点u和v不在同一个连通分量中（即不在同一棵树中）
    • 则将这条边加入最小生成树中
    • 合并包含u和v的两棵树（连通分量）
  4. 重复步骤3，直到最小生成树包含图中所有顶点（即V-1条边，其中V是顶点数）

算法详解

以共有6个顶点(A-F)和10条边的带权无向图为例：

  • A-B：权重3
  • A-C：权重1
  • A-D：权重6
  • B-C：权重5
  • B-E：权重4
  • C-D：权重5
  • C-E：权重6
  • C-F：权重4
  • D-F：权重2
  • E-F：权重6
img
初始化：
  • 按权重排序所有边：
    1. A-C：权重1
    2. D-F：权重2
    3. A-B：权重3
    4. B-E：权重4
    5. C-F：权重4
    6. B-C：权重5
    7. C-D：权重5
    8. A-D：权重6
    9. C-E：权重6
    10. E-F：权重6
  • 初始森林：每个顶点各为一棵树 {A}, {B}, {C}, {D}, {E}, {F}
执行Kruskal算法：
  1. 处理边A-C（权重1）：
    • A和C不在同一连通分量中
    • 将边A-C加入最小生成树
    • 合并顶点A和C的连通分量: {A,C}, {B}, {D}, {E}, {F}
  2. 处理边D-F（权重2）：
    • D和F不在同一连通分量中
    • 将边D-F加入最小生成树
    • 合并顶点D和F的连通分量: {A,C}, {B}, {D,F}, {E}
  3. 处理边A-B（权重3）：
    • A和B不在同一连通分量中
    • 将边A-B加入最小生成树
    • 合并顶点A和B的连通分量: {A,B,C}, {D,F}, {E}
  4. 处理边B-E（权重4）：
    • B和E不在同一连通分量中
    • 将边B-E加入最小生成树
    • 合并顶点B和E的连通分量: {A,B,C,E}, {D,F}
  5. 处理边C-F（权重4）：
    • C和F不在同一连通分量中
    • 将边C-F加入最小生成树
    • 合并顶点C和F的连通分量: {A,B,C,D,E,F}
  6. 所有顶点已经在同一连通分量中，算法结束

我们已经选择了5条边（对于6个顶点的图，最小生成树需要5条边），因此不再处理剩余的边：

  • B-C（权重5）：不处理
  • C-D（权重5）：不处理
  • A-D（权重6）：不处理
  • C-E（权重6）：不处理
  • E-F（权重6）：不处理
最终结果：

最小生成树包含以下边：

  • A-C（权重1）
  • D-F（权重2）
  • A-B（权重3）
  • B-E（权重4）
  • C-F（权重4）

总权重：1 + 2 + 3 + 4 + 4 = 14

核心特性
  • 贪心策略：每次选择权重最小的边，只要它不会形成环
  • 并查集：使用并查集数据结构高效实现连通分量的管理和合并
  • 最优性：保证得到的生成树总权重最小
  • 时间复杂度：O(E log E)或O(E log V)，其中E为边数，V为顶点数
  • 空间复杂度：O(E + V)，主要用于存储边、顶点和并查集

动态规划（DP）

最长递增子序列LIS

介绍

最长递增子序列（Longest Increasing Subsequence, LIS）是一个经典的动态规划问题，目标是找出一个给定序列中最长的子序列，要求该子序列中的所有元素按照严格递增的顺序排列。注意，子序列不要求连续，但要保持原序列中元素的相对顺序。

最长递增子序列问题可以通过多种方法解决，其中动态规划是最为经典和直观的方法，时间复杂度为O(n²)，n是序列长度。还有使用二分查找优化的方法可以将时间复杂度降低到O(n log n)。

算法步骤

  1. 定义状态：dp[i]表示以第i个元素结尾的最长递增子序列的长度
  2. 初始化：所有dp[i]初始值为1（至少包含自身一个元素）
  3. 状态转移：对于每个位置i，检查所有在它之前的位置j：
    • 如果nums[i] > nums[j]，则可以将nums[i]接在以nums[j]结尾的子序列之后
    • dp[i] = max(dp[i], dp[j] + 1)
  4. 结果：max(dp[0], dp[1], …, dp[n-1])

算法详解

为了更好地理解最长递增子序列的动态规划求解过程，我们以序列 [10, 9, 2, 5, 3, 7, 101, 18] 为例，详细分析整个计算流程：

初始化阶段

创建长度为8的dp数组，并将所有元素初始化为1（表示每个元素自身就是一个长度为1的递增子序列）

dp = [1, 1, 1, 1, 1, 1, 1, 1]
动态规划填表过程

从i=1开始，对每个位置i进行状态转移：

  • i=1, nums[1]=9：
    • 检查j=0, nums[0]=10：由于9<10，不符合递增条件
    • dp[1]保持为1
    • 当前dp = [1, 1, 1, 1, 1, 1, 1, 1]
  • i=2, nums[2]=2：
    • 检查j=0, nums[0]=10：由于2<10，不符合递增条件
    • 检查j=1, nums[1]=9：由于2<9，不符合递增条件
    • dp[2]保持为1
    • 当前dp = [1, 1, 1, 1, 1, 1, 1, 1]
  • i=3, nums[3]=5：
    • 检查j=0, nums[0]=10：由于5<10，不符合递增条件
    • 检查j=1, nums[1]=9：由于5<9，不符合递增条件
    • 检查j=2, nums[2]=2：由于5>2，符合递增条件，dp[3]=max(dp[3], dp[2]+1)=max(1,2)=2
    • dp[3]=2，表示以5结尾的LIS长度为2
    • 当前dp = [1, 1, 1, 2, 1, 1, 1, 1]
  • i=4, nums[4]=3：
    • 检查j=0,1,2,3：只有当j=2时，nums[4]>nums[2]（3>2），更新dp[4]=2
    • 当前dp = [1, 1, 1, 2, 2, 1, 1, 1]
  • i=5, nums[5]=7：
    • 检查j=0,1：不符合递增条件
    • 检查j=2：由于7>2，更新dp[5]=2
    • 检查j=3：由于7>5，更新dp[5]=max(dp[5], dp[3]+1)=max(2,3)=3
    • 检查j=4：由于7>3，更新dp[5]=max(dp[5], dp[4]+1)=max(3,3)=3
    • 当前dp = [1, 1, 1, 2, 2, 3, 1, 1]
  • i=6, nums[6]=101：
    • 对于j=0到5，所有元素都小于101，找出最大的dp[j]+1
    • 最大的dp[j]是dp[5]=3，因此dp[6]=4
    • 当前dp = [1, 1, 1, 2, 2, 3, 4, 1]
  • i=7, nums[7]=18：
    • 对于j=0到6，检查哪些元素小于18
    • 找到j=2,3,4,5时符合条件，最大的dp[j]是dp[5]=3
    • 更新dp[7]=dp[5]+1=4
    • 最终dp = [1, 1, 1, 2, 2, 3, 4, 4]
结果计算
  1. dp数组中的最大值就是最长递增子序列的长度：
最大值 = max(dp) = 4
找出具体的子序列
  1. 如果要得到具体的LIS，我们需要回溯：
    • 从dp值等于最大长度的位置开始追踪
    • 在本例中，dp[6]=dp[7]=4，我们可以从索引7（值为18）开始
    • 查找索引j<7，使得dp[j]=3且nums[j]<nums[7]，找到j=5（值为7）
    • 然后查找索引j<5，使得dp[j]=2且nums[j]<nums[5]，找到j=3（值为5）
    • 继续查找索引j<3，使得dp[j]=1且nums[j]<nums[3]，找到j=2（值为2）
    • 最终得到LIS为[2,5,7,18]
图示演示

下面是各步骤的dp数组变化过程的示意图：

索引 i01234567
nums[i]109253710118
初始dp11111111
i=1后11111111
i=2后11111111
i=3后11121111
i=4后11122111
i=5后11122311
i=6后11122341
i=7后11122344
核心特性
  • 子结构最优性：问题的最优解包含子问题的最优解
  • 状态定义明确：dp[i]表示以第i个元素结尾的LIS长度
  • 时间复杂度：基本实现O(n²)，优化版本O(n log n)
  • 空间复杂度：O(n)，需要一维dp数组
  • 非连续性：子序列元素在原序列中不要求连续

基础实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
​
class LongestIncreasingSubsequence {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        
        int n = nums.size();
        vector<int> dp(n, 1); // 初始化每个位置的LIS长度为1
        
        int maxLength = 1;
        
        // 动态规划过程
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxLength = max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
    
    vector<int> getLIS(vector<int>& nums) {
        if (nums.empty()) {
            return {};
        }
        
        int n = nums.size();
        vector<int> dp(n, 1);
        vector<int> prev(n, -1); // 记录前驱节点
        
        int maxLength = 1;
        int endIndex = 0;
        
        // 动态规划过程
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j; // 记录前驱
                }
            }
            if (dp[i] > maxLength) {
                maxLength = dp[i];
                endIndex = i; // 记录最长子序列的结束位置
            }
        }
        
        // 根据前驱数组构造LIS
        vector<int> lis;
        while (endIndex != -1) {
            lis.push_back(nums[endIndex]);
            endIndex = prev[endIndex];
        }
        
        reverse(lis.begin(), lis.end()); // 需要反转
        
        return lis;
    }
};
​
int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    
    LongestIncreasingSubsequence solution;
    int lisLength = solution.lengthOfLIS(nums);
    vector<int> lis = solution.getLIS(nums);
    
    cout << "数组: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    cout << "最长递增子序列的长度: " << lisLength << endl;
    
    cout << "一个最长递增子序列: ";
    for (int num : lis) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}
​
文末附加内容
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
5天速成数据结构与算法-Day1

							
							

							
5天速成数据结构与算法-Day3

							
							

							
动态规划入门：从0-1背包到最长公共子序列