蓝桥杯备考——算法

一、排序

冒泡排序、选择排序、插入排序、 快速排序、归并排序、桶排序
  
二、摆列

三、二分查找与二分答案

四、搜索（DFS）

DFS（DFS根本、回溯、剪枝、影象化）
1.DFS算法（深度优先搜索算法）

深度优先搜索（ DFS ）是一种用于遍历或搜索图或树的算法，它从起始节点开始，沿着一条路径不绝深入直到无法继承为止，然后回溯到上一个节点继承探索。 DFS 使用栈来记录遍历的路径，它优先访问近来添加到栈的节点。
DFS 的重要长处是简单且易于实现，它不须要额外的数据结构来记录节点的访问环境，仅使用栈来存储遍历路径。然而， DFS 大概会陷入无穷循环中，由于它不思量节点是否已经访问过。
     对于一个连通图，深度优先搜索遍历的过程如下：
  （1）从图中某个顶点v出发，访问v；
  （2）找到刚访问过的顶点的第一个未被访问的毗邻点，访问该顶点。 以该顶点为新顶点，重 复此步调， 直至刚访问过的顶点没有未被访问的毗邻点为止。
  (3)返回前一个访问过的且仍有未被访问的毗邻点的顶点，找出该顶点的下一个未被访问的毗邻点， 访问该顶点。
  (4)重复步调 (2) 和(3), 直至图中全部顶点都被访问过，搜索竣事。
  

顶点访问序列：v1 -> v2 -> v4 -> v8 -> v5 -> v3 -> v6 -> v7
DFS 使用栈来记录遍历的路径，它优先访问近来添加到栈的节点。
  显然， 深度优先搜索遍历连通图是一个递归的过程。 为了在遍历过程中便千区分顶点是否已
  被访问，需附设访问标志数组 visited[n] , 其初值为 "false", 一旦某个顶点被访问，则其相应的分
量置为 "true"。  
python语言：

1. # 图的DFS遍历
2. def dfs(graph, start, visited):
3.     # 访问当前节点
4.     print(start, end=' ')
5.     # 标记当前节点为已访问
6.     visited[start] = True
7.     # 遍历当前节点的邻居节点
8.     for neighbor in graph[start]:
9.         # 如果邻居节点未被访问，则继续深度优先搜索
10.         if not visited[neighbor]:
11.             dfs(graph, neighbor, visited)
13. # 图的邻接表表示
14. graph = {
15.     '1': ['2', '3'],
16.     '2': ['2', '4', '5'],
17.     '3': ['1', '6', '7'],
18.     '4': ['2','8'],
19.     '5': ['2','8'],
20.     '6': ['3','7'],
21.     '7': ['3','6'],
22.     '8': ['4','5']
23. }
25. # 标记节点是否已访问的列表
26. visited = {node: False for node in graph}
28. # 从节点A开始进行DFS遍历
29. print("DFS遍历结果：")
30. dfs(graph, '1', visited)

复制代码

C++ / C语言：

算法1.深度优先搜索遍历连通图

1. // 1. 深度优先搜索遍历连通图
2. bool visited[MVNum];     

复制代码