做网站工程案例图片,wordpress回复后可见,wordpress 改邮箱,佛山制作网页公司图的实现方式
邻接矩阵
定义
邻接矩阵是一个二维数组#xff0c;其中的元素表示图中节点之间的关系。通常#xff0c;如果节点 i 与节点 j 之间有边#xff08;无向图#xff09;或者从节点 i 到节点 j 有边#xff08;有向图#xff09;#xff0c;则矩阵中的元素值…图的实现方式
邻接矩阵
定义
邻接矩阵是一个二维数组其中的元素表示图中节点之间的关系。通常如果节点 i 与节点 j 之间有边无向图或者从节点 i 到节点 j 有边有向图则矩阵中的元素值为 1 或者表示边的权重值。如果没有边相连则元素值为 0 或者一个特定的标记通常表示无穷大。
优点
适用于稠密图即节点之间有很多边的情况因为它不会浪费太多空间。支持常数时间内的边的查找操作。
缺点
对于稀疏图它会浪费大量的空间因为大部分元素都是 0。插入和删除边的操作相对较慢需要修改矩阵的值。
邻接表
定义
邻接表是一种数据结构用于表示图的每个节点及其相邻节点的列表。通常使用数组或哈希表和链表或其他数据结构的组合来实现。每个节点对应一个数组元素该元素存储指向该节点相邻节点的链表或数组。
优点
适用于稀疏图因为它不会浪费大量空间。插入和删除边的操作相对较快因为只需要修改链表或数组。
缺点
查找两个节点之间是否存在边需要遍历相邻节点列表时间复杂度取决于节点的度数。
图的遍历
深度优先搜索(DFS)
定义
DFS从一个起始节点开始沿着一条边尽可能深地探索图直到无法继续为止然后回溯到上一个节点继续深入其他分支。DFS通常使用递归或栈数据结构来实现。
步骤
从起始节点开始将其标记为已访问。
对于当前节点遍历其未被访问的邻居节点。
选择一个邻居节点将其标记为已访问并递归或使用栈继续探索该邻居节点。
重复步骤3直到没有未被访问的邻居节点然后回溯到上一个节点继续探索其他邻居。
特点
深度优先搜索会一直沿着一条分支深入直到到达最深处然后返回并探索其他分支。使用递归时可能导致堆栈溢出因此对于大型图可能需要使用非递归实现使用显式的栈数据结构。
广度优先搜索(BFS)
定义
BFS从一个起始节点开始首先访问其所有未被访问的邻居节点然后按照距离从起始节点逐层扩展直到遍历完整个图。BFS通常使用队列数据结构来实现。
步骤
从起始节点开始将其标记为已访问并将其加入队列。
从队列中取出一个节点访问其所有未被访问的邻居节点并将它们标记为已访问并加入队列。
重复步骤2直到队列为空。
特点
广度优先搜索首先访问离起始节点最近的节点然后逐层扩展确保了最短路径的搜索。使用队列来实现确保了节点按照距离逐层访问。
最小生成树
概念
最小生成树Minimum Spanning Tree简称 MST是在一个连通图中找到一棵包含图中所有节点的树并且该树的所有边的权重之和最小的树。通俗地说最小生成树是一棵树它连接了图中的所有节点并且总权重最小。Prim算法和Kruskal算法是两种常见的用于求解最小生成树问题的算法。
Prim算法
思想
Prim算法的关键思想是始终选择当前最小权重的边以确保最小生成树的总权重最小。这种贪心策略保证了Prim算法的正确性。
步骤
选择一个起始节点首先从图中选择一个任意的起始节点作为最小生成树的根节点。
初始化创建一个空的最小生成树开始时只包含根节点。同时创建一个优先队列通常使用最小堆来存储候选边该队列初始化为空。
找到候选边将起始节点的所有相邻边连接到未包含在最小生成树中的节点的边添加到优先队列中。
选择最小权重的边从优先队列中选择权重最小的边即最小的边权重并将其添加到最小生成树中。
标记节点将该边连接的节点标记为已访问或已包含在最小生成树中。
重复步骤3至5不断重复步骤3和步骤4选择并添加下一条权重最小的边直到最小生成树包含了图中的所有节点。
结束当最小生成树包含了所有节点时算法终止。
特点
Prim算法的时间复杂度取决于优先队列的实现方式通常为O(E VlogV)其中E是边的数量V是节点的数量。Prim算法在稠密图边数量较多上效果较好因为优先队列中的边数量较多时操作的时间复杂度较低。它适用于带权重的图用于解决网络设计、电路设计、城市规划等问题。
Kruskal算法
思想
Kruskal算法的关键思想是始终选择权重最小的边并确保最小生成树不形成环。这种贪心策略保证了Kruskal算法的正确性。
步骤
初始化将图中的所有边按照权重从小到大排序并将它们存储在一个边集合中。同时创建一个空的最小生成树开始时不包含任何边。
遍历边集合按照排序后的顺序遍历边集合。
检查边的端点对于当前遍历到的边检查它的两个端点是否已经在最小生成树中。如果边的两个端点都不在最小生成树中说明将这条边添加到最小生成树不会形成环因此可以安全地将这条边加入最小生成树中。
添加边将通过步骤3确定可以添加的边加入到最小生成树中。
重复步骤2至4不断重复遍历边集合并添加边直到最小生成树包含了图中的所有节点或者边集合已经遍历完。
结束当最小生成树包含了所有节点时算法终止。
特点
Kruskal算法的时间复杂度主要取决于排序边的操作通常为O(ElogE)其中E是边的数量。由于Kruskal算法不需要对节点的度数进行操作因此在稠密图边数量较多上表现较好。它适用于带权重的图用于解决网络设计、电路设计、城市规划等问题。需要注意的是Kruskal算法不一定会生成唯一的最小生成树但它保证了生成的最小生成树的总权重是最小的。如果存在多个最小生成树它们的总权重将相等。
最短路径
概念
最短路径问题是图论中的一个经典问题其目标是找到从一个指定的起始节点到另一个指定的目标节点之间的最短路径即具有最小权重距离、代价等的路径。最短路径问题分为单源最短路径和所有节点对最短路径。
单源最短路径问题Single-Source Shortest Path在单源最短路径问题中给定一个起始节点要找到该节点到图中所有其他节点的最短路径。最著名的算法是Dijkstra算法。
所有节点对最短路径问题All-Pairs Shortest Path在所有节点对最短路径问题中需要找到图中任意两个节点之间的最短路径。最著名的算法是Floyd算法。
Dijkstra算法
思想
Dijkstra算法的核心思想是使用贪心策略即始终选择当前距离最短的节点进行探索并逐步更新距离数组。由于它不处理负权重边因此适用于带有非负权重边的图。
步骤
初始化首先创建一个集合通常是一个优先队列或最小堆用于存储尚未确定最短路径的节点。同时初始化一个距离数组用于记录从起始节点到每个节点的当前最短距离。将起始节点的距离设置为0表示到达起始节点的距离为0而其他节点的距离设置为无穷大或一个足够大的值表示尚未确定的距离。
选择最近的节点从集合中选择距离起始节点最近的节点并将其标记为当前的最短路径节点。通常这个选择过程使用优先队列或最小堆来实现以确保每次选择的是距离最近的节点。
更新距离对于当前选定的最短路径节点遍历其所有未被确定最短路径的邻居节点。计算从起始节点经过当前节点到邻居节点的距离并将这个距离与之前记录的距离进行比较。如果新计算得到的距离更短就更新邻居节点的距离。
重复步骤2和步骤3不断重复选择最近的节点和更新距离的步骤直到所有节点都被标记为确定最短路径或集合为空。
结束当所有节点都被标记为确定最短路径时算法终止距离数组中存储的就是从起始节点到所有其他节点的最短路径。
特点
Dijkstra算法的时间复杂度通常为O(V^2)其中V是节点的数量。但如果使用优先队列或最小堆来实现时间复杂度可以优化为O(E VlogV)其中E是边的数量。因此对于大型图来说使用优先队列实现Dijkstra算法更有效率。算法的正确性得益于贪心策略它保证了每一步都选择了当前最优的路径。
Floyd算法
思想
使用动态规划的方法通过考虑所有可能的中间节点逐步更新节点对之间的最短路径距离。这个算法可以处理带有正、负权重边的图以及检测负权重环路。
步骤
初始化距离矩阵创建一个距离矩阵通常用二维数组表示其中元素d[i][j]表示从节点i到节点j的最短距离。初始时将矩阵中的对角线元素i等于j的元素设置为0表示从节点i到节点i的距离为0。对于其他元素如果存在直接的边连接节点i和节点j则将d[i][j]设置为边的权重否则将其设置为无穷大。
更新距离矩阵对于每对节点i和j以及中间节点k检查是否存在一条路径从节点i到节点j经过节点k比当前的最短距离更短。具体步骤如下
对于每一对节点i和ji ≠ j遍历所有中间节点k1到n其中n是节点的总数。
计算从节点i经过节点k到节点j的距离d[i][k] d[k][j]。
如果上述距离小于当前的最短距离d[i][j]则更新d[i][j]为这个新的更短距离。
重复步骤2不断重复更新距离矩阵的步骤直到不再存在更短的路径为止。这意味着每个节点对之间的最短路径已经被找到。
结束当算法完成后距离矩阵d包含了所有节点对之间的最短路径距离。
特点
Floyd算法的时间复杂度为O(V^3)其中V是节点的数量。虽然它在时间复杂度上比Dijkstra算法慢但Floyd-Warshall算法具有一个重要的优点即可以一次性计算所有节点对之间的最短路径因此非常适合于计算密集型问题和需要计算所有节点对的情况。
