图是重要的数据结构，在学习图的算法之前，需要了解图的基本概念，包括顶点、边、有向、无向、权值、路由回路、连通域、邻点、度、入边、出边、入度、出度等。 具体请参考这篇文章。 是图的理论基础。 此外，还需要理解如何存储图。 这样可以更好地理解图的算法。 图的存储结构请参考这篇文章。 数据结构——图(1)、图的存储结构Java实现。
另一方面，扫描图的遍历是指从图中的某个节点出发，根据特定的搜索方法沿着图中的各个边只访问一次所有节点。 注意到树是特殊的图，树的扫描实际上也可以看作是特殊的图的扫描。 图的遍历根据访问节点的顺序主要分为宽优先搜索(Breadth-First-Search )和深优先搜索(Depth-First-Search )以及A*搜索算法。
1 .广度优先搜索(BFS )首先访问起始节点v，然后从v出发，依次访问v的未访问的相邻节点w1、w2、wi，接着依次访问w1、w2、wi的所有未访问的相邻节点从这些访问的节点出发，访问所有未访问的相邻节点……依次类推，直到图中的所有节点都被访问。
宽度优先搜索是一个分层搜索过程，每进一步可能访问更多的节点，为了实现分层访问，算法需要使用辅助队列记录接入节点下一层的节点该算法可以实现最短路径的搜索。
2 .深度优先搜索(DFS )深度优先搜索类似于广度优先搜索，但喜欢听歌的cookie，该算法将深度优先，然后扩展到广度。
有关这两种算法的详细信息，介绍了可视图的基本算法(BFS和DFS )。
3.A*算法A*搜索算法，俗称A星算法，作为一种启发式搜索算法为在图形平面上，有多个节点的路径，求出最低通过成本的算法。 该算法像Dijkstra算法一样，能够找到最短路径； 也像BFS一样进行启发式搜索。
算法最核心的部分在于其评估函数的设计：f(n)=g(n)+h(n)。其中f(n)是每个可能试探点的估值，它有两部分组成：一部分，为g(n)，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。另一部分，即h(n)，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值h(n )设计的好坏直接关系到具有这种启发式函数的启发式算法能否称为a星算法
有关详细信息，请参阅A*算法。
二.最短路径算法4.Dijkstra算法Dijkstra算法也称为戴克斯特拉(Dijkstra )，用于解析单源最短路径问题。 即，在图中求出从某个顶点到其他任意一个顶点的最短路径。 该算法基于最短路径的最优子结构性质，只要从起点开始每一步走最短路径，更新各点到起点的最短距离，就可以得到各点到起点的最短距离。 实际上，迪斯科彻算法在A*算法的特殊情况下，即h(n )为0时，此时为f(n )=g (n ) )。 Dijkstra算法无法判断具有负权重的边的图的最短路径。
有关详细信息，请参阅单通道最短路径Dijkstra标注算法。
5.Bellman-Ford算法Bellman-Ford算法，又称贝尔曼- Ford算法，为求含负权图的单源最短路径的一种算法，效率低，代码难度低。 其原理是连续进行松弛，每次松弛时更新各边。 如果在n-1次松弛后也能更新的话，因为图中有负的循环，所以得不到结果。 否则就完成了。
文章详细介绍了该算法。 请参见贝拉曼福特对齐。
6 .浮动薄壳算法浮动薄壳算法解决任意两点间的最短路径的一种算法通常可以在任何图上使用，如有向图、负加权图等。 浮动薄壳算法用于找出各点之间的最短距离。 需要用邻接矩阵保存边缘，该算法通过考虑最优子路径得到最优路径。 该算法的基本思想：如果从一点到另一点的直接路径不是最短的，则短路最多的一定会通过第三点。 因此，将所有点作为1次中间点插入现在的2点间的最短路径，判断通过任意2点间的中间点的路程是否会变小。 核心算法只有5行：
for(k=1； k=n； k(//k是“媒体节点”(首先列出媒体节点) for ) I=1； i=n； I ) for ) j=1； j=n； j ) if ) e[I][j]e[I][k]e[j] ) e[I]=e[I][k]e[k][j]对该算法的理解是Floyd算法和alibertinein
第三，最小生成树7.Prim算法Prim算法(Prim算法)是在加权连通图里搜索最小生成树即对于由该算法搜索到的边缘子集组成的树，将连通图中的所有
算法步骤：
1 )输入)设顶点的集合为v，边的集合为e的加权连通图2 )
.初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；3).重复下列操作，直到Vnew = V：a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。详细内容参见：Prim。
8.Kruskal算法Kruskal算法，求加权连通图的最小生成树的算法。它是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。
对于图G(V,E)，以下是算法描述：
输入： 图G
输出： 图G的最小生成树
具体流程：
具体参见：最小生成树之Kruskal算法
四、图匹配 9.匈牙利算法匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，用于求解指派问题(assignment problem)，算法时间复杂度为O(n^3)。
匹配：一个匹配即一个包含若干条边的集合，且其中任意两条边没有公共端点。选择这样的边数最大的子集称为图的最大匹配问题，最大匹配的边数称为最大匹配数。
具体的讲解请参见：匈牙利算法（二分图）和二分图最大匹配问题匈牙利算法。
Ford-Fulkerson算法（FFA）是一种贪婪算法，用于计算流网络中的最大流量。流网络（Flow Networks）指的是一个有向图 G = (V, E)，其中每条边 (u, v) ∈ E 均有一非负容量 c(u, v) ≥ 0。如果 (u, v) ∉ E 则可以规定 c(u, v) = 0。流网络中有两个特殊的顶点：源点 s （source）和汇点 t（sink）。
最大流问题就是在满足容量限制条件下，使从起点s到终点t的流量达到最大。
Ford-Fulkerson方法首先对图中的所有边的流量初始化为零值，然后开始进入循环：如果在残存网络中可以找到一条从s到t的增广路径，那么要找到这条这条路径上值最小的边，然后根据该值来更新流网络。
详情参阅：最大流之Ford-Fulkerson方法详解及实现。