7.4 图论

7.4 图论 — iEDA 开源文档与工程实践。

本目录内容

弗洛伊德算法作为求最短路径的经典算法，其算法实现相比迪杰斯特拉等算法是非常优雅的，可读性和理解都非常好。

回想一下我们在无向图的时候，当时我们就利用深度优先搜索解决了一幅无向图的连通问题。根据深搜能够到达所有连通的顶点，我们很容易解决这个问题。但是，问题变成有向图，就没有那么简单了！…

给定一个网络 G = ( V , E ) G=(V,E) G = ( V , E ) ，每条边除了有容量限制 c ( u , v ) c(u,v) c ( u , v ) ，还有…

若 G G G 为无向图，则 E E E 中的每个元素为一个无序二元组 ( u , v ) (u, v) ( u , v ) ，称作无向边 (Undirected edge) …

回溯算法（DFS 深度优先算法）实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索…

DFS算法即：Depth First Search，深度优先搜索。这个算法的关键是解决“当下如何做”，至于下一步如何做和“当下如何做”是一样的，该算法从一个状态DFS(n)转移到…

上下界网络流本质是给流量网络的每一条边设置了流量上界 c ( u , v ) c(u,v) c ( u , v ) 和流量下界 b ( u , v ) b(u,v) b ( u …

匈牙利算法又称为 KM 算法，可以在 O ( n 3 ) O(n^3) O ( n 3 ) 时间内求出二分图的最大权完美匹配。

这篇文章讲无权二分图（unweighted bipartite graph）的最大匹配（maximum matching）和完美匹配（perfect matching），以及用于…

双向同时搜索的基本思路是从状态图上的起点和终点同时开始进行广搜或深搜。如果发现搜索的两端相遇了，那么可以认为是获得了可行解。

问题来源：1859年，爱尔兰数学家、天文学家哈密顿提出的一个在正十二面体的二十个顶点上周游世界的游戏。基本概念：哈密顿路径：通过图中所有顶点一次且仅一次的路径称为哈密顿(Ha…

二分图：将所有点分成两个集合，使得所有边只出现在集合之间。一定不含有奇数环，可能含有长度为偶数的环，不一定是连通图。