cms做淘宝客网站,凉山网站建设,个人可以做外贸网站吗,企业做网站大概多少钱在上一篇中我们进行了的并查集相关练习#xff0c;在这一篇中我们将学习图的知识点。 目录 概念深度优先DFS伪代码 广度优先BFS伪代码 最短路径算法#xff08;Dijkstra#xff09;伪代码 Floyd算法拓扑排序逆拓扑排序 概念 下面介绍几种在对图操作时常用的算法。 深度优先D… 在上一篇中我们进行了的并查集相关练习在这一篇中我们将学习图的知识点。 目录 概念深度优先DFS伪代码 广度优先BFS伪代码 最短路径算法Dijkstra伪代码 Floyd算法拓扑排序逆拓扑排序 概念 下面介绍几种在对图操作时常用的算法。 深度优先DFS
深度优先搜索DFS是一种用于遍历或搜索树、图等数据结构的基本算法。该算法从给定的起点开始沿着一条路径直到达到最深的节点然后再回溯到上一个节点继续探索下一条路径直到遍历完所有节点或者找到目标节点为止。
具体步骤如下 标记起始节点为已访问。 访问当前节点并获取其所有邻居节点。 遍历所有邻居节点如果该邻居节点未被访问过则递归地对该邻居节点进行深度优先搜索。 重复步骤2和步骤3直到所有能够到达的节点都被访问过。
DFS算法使用了递归或者栈的机制在每一轮中尽可能深入地探索并且只有在到达死胡同无法继续深入时才会回溯。DFS并不保证先访问距离起始节点近的节点而是以深度为导向。
DFS算法可以用于寻找路径、生成拓扑排序、解决回溯问题等但不保证找到最短路径。其时间复杂度为O(VE)其中V表示节点数E表示边数。在树或图的遍历中DFS通常占用的空间较少但在最坏情况下可能需要使用大量的栈空间。
简单来说DFS遵循悬崖勒马回头是岸的原则
拿下图举例从0一直完左走走到3发现没路可走后回头继续寻找。 所以图的深度优先遍历类似于二叉树的先序遍历
伪代码
# 定义图的数据结构
graph {A: [B, C],B: [D, E],C: [F],D: [],E: [F],F: []
}# 定义访问状态数组
visited {}# 初始化访问状态
for node in graph:visited[node] False# 定义DFS函数
def dfs(node):# 标记当前节点为已访问visited[node] Trueprint(node, end )# 遍历当前节点的邻接节点for neighbor in graph[node]:# 如果邻接节点未被访问则递归调用DFS函数if not visited[neighbor]:dfs(neighbor)# 从起始节点开始进行DFS
start_node A
dfs(start_node)
广度优先BFS
广度优先搜索BFS是一种用于遍历或搜索树、图等数据结构的基本算法。该算法从给定的起点开始按照距离递增的顺序依次访问其所有邻居节点并将这些邻居节点加入到一个队列中进行遍历直到访问到目标节点或者遍历完所有节点。
具体步骤如下 创建一个队列将起始节点加入队列中并标记为已访问。 循环执行以下步骤直到队列为空 弹出队列头部的节点。访问当前节点并获取其所有邻居节点。遍历所有邻居节点如果该邻居节点未被访问过则将其加入队列尾部并标记为已访问。 循环结束后所有能够从起始节点到达的节点都已经被访问过了。
BFS算法可以用于寻找最短路径或者解决迷宫等问题其时间复杂度为O(VE)其中V表示节点数E表示边数。相对于深度优先搜索BFS搜索更具有层次性能够保证先访问距离起始节点近的节点因此在寻找最短路径时更为有效。
如何对一个图进行广度优先遍历呢
方法是每一层从左到右进行遍历 比如下图的结果就是1、2、3、5、6、4、7 所以图的广度优先遍历类似于树的层次遍历
伪代码
# 定义图的数据结构
graph {A: [B, C],B: [D, E],C: [F],D: [],E: [F],F: []
}# 定义访问状态数组
visited {}# 初始化访问状态
for node in graph:visited[node] False# 定义BFS函数
def bfs(start_node):# 创建队列并将起始节点入队queue []queue.append(start_node)visited[start_node] Truewhile queue:# 取出队首节点current_node queue.pop(0)print(current_node, end )# 遍历当前节点的邻接节点for neighbor in graph[current_node]:# 如果邻接节点未被访问则将其入队并标记为已访问if not visited[neighbor]:queue.append(neighbor)visited[neighbor] True# 从起始节点开始进行BFS
start_node A
bfs(start_node)
最短路径算法Dijkstra
Dijkstra算法是一种用于解决带权重图中单源最短路径问题的经典算法。它能够找到从起始节点到其他所有节点的最短路径。
该算法的基本思想是通过逐步扩展已知最短路径来逐步确定起始节点到其他节点的最短路径。它维护一个距离字典记录从起始节点到每个节点的当前最短距离并使用一个优先队列按照距离的大小进行节点的选择和访问。
具体步骤如下 创建一个距离字典并将所有节点的距离初始化为无穷大将起始节点的距离设置为0。 将起始节点加入优先队列。 循环执行以下步骤直到优先队列为空 从优先队列中取出距离最小的节点作为当前节点。遍历当前节点的所有邻居节点 计算从起始节点到当前邻居节点的新距离即当前节点的距离加上当前节点到邻居节点的边的权重。如果新距离小于邻居节点的当前距离则更新邻居节点的距离为新距离并将邻居节点加入优先队列。 循环结束后距离字典中记录了从起始节点到所有其他节点的最短距离。
Dijkstra算法适用于有向图或无向图但要求图中的边权重必须为非负值。它是一种贪心算法在每一步都选择当前距离最小的节点进行扩展直到到达目标节点或遍历完所有节点。该算法的时间复杂度为O((|V||E|)log|V|)其中|V|是节点数|E|是边数。
伪代码
# 定义图的数据结构
graph {A: {B: 5, C: 3},B: {A: 5, C: 1, D: 6},C: {A: 3, B: 1, D: 2},D: {B: 6, C: 2}
}# 定义起始节点和终止节点
start_node A
end_node D# 定义距离字典和前驱节点字典
distances {}
predecessors {}# 初始化距离字典和前驱节点字典
for node in graph:distances[node] float(inf) # 将所有节点的距离初始化为无穷大predecessors[node] None# 设置起始节点的距离为0
distances[start_node] 0# 定义辅助函数获取未访问节点中距离最小的节点
def get_min_distance_node(unvisited):min_distance float(inf)min_node Nonefor node in unvisited:if distances[node] min_distance:min_distance distances[node]min_node nodereturn min_node# Dijkstra算法主体
unvisited set(graph.keys())
while unvisited:current_node get_min_distance_node(unvisited)unvisited.remove(current_node)if current_node end_node:breakfor neighbor, weight in graph[current_node].items():distance distances[current_node] weightif distance distances[neighbor]:distances[neighbor] distancepredecessors[neighbor] current_node# 重构最短路径
path []
current_node end_node
while current_node ! start_node:path.insert(0, current_node)current_node predecessors[current_node]
path.insert(0, start_node)# 输出结果
print(最短路径:, path)
print(最短距离:, distances[end_node])Floyd算法
Floyd算法也称为插点法是一种用于寻找图中所有节点对之间最短路径的算法同时也可以用于检测图中是否存在负权回路。
Floyd算法采用动态规划的思想通过不断更新两个节点之间经过其他节点的最短距离来求解任意两个节点之间的最短路径。具体而言算法维护一个二维数组 dp其中 dp[i][j] 表示从节点 i 到节点 j 的最短路径长度。初始化时若存在一条边从节点 i 到节点 j则 dp[i][j] 的初值为这条边的边权否则dp[i][j] 被赋值为一个足够大的数表示节点 i 无法到达节点 j。
接下来我们通过枚举一个中间节点 k来更新所有节点对之间的最短路径长度。具体而言如果 dp[i][j] dp[i][k] dp[k][j]则说明从节点 i 到节点 j 经过节点 k 的路径比当前的最短路径还要短此时可以更新 dp[i][j] 的值为 dp[i][k] dp[k][j]。
重复执行上述步骤直到枚举完所有的中间节点 k即可得到任意两个节点之间的最短路径长度。如果在更新过程中发现某些节点之间存在负权回路则说明无法求解最短路径。
#define INF 99999
#define V 4void floydWarshall(int graph[V][V]) {int dist[V][V], i, j, k;// 初始化最短路径矩阵为图中的边权值for (i 0; i V; i)for (j 0; j V; j)dist[i][j] graph[i][j];// 动态规划计算最短路径for (k 0; k V; k) {for (i 0; i V; i) {for (j 0; j V; j) {// 如果经过顶点k的路径比直接路径更短则更新最短路径if (dist[i][k] dist[k][j] dist[i][j])dist[i][j] dist[i][k] dist[k][j];}}}// 打印最终的最短路径矩阵for (i 0; i V; i) {for (j 0; j V; j) {// 如果路径为无穷大则打印INF否则打印最短路径值if (dist[i][j] INF)printf(%7s, INF);elseprintf(%7d, dist[i][j]);}printf(\n);}
}
拓扑排序
拓扑排序和逆拓扑排序都是用于对有向无环图进行排序的算法。
拓扑排序对于一个有向无环图拓扑排序可以得到一组节点的线性序列使得对于任何一个有向边 (u, v)在序列中节点 u 都排在节点 v 的前面。以下是拓扑排序的伪代码
# 定义图的数据结构
graph {A: [B, C],B: [D, E],C: [F],D: [],E: [F],F: []
}# 定义入度字典
in_degree {}# 初始化入度字典
for node in graph:in_degree[node] 0for node in graph:for neighbor in graph[node]:in_degree[neighbor] 1# 定义队列并将入度为0的节点加入队列
queue []
for node in in_degree:if in_degree[node] 0:queue.append(node)# 进行拓扑排序
result []
while queue:current_node queue.pop(0)result.append(current_node)for neighbor in graph[current_node]:in_degree[neighbor] - 1if in_degree[neighbor] 0:queue.append(neighbor)# 输出结果
print(result)逆拓扑排序
逆拓扑排序与拓扑排序相反逆拓扑排序可以得到一组节点的线性序列使得对于任何一个有向边 (u, v)在序列中节点 v 都排在节点 u 的前面。以下是逆拓扑排序的伪代码
# 定义图的数据结构
graph {A: [B, C],B: [D, E],C: [F],D: [],E: [F],F: []
}# 定义出度字典
out_degree {}# 初始化出度字典
for node in graph:out_degree[node] len(graph[node])# 定义队列并将出度为0的节点加入队列
queue []
for node in out_degree:if out_degree[node] 0:queue.append(node)# 进行逆拓扑排序
result []
while queue:current_node queue.pop(0)result.append(current_node)for neighbor in graph[current_node]:out_degree[neighbor] - 1if out_degree[neighbor] 0:queue.append(neighbor)# 输出结果
print(result)至此图的知识点就介绍完了在下一篇中我们将进行图的专项练习。
