（0）目录
图算法小结(prime与dijkstra对比)
图算法小结(并查集)
哈夫曼树 之 建树和编解码
一：起因
（1）关于图的算法一般是比较复杂的，，自己在这方面也是比较弱的，首先是图的存储问题 和 遍历问题：
存储分为两种，邻接矩阵 和 临街表；遍历分为DFS 和 BFS两种，非常类似于二叉树的先跟遍历和层次遍历。
（2）图在实际应用中是非常广泛的，这与万物归一，万物相连的理论是一致的，两个物体之间有着千丝万缕的联系，我们成这种联系建立的网络为图（带权图）；联系的强弱为边的权重。
（3）图的一些复杂的算法，也是建立在两种遍历图的思想的基础上进行的，所以我们先从简单的谈起。
（4）图的相关知识：
图的定义： 很简单，G(V,E)， V、E分别表示点和边的集合。 图的表示： 主要有两种，邻接矩阵和邻接表，前者空间复杂度，O(V2），后者为O(V+E)。因此，除非非常稠密的图(边非常多），一般后者优越于前者。图的遍历： 宽度遍历BFS(start): (1) 队列Q=Empty，数组bool visited[V]={false…}. Q.push(start); (2) while (!Q.empty()){ u = Q.pop(); visited[u] = true; //遍历u结点 foreach (u的每一个邻接结点v) Q.push(v); } 深度遍历DFS(start): (1) 栈S=Empty, 数组bool visited[V]={false…}. S.push(start); (2) while (!S.empty()){ u = S.pop(); if (!visited[u]) visited[u] = true; //遍历u结点 foreach (u的每一个邻接结点v) S.push(v); } 两个算法很相似，主要区别在于一个使用队列，一个使用栈。队列是先入先出，所以访问u以后接下来就访问u中未访问过的邻接结点；而栈的后进先出，当访问u后，压入了u的邻接结点，在后面的循环中，首先访问u的第一个临接点v，接下来又将v的邻接点w压入S，这样接下来要访问的自然是w了。最小生成树： (1)Prime算法: (1) 集合MST=T=Empty，选取G中一结点u，T.add(u) (2) 循环|V|-1次： 选取一条这样的边e=min{(x,y) | x in T, y in V/T} T.add(y); MST.add(e); (3) MST即为所求 (2) Kruskal算法 (1) 将G中所有的边排序并放入集合H中，初始化集合MST=Empty,初始化不相交集合T={{v1}, {v2}…}}，也即T中每个点为一个集合。 (2) 依次取H中的最短边e(u,v)，如果Find-Set(u)!=Find-Set(v)（也即u、v是否已经在一棵树中），那么Union(u,v) （即u,v合并为一个集合)，MST.add(e); (3) MST即为所求
这两个算法都是贪心算法，区别在于每次选取边的策略。证明该算法的关键在于一点：如果MST是图G的最小生成树，那么在子图G’中包含的子生成树MST’ 也必然是G’的最小生成树。这个很容易反正，假设不成立，那么G’有一棵权重和更小的生成树，用它替换掉MST’，那么对于G我们就找到了比MST更小的生成树，显然这与我们的假设(MST是最小生成树)矛盾了。 理解了这个关键点，算法的正确性就好理解多了。对于Prime，T于V/T两个点集都会各自有一棵生成树，最后要连起来构成一棵大的生成树，那么显然要选两者之间的最短的那条边了。对于Kruskal算法，如果当前选取的边没有引起环路，那么正确性是显然的（对给定点集依次选最小的边构成一棵树当然是最小生成树了），如果导致了环路，那么说明两个点都在该点集里，由于已经构成了树（否则也不可能导致环路）并且一直都是挑尽可能小的，所以肯定是最小生成树。最短路径: 这里的算法基本是基于动态规划和贪心算法的，经典算法有很多个，主要区别在于：有的是通用的，有的是针对某一类图的，例如，无负环的图，或者无负权边的图等。 单源最短路径（1） 通用（Bellman-Ford算法）： （2） 无负权边的图(Dijkstra算法)： （3） 无环有向图(DAG) ： 所有结点间最短路径： （1） Floyd-Warshall算法： （2） Johnson算法：关键路径 和拓扑排序:
二：代码示例
（1）最简单的图的遍历问题
世上没有绝望的处境，只有对处境绝望的人。
