图

4.1 无向图

边（edge）仅仅是两个顶点（vertex）之间的连接。为了 和其他图模型相区别，我们将它称为无向图。

4.1.3 深度优先搜索

深度优先是将一条路的所有可能性走过后，再走另外一条路

4.1.5 广度优先搜索

广度优先是将这一级别的岔路都走完后，再根据条件往下走

算法实现

两者大大致实现相同，例如有N个点，我们生成长度为N的二维数组，对应每个点，然后再将所有能直接到该节点顶点放到这个二维数组中，这样我们就有一条路径关系了。

参考图：

4.2 有向图

在有向图中，边是单向的：每条边所连接的两个顶点都是一个有序对，它们的邻接性是单向的. 拓扑排序:给定一幅有向图，将所有的顶点排序，使得所有的 有向边均从排在前面的元素指向排在后面的元素（或者说明无法做 到这一点）。

拓扑排序其实就是深度优先搜索的顶点逆后续 ![][http://qiniucdn.dgars.com/%E5%B1%8F%E5%B9%95%E5%BF%AB%E7%85%A7%202019-04-06%20%E4%B8%8B%E5%8D%887.05.52.png]

4.3 最小生成图

加权图：是一种为每条边关联一个权值或是成本的图模型。 最小生成树：给定一幅加权无向图，找到它的一 棵最小生成树。 贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

Prim算法基本思想： 一个图基本上都是由两个点两个点链接而成的，所以，我们可以用下面的数据格式来表示所有的点+边: 然后利用贪心算法，将所有定点之间权重最小的链接进行组合即可。，例如有(0-1[0.2] 0-2[0.1] 0-3[0.3])这三条边，其中0-2这条边的权重最小，则将0标记为已记录，0-2标记为权重最小的线，然后再找跟2连接的最小权重的点，然后以此类推，就得到了最小生成图

Kruskal算法：同样的贪心算法，将所有边从小到大排列，然后一个个加入树中，已经链接过的相关点抛弃即可。

4.4 最短路径

最短路径:找到从一个顶点到达另一个顶点的成本最小的路径。 算法类似与最小生成图，遍历所有的顶点以及连接的边，保存到数组中，有多少个顶点就创建对应lenght的数组，然后找个起点，从找个起点开始递归找所有链接的顶点,并保存从顶点到每个点的权重，如果有环导致重复链接到某个点，则与上次的权重作对比，取最小权重。如果该顶点与其他顶点还有链接，则更新对应的权重。 此处需要注意的是，如果图内有环，且是负环的时候，碰到环不能立刻进行消除，而应该进行权重判断，然后按上述原则修改对应链上的权重即可

--EOF--

若无特别说明，本站文章均为原创，转载请保留链接，谢谢