最短路径快速算法
最短路径快速算法（），国际上普遍认为是带有佇列最佳化的Bellman-Ford 算法，一般仅在中国大陆被称为SPFA，是一个用于求解有向带权图单源最短路径的算法。这一算法在随机的稀疏图上表现出色，并且适用于带有负边权的图。 然而SPFA在最坏情况的时间复杂度与 Bellman-Ford 演算法相同，因此在非负边权的图中，使用堆优化的Dijkstra 算法效率可能优于SPFA。 SPFA首先在1959年由作为广度优先搜索的扩展发表，相同算…
标签：#图算法
共 35 篇文章
克里斯托菲德斯算法
克里斯托菲德斯算法（）是旅行商问题在度量空间（即距离对称且满足三角不等式）上的一个近似算法。 该算法可以保证相对最优哈密尔顿回路长度有3/2的近似比。于1976年首次发表了这个算法，故以他的名字命名之。 ，这一算法仍然是一般性旅行商问题的算法中近似比最好的结果。 算法 令 G = (V,w) 是旅行商问题的一个实例。 即， G 是一顶点集V 上的一个完全图，函数 w 给 G 的每条边指定了一个非负实边权。 依三角不等式，对每三个顶点 u…
力导向图
力导向图形绘制算法是以美观的方式绘制图形的一类算法。它们的目的是将一个图的节点定位在二维或二维三维空间中，这样所有的边或多或少都是等长的，交叉的边越少越好。方法是根据边和节点的相对位置在边和节点的集合中分配力，然后利用这些力模拟边和节点的运动。 虽然图形绘制可能是一个难题，但作为物理模拟的力导向算法通常不需要关于平面性等图论的特殊知识。 力 力导向图绘制算法把把力赋给图形绘制的节点集合与边的集合。通常，基于胡克定律的类似弹簧的吸引力用于…
哈韦尔-哈基米算法
哈韦尔-哈基米算法是一种图论算法，由与先后发表，解决了。这个问题是指给定一串有限多个非负整数组成的序列，是否存在一个简单图使得其恰为这个序列。我们称满足条件的序列为可简单图化的。如果一个序列可简单图化，这个算法能够构造一个特解；否则算法指出序列不可简单图化。该算法是一个递归算法。 算法 哈韦尔-哈基米算法基于以下定理。 令S=(d_1,\dots,d_n)为有限多个非负整数组成的非递增序列。S可简单图化当且仅当有穷序列S'=(d_2-1…
带宽 (图论)
图论中，图带宽问题是用不同整数f(v_i)给图G的n个顶点v_i贴上标签，使得量\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}最小化的问题（其中E是G的边集）。 这问题可以形象理解为，将图的顶点置于沿x轴的不同整数点上，使最长边最短的问题。这种放置称作线性图排列（linear graph arrangement）、线性图布局（linear graph layout）或线性图放置（linear…
拓撲排序
在计算机科学领域，有向图的拓扑排序（）或拓撲定序（）是对其顶点的一种线性排序，使得对于从顶点 u 到顶点 v 的每个有向边 uv ， u 在排序中都在 v 之前。 例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。 当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。 任何有向无环图至少有一个拓扑排序。已知有算法可以在-{}-线性时间内，…
最小生成树
和它的最小生成树。在该图中，边的长度正比于权值A。]] 最小生成树（，簡稱MST）是最小權重生成樹（）的簡稱，是一个连通加权无向图中一棵权值最小的生成树。 在一給定的無向圖 G = (V, E) 中，(u, v) 代表連接頂點 u 與頂點 v 的邊（即 (u, v)\in E），而 w(u, v) 代表此邊的權重，若存在 T 為 E 的子集（即 T\subseteq E）且 (V, T) 為樹，使得： :w(T) = \sum_{(u,…
普林姆算法
普里姆算法（）是图论中的一种贪心算法，可在一个加权连通图中找到其最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家发现；并在1957年由美国计算机科学家羅伯特·C·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。 描述 从单一顶点开始，普里姆算法按照…
Floyd-Warshall算法
算法（），中文亦称弗洛伊德算法或佛洛依德算法，是解决任意两点间的最短路径的一种算法，可以正確處理有向圖或负权（但不可存在负权回路）的最短路径問題，同时也被用于计算有向图的传递闭包。 算法的时间复杂度為O(|V|^3)，空间复杂度为O(|V|^2)，其中V是点集。 原理 算法的原理是动态规划。 设D_{i,j,k}为从i到j的只以(1..k)集合中的节点为中间節点的最短路径的长度。 #若最短路径经过点k，则D_{i,j,k}=D_{i,k…
A*搜尋演算法
*A搜索算法*（）是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於遊戲中的NPC的移動計算，或网络游戏的BOT的移動計算上。 该算法综合了和戴克斯特拉算法的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（需要评估函数满足单调性）。 在此算法中，如果以g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离（根据所采用的评估函数的不同而变化），那么A算法的估算函数为： …
传递闭包
数学中，集合X上的二元关系 R 的传递闭包是包含R的X上的最小的遞移關係。 例如，如果 X 是由人组成的集合（不论人活着与否）而R是关系“为父子”，则 R 的传递闭包是关系“x 是 y 的祖先”。再比如，如果 X 是空港的集合而关系 xRy 为“从空港 x 到空港 y 有直航”，则 R 的传递闭包是“可能经一次或多次航行从 x 飞到 y”。 存在性和描述 对于任何关系 R，R 的传递闭包总是存在的。传递关系的任何家族的交集也是传递的。进…
霸道选举算法
霸道选举算法（Bully algorithm）是一种分布式选举算法，每次都会选出存活的进程中ID最大的候选者。 霸道选举算法的假设 算法假设： 系统是同步的 进程在任何时候都可能失败，包括算法在执行的过程中 进程失败后停止工作，重启后重新工作 有失败监控者，它可以发现失败的进程 进程之间的消息传递是可靠的 每一个进程知道自己和其他每一个进程的ID以及地址 霸道算法的选举流程 选举过程中会发送以下三种消息类型： Election消息：表示…
格文-纽曼算法
格文-纽曼算法（得名於和）是复杂系统启发式社区发现算法。 边介数和社会结构 格文-纽曼算法通过不断地删除网络中的边来检测网络中的社区。在最终剩余的网络中的连通分量也就是社区。格文-纽曼算法并不是去测量哪些边具有最高的中心度，而是去关注哪些最有可能连接着社区。 顶点介数是一种反应网络中顶点的中心度的指标。对于一个顶点i，顶点介数是指网络中经过该顶点的所有最短路径的数量。 格文-纽曼算法将介数扩展到了边。类似地，一条边的边介数是指网络中经过…
米斯拉-格里斯边着色算法
米斯拉-格里斯边着色算法是图论算法的一种，能够在多项式时间内找到任意图的一种边着色方案。这种着色算法最多使用\Delta+1种颜色，\Delta是该图节点的最大度数。这对于一些图而言是最优的，根据Vizing定理，最坏情况下，这种算法给出的结果比最优值多使用一种颜色。 该算法由Jayadev Misra和在1992年首次提出，是对Béla Bollobás提出的一种算法的简化。 对于边着色问题，该算法是已知最快的“几乎最优”算法。时间复…
双向搜索
双向搜索算法是一种图的遍历算法，用于在中搜索从一个顶点到另一个顶点的最短路径。算法同时运行两个搜索：一个从初始状态正向搜索，另一个从目标状态反向搜索，当两者在中间汇合时搜索停止。在很多情况下该算法更快，假设搜索一棵分支因子b的树，初始节点到目标节点的距离为d，该算法的正向和反向搜索复杂度都是O(bd/2) (大O符号)，两者相加后远远小于普通的单项搜索算法（复杂度为O(bd)）。 在A搜尋演算法中，双向搜索的启发式函数可以定义为：正向搜…