wang域名注册网站,珠海百度快速优化,东莞企业营销,商会网站怎么做一、排序
冒泡排序、选择排序、插入排序、 快速排序、归并排序、桶排序 二、枚举
三、二分查找与二分答案
四、搜索#xff08;DFS#xff09;
DFS#xff08;DFS基础、回溯、剪枝、记忆化#xff09;
1.DFS算法#xff08;深度优先搜索算法#xff09;
深度优先搜…一、排序
冒泡排序、选择排序、插入排序、 快速排序、归并排序、桶排序 二、枚举
三、二分查找与二分答案
四、搜索DFS
DFSDFS基础、回溯、剪枝、记忆化
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语言
# 图的DFS遍历
def dfs(graph, start, visited):# 访问当前节点print(start, end )# 标记当前节点为已访问visited[start] True# 遍历当前节点的邻居节点for neighbor in graph[start]:# 如果邻居节点未被访问则继续深度优先搜索if not visited[neighbor]:dfs(graph, neighbor, visited)# 图的邻接表表示
graph {1: [2, 3],2: [2, 4, 5],3: [1, 6, 7],4: [2,8],5: [2,8],6: [3,7],7: [3,6],8: [4,5]
}# 标记节点是否已访问的列表
visited {node: False for node in graph}# 从节点A开始进行DFS遍历
print(DFS遍历结果)
dfs(graph, 1, visited)
C / C语言
算法1.深度优先搜索遍历连通图
// 1. 深度优先搜索遍历连通图
bool visited[MVNum]; // 访问标志数组其初值设为“false”
void DFS(Graph G, int v)
{ // 从第v个顶点出发 递归地深度优先遍历图Gcout v; visited[v] true;for (wFirstAdjVex(G,v); w0; wNextAdjVex(G,v,w))// 依次检查v的所有邻接点wFirstAdjVex(G,v)表示v的第一个邻接点// NextAdjVex(G,v,w)表示v相对于w的下一个邻接点w0表示存在邻接点if (!visited[w]) DFS(G,w); // 对v的尚未访问的邻接点w递归调用DFS
}
算法2.深度优先搜索遍历 非连通图
若是非连通图 上述遍历过程执行之后 图中一定还有顶点未被访间需要从图中另选
一个未被访问的顶点作为起始点 重复上述深度优先搜索过程 直到图中所有顶点均被访问
过为止。这样 要实现对非连通图的遍历需要循环调用算法 1, 具体实现如算法 2所示。 void DFSTraverse(Graph G)
{ //对非连通图G做深度优先遍历for(vO;vG.vexnum;v) visited[v]false; // 访问标志数组初始化for(vO;vG.vexnum;v) // 循环调用算法1if(!visited[v]) DFS(G,v); // 对尚未访问的顶点调用DFS
} 算法 3 采用 邻接矩阵 表示图的深度优先搜索遍历 void DFS_AM(AMGraph G,int v)
{ // 图G为 邻接矩阵类型从第v个顶点出发深度优先搜索遍历图Gcoutv; visited[v]true; // 访问第v个顶点并置访问标志数组相应分址值为truefor(wO; wG.vexnum; w) // 依次检查邻接矩阵 v所在的行if((G.arcs[v][w] !O) (!visited[w])) DFS(G,w); //G.arcs[v][w] ! 0表示w是v的邻接点 如果w未访问 则递归调用DFS
} 算法 4 采用邻接表表示图的深度优先搜索遍历 void DFS_AL (ALGraph G,int v)
{ //图G为 邻接表 类型 从第v个顶点出发深度优先搜索遍历图Gcoutv; visited[v]true; // 访问第v个顶点并置访问标志数组相应分量值为truepG.vertices[v] .firstarc; //p指向v的边链表的第一个边结点while(p!NULL) // 边结点非空{wp-adjvex; // 表示w是v的邻接点if(!visited[w]) DFS(G,w); // 如果w未访问 则递归调用DFSpp-nextarc; //p指向下一个边结点}
}
例题1.最大连通
问题描述填空题
小兰有一个30行60列的数字矩阵矩阵中的每个数都是0或1。 110010000011111110101001001001101010111011011011101001111110010000000001010001101100000010010110001111100010101100011110 001011101000100011111111111010000010010101010111001000010100 101100001101011101101011011001000110111111010000000110110000 010101100100010000111000100111100110001110111101010011001011 010011011010011110111101111001001001010111110001101000100011 101001011000110100001101011000000110110110100100110111101011 101111000000101000111001100010110000100110001001000101011001 001110111010001011110000001111100001010101001110011010101110 001010101000110001011111001010111111100110000011011111101010 011111100011001110100101001011110011000101011000100111001011 011010001101011110011011111010111110010100101000110111010110 001110000111100100101110001011101010001100010111110111011011 111100001000001100010110101100111001001111100100110000001101 001110010000000111011110000011000010101000111000000110101101 100100011101011111001101001010011111110010111101000010000111 110010100110101100001101111101010011000110101100000110001010 110101101100001110000100010001001010100010110100100001000011 100100000100001101010101001101000101101000000101111110001010 101101011010101000111110110000110100000010011111111100110010 101111000100000100011000010001011111001010010001010110001010 001010001110101010000100010011101001010101101101010111100101 001111110000101100010111111100000100101010000001011101100001 101011110010000010010110000100001010011111100011011000110010 011110010100011101100101111101000001011100001011010001110011 000101000101000010010010110111000010101111001101100110011100 100011100110011111000110011001111100001110110111001001000111 111011000110001000110111011001011110010010010110101000011111 011110011110110110011011001011010000100100101010110000010011 010011110011100101010101111010001001001111101111101110011101 如果从一个标为1的位置可以通过上下左右走到另一个标为1的位置则称两个位置连通。与某一个标为1的位置连通的所有位置包括自己组成一个连通分块。
请问矩阵中最大的连通分块有多大
答案
import os
import sysdef dfs(x, y, num): # x,y是当前的位置num是最大连通的数量vis[x][y] 1 # 表明这个位置已经被搜素过了for dx,dy in [(1, 0), (-1, 0), (0,1), (0, -1)]: # 标准的上下左右搜索current_x x dxcurrent_y y dyif 0 current_x 30 and 0 current_y 60: # 边界限制try:if vis[current_x][current_y] ! 1 and data[current_x][current_y] 1: # 上下左右有位置没有被探索同时还是字符串的1num dfs(current_x,current_y,num)except: # 这里是方便找到如果输入错误是在哪用来检查循环条件是否写错print(current_x)print(current_y)return num 1 # 本身的1加上所有与它相连的numdata [
110010000011111110101001001001101010111011011011101001111110,010000000001010001101100000010010110001111100010101100011110,001011101000100011111111111010000010010101010111001000010100,101100001101011101101011011001000110111111010000000110110000,010101100100010000111000100111100110001110111101010011001011,010011011010011110111101111001001001010111110001101000100011,101001011000110100001101011000000110110110100100110111101011,101111000000101000111001100010110000100110001001000101011001,001110111010001011110000001111100001010101001110011010101110,001010101000110001011111001010111111100110000011011111101010,011111100011001110100101001011110011000101011000100111001011,011010001101011110011011111010111110010100101000110111010110,001110000111100100101110001011101010001100010111110111011011,111100001000001100010110101100111001001111100100110000001101,001110010000000111011110000011000010101000111000000110101101,100100011101011111001101001010011111110010111101000010000111,110010100110101100001101111101010011000110101100000110001010,110101101100001110000100010001001010100010110100100001000011,100100000100001101010101001101000101101000000101111110001010,101101011010101000111110110000110100000010011111111100110010,101111000100000100011000010001011111001010010001010110001010,001010001110101010000100010011101001010101101101010111100101,001111110000101100010111111100000100101010000001011101100001,101011110010000010010110000100001010011111100011011000110010,011110010100011101100101111101000001011100001011010001110011,000101000101000010010010110111000010101111001101100110011100,100011100110011111000110011001111100001110110111001001000111,111011000110001000110111011001011110010010010110101000011111,011110011110110110011011001011010000100100101010110000010011,010011110011100101010101111010001001001111101111101110011101]
res 0
vis [[0 for i in range(60)] for j in range(30)] # 标记数组
for i in range(30): # i和j是位置for j in range(60):if data[i][j] 1 and vis[i][j] 0:num 0num dfs(i,j,num)res max(num, res)
print(res)
例题2. 2. 广度优先搜索 BFS 算法
是一种用于遍历或搜索图或树的算法它从起始节点开始逐层地向外扩展先访问当前节点的所有邻居节点然后再访问邻居节点的邻居节点直到遍历完所有节点。
BFS 使用队列来记录遍历的路径它优先访问最早添加到队列的节点。 BFS 的主要优点是能够找到起始节点到目标节点的最短路径因为它是逐层遍历的。 python语言
from collections import deque# 图的BFS遍历
def bfs(graph, start):# 使用队列来记录遍历路径queue deque([start])# 标记节点是否已访问的集合visited set([start])while queue: # 当栈不为空node queue.popleft() # 左端出栈print(node, end )for neighbor in graph[node]:if neighbor not in visited:queue.append(neighbor) # 右端进栈visited.add(neighbor)# 图的邻接表表示
graph {1: [2, 3],2: [2, 4, 5],3: [1, 6, 7],4: [2,8],5: [2,8],6: [3,7],7: [3,6],8: [4,5]
}# 从节点A开始进行BFS遍历
print(BFS遍历结果)
bfs(graph, 1) # 1 2 3 4 5 6 7 8
python: collections模块——双向队列deque 类似于list的容器可以快速的在队列头部和尾部添加、删除元素 3. DFS 与 BFS 的对比
DFS 和 BFS 是两种不同的图遍历算法在不同的应用场景下具有不同的优势
DFS 适用于找到起始节点到目标节点的路径但不一定是最短路径。它通过递归的方式深入探索图的分支因此对于深度较小的图或树 DFS 通常表现较好。BFS 适用于找到起始节点到目标节点的最短路径。它通过逐层遍历图的节点从而保证找到的路径是最短的。在需要寻找最短路径的情况下 BFS 是更好的选择
