目录
一、哈夫曼树
1.1 带权扩充二叉树的外部路径及其长度
1.2 哈夫曼树
1.3 构造哈夫曼树的算法
1.4 哈夫曼算法的Python实现
1.5 算法复杂度分析
二、图的遍历
2.1 深度优先遍历算法
2.2 宽度优先遍历算法
2.3 深度优先遍历的非递归算法
三、生成树
四、MST——Kruskal算法
4.1 基本方法
4.2 算法实现中的问题
五、MST——Prim算法
5.1 MST的一个重要性质
5.2 Prim算法的基本想法
5.3 Prim算法的实现
六、SP——Dijkstra算法
6.1 基本想法
6.2 算法梗概
6.3 算法实现
七、SP——Floyd算法
7.1 基本想法
7.2 算法实现
一、哈夫曼树
1.1 带权扩充二叉树的外部路径及其长度
1.2 哈夫曼树
设有实数集w，t是一棵扩充二叉树，其m个外部结点分别以为权，而且t的带权外部路径长度WPL在所有这样的扩充二叉树中达到最小，则称t为数据集w的最优二叉树或者哈夫曼树。
1.3 构造哈夫曼树的算法
·输入一实数集w
·在构造中维护一棵包含k棵二叉树的集合F，开始时k=m，，其中每棵T是一棵只包含权w的根结点的单点二叉树
·重复执行以下两个步骤：
（1）构造一棵新二叉树，其左右子树是从F中选取的两棵权最小的二叉树，其根节点的权值设置为这两棵子树的根结点的权值之和
（2）将所选的两棵二叉树从F中删除，把新构造的二叉树加入F
注意：给定集合w上的哈夫曼树不唯一。交换其中任意一个或多个结点的左右子树，得到的仍是w上的哈夫曼树。
1.4 哈夫曼算法的Python实现
·用二叉树的结点类构造哈夫曼树，在根结点记录树的权值
·为了不断选出权值最小的两棵二叉树，宜使用优先队列存放这组二叉树，从小到大排列
·这里还需解决两个问题：一、为二叉树结点类定义一个排序的方法；二，为优先队列定义检查元素个数的方法，以便只在一棵树时结束。这些均可以通过扩充已有类实现：
class HTNode(BinTNode):
def __lt__(self, other node):
return self.data < other node.data
class HuffmanPriQ(PrioQueue):
def number(self):
return Len(self._elems)
完整的算法如下：
def HaffmanTree(weights):
trees = HuffmanPrioQ()
for w in weights:
trees.enqueue(HTNode(w))
while trees.number() > 1:
t1 = trees.dequeue()
t2 = trees.dequeue()
x = t1.data + t2.data
trees.enqueue(HTNode(x, t1, t2))
return trees.dequeue()
1.5 算法复杂度分析
第一个循环，时间复杂度是，第二个循环，时间复杂度是同样。可见，这个算法的时间复杂度是。
二、图的遍历
2.1 深度优先遍历算法
·首先访问顶点v，并将其标记为已访问
·检查v的邻接顶点，从中选一个尚未访问的顶点，从它出发继续进行深度优先搜索（这是递归）。不存在这种邻接顶点是回溯
·反复上述操作直到v出发可达的顶点都已访问
·如果图中还存在未访问的顶点，则选出一个未访问的顶点，由它出发重复前述过程，直到图中所有顶点都已访问为止
注意，如果对任意顶点的邻接点采取不同的排列顺序，会得到不同的搜索序列。当然，若统一规定顺序，则序列唯一。
2.2 宽度优先遍历算法
·首先访问顶点v，并将其标记为已访问
·依此访问v的所有相邻顶点，再依次访问与邻接的所有尚未访问过的顶点
·如果图中还存在未访问的顶点，则选出一个未访问的顶点，由它出发重复前述过程，直到图中所有顶点都已访问为止
2.3 深度优先遍历的非递归算法
为防止多次遍历同一顶点，需采用一个内部的表对象记录访问历史，对应每个顶点有一个表元素。当一个顶点被访问时，将该顶点下表对应的表元素设置为1。初始时这个表的所有元素取0值。
算法中入栈的元素形式为(i,edges)，其中edges是某个顶点的边表，i是边表的下标，表示当这个序对弹出时应该老吕的下一条边的下标。即edges[i]
完整的算法如下：
def DFS_graph(graph, v0):
vnum = graph.vertex_num()
visited = [0] * vnum
visited[v0] = 1
DFS_seq = [v0]
st = SStack()
st.push((0, graph.out_edges(v0)))
while not st.is_empty():
i, edges = st.pop()
if i < len(edges):
v, e = edges[i]
st.push((i+1, edges)) # 访问完一个顶点后访问下一个顶点
if visited[v] == 0:
DFS_seq.append(v)
visited[v] = 1
st.push((0, graph.out_edges(v))) # 此顶点未访问，由此开始深搜
return DFS_seq
三、生成树
从连通无向图或强连通有向图中任意顶点出发遍历，或从有根有向图的根顶点出发遍历，都可以访问到所有顶点。在遍历中经过的边加上原图的所有顶点，就构成该图的一棵生成树。
生成树上的边形成了从初始顶点到其他顶点的一簇路径。在这簇路径里，一个顶点可能有多个“下一顶点”，但至多有一个“前一顶点”。记录路径的一种方式时记录所有的“前一顶点”关系。
用一个包含vnum个元素的表span_forest记录得到的路径信息，格式为(vj, e)，vj是v0到vi的路径上vi的前一顶点，e是vj到vi的邻接边的信息。
算法主循环是考虑到图可能不连通，为了找到下一个未遍历的顶点。if的条件成立就是找到了尚未访问的顶点，给它的标记是到自己的边长为0，然后以它为根构造一棵生成树。
完整的算法如下：
def DFS_span_tree(graph):
vnum = graph.vertex_num()
span_forest = [None]*(vnum)
def dfs(graph, v):
nonlocal span_forest
for u, w in graph.out_edges(v):
if span_forest[u] is None:
span_forest[u] = (v, w)
dfs(graph, u)
for v in range(vnum):
if span_forest[v] is None:
span_forest[v] = (v, 0)
dfs(graph, v)
return span_forest
四、MST——Kruskal算法
4.1 基本方法
·初始时取包含G中所有n个顶点但没有任何边的孤立点子图T，T里的每个顶点自成一个连通分量。下面将通过不断扩充T的方式构造最小生成树
·将边集E中的边按权值递增的顺序排序，在构造中的每一步顺序地检查这个边序列，找到下一条（最短的）两端点位于T的两个不同的连通分量的边e，把e加入T
·每次操作使T减少一个连通分量，重复操作即可得到结果
4.2 算法实现中的问题
考虑算法的抽象描述：
T = (V, {})
while T中所含的边数小于n-1:
从E中选取当前最小边(u, v)，将它从E中删除
if (u, v)两端点属于T的不同连通分量：
将边(u, v)加入T
需要考虑两个问题：
一、当前最短边的选取。可以每次扫描剩下的边，选出最短边；可以先将所有的边排序后顺去选取；还可以使用优先队列。
二、如何判断两个顶点在当时的T里属于两个不同的连通分量。解决方法是为每个连通分量确定一个代表元。在算法执行过程中，需要记录和维护每个顶点的代表元。最麻烦的问题是合并连通分量时的代表元维护。完成这件事的简单方法是从原来的两个代表元中任选一个，而后更新另一连通分量中顶点的代表元。
在下面的算法中，reps记录个顶点的代表元，mst记录最小生成树，edges记录所有的边，格式为(w, vi, vj)。w是权值，vi和vj是两个端点。利用sort操作将边按权值排序，随后的操作就是逐个选择最短的有效边。
完整的算法如下：
def Kruskal(graph):
vnum = graph.vertex_num()
reps = [i for i in range(vnum)]
mst, edges = [], []
for vi in range(vnum):
for v, w in graph.out_edges(vi):
edges.append( (w, vi, v) )
edges.sort()
for w, vi, vj in edges:
if reps[vi] != reps[vj]:
mst.append( (vi, vj), w)
if len(mst) == vnum-1:
break
rep = reps[vi]
orep = reps[vj]
for i in range(vnum):
if reps[i] == orep:
reps[i] = rep
return mst
五、MST——Prim算法
5.1 MST的一个重要性质
设G=(V,E)是一个网络，U是V的任一真子集，设e=(u,v)E且uU，vV-U，而且e在G中所有一个端点在U而另一端点在V-U的边中权值最小，那么g必有一棵包括边e的最小生成树。
5.2 Prim算法的基本想法
从一个顶点出发，利用MST性质选择最短连接边，扩充已连接的顶点集并加入所选的边。
·从图的顶点集中任取一顶点放入集合U中，令边集合E为空集
·检查所有一个端点在集合U里而另一个端点在集合V-U的边，找出其中权值最小的边(u,v)，将顶点v加入顶点集合U，并将e加入边集合E
·重复上面步骤，直到U=V
5.3 Prim算法的实现
mst 记录构造的最小生成树的边，格式为((i,j), w)
cands 优先队列，记录候选的最短边，格式为(w, i, j)
算法过程
·初始时把（0，0，0）放入优先队列，表示从顶点0到其自身的长度为0的边
·循环在第一次迭代中先把顶点0计入U，即设置元素mst[0]=((0,0),0)，然后把顶点0到其余顶点的边按权值存入优先队列
·反复选择优先队列里的最短边(u,v)，如果确定了它连接U与V-U，就把这条边及其权值计入mst，并把v的出边存入优先队列；否则就直接丢弃掉
完整的算法如下：
def Prim(graph):
vnum = graph.vertex_num()
mst = [None] * vnum
hands = PrioQueue([(0,0,0)])
count = 0
while count < vnum and not cands.is_empty():
w, u, v = cands.dequeue()
if mst[v]:
continue
mst[v] = ((u, v), w)
count += 1
for vi, w in graph.out_edges():
if not mst[vi]
cands.enqueue((w, v, vi))
return mst
六、SP——Dijkstra算法
6.1 基本想法
在Dijkstra算法的执行过程中，把图中的顶点分为两个集合：当时已知最短路径集合U，以及尚不知道最短路径的顶点集合V-U。在算法的执行过程中逐步扩充已知最短路径的顶点集合，每一步从顶点集合V-U中找出一个顶点（它是当时已经能确定最短路径的顶点）加入U。反复执行这样的步骤，直至找到从到其他所有顶点的最短路径。
·如果已知从v0到u的距离（u U），而且存在从u到v的边，那么从v0到v的当前已知距离，就是在所有经由满足上述条件的u的间接路径中最短的那一条路径的长度。
·如果v'在当前所有不属于 U 的顶点中cdis最小，那么。也就是说，从v0到v'的当前已知距离就是其实际距离，因此到它的最短路径已知，现在就可把v'加入顶点集合U
·最短路径中前段也是最短路径：如果v'是从初始点v0到某顶点v的最短路径p上v的前一个顶点，那么从路径p去掉最后顶点v得到的路径p'也是v0到v'的最短路径。
6.2 算法梗概
初始：
·在集合u中放入顶点v0， v0到v0的距离为0
·对v-u里的每个顶点v，如果（v0,v） e，（即存在直接的边），则到v的已知最短路径长度设为 w(v0, v)，否则令v的已知路径的长度为∞。这里的 w(v0, v)是从v0到v的边的权值
反复做：
·从v-u中选出当时已知最短路径长度最小的顶点加入u（注意是路径长度最小，不是边的权值最小），因为这时到的已知最短路径长度就是v0到vmin的距离
·由于vmin的加入，v-u中某些顶点的已知最短路径长度可能改变。如果从v0经过vmin到v'的路径比原来已知的最短路径更短，就说明发现了到v'的新的已知最短路径，该路径经过vmin到v'。在这种情况下，更新到v'的已知最短路径及距离的记录。
6.3 算法实现
需要考虑以下几个问题：
·如何记录最短路径：由相关性质知，只需记录v的前一顶点即可。由此可见，记录所有最短路径只需要用一个vnum-1个元素的边集合。
·算法采用paths表记录路径，格式为（v', p），表示从v0到顶点v的最短路径上的前一顶点是v'，该最短路径的长度是p。paths[v]=none表示v还不在U里。
·候选边记录在优先队列中，格式为(p, v, v')，表示从v0经v到v'的已知最短路径为p。根据p的值排序。
·每次选出具有最小p值的边。如果其终点v'在V-U，就将其加入paths，并将由v'可达的其他顶点及其路径长度记录优先队列。如果优先队列中已有到某顶点的路径，但后来发现的新路径长度更短，需要保证最短的路径被先行取出。
完整的算法如下：
def Dijkstra(graph, v0):
vnum = graph.vertex_num()
assert 0 <= v0 < vnum
paths = [None] * vnum
count = 0
cands = PrioQueue([(0, v0, v0)])
while count < vnum and not cands.is_empty():
plen, u, vmin = cands.dequeue()
if paths[vmin]:
continue
paths[vmin] = (u, plen)
for v, w in graph.out_edges(vmin):
if not paths[v]: # 注意此处
hands.enqueue((plen + w, vmin, v))
count += 1
return paths
思考以下几个问题：
1、对比Dijkstra算法与Prim算法，仔细观察异同；
2、在Dijkstra算法中，由于 到各点的最短路径是动态规划中的，需要时刻更新最短路径的数据。算法中是如何实现这一点的？
3、如果边的权值为负数，Dijkstra算法还有效吗？为什么？
4、Dijkstra算法中，得到的是 到各顶点的最短路径。如何同步得到所有顶点到其它各顶点的最短路径？
七、SP——Floyd算法
7.1 基本想法
开始：对每队v和v'，途中不经过任何顶点的路径长度已知。如果存在v到v'的边，这个长度就是该边的权；若不存在则为.
k = 0 :对每对v和v'，除前一步已知的路径外，从v到v'的途径顶点的下标不大于k（此处为不大于0，因此只有一种选择）的路径可分为两段（若没有路径，则认为是）,
这一路径的长度就是两段路径的长度之和。比较这一新路径和前一步已知路径（是已知路径中最短的），可以确定从v到v'的途径顶点的下标不大于0的最短路径。
k = 1 :对每对v和v'，除前一步已知的路径外（途径下标小于等于0），从v到v'的途径顶点的下标不大于k的路径可分为两段,
k = 2 :同理
k: ,
如此继续，直至做完k=n-1的情况。
7.2 算法实现
两类矩阵：A记录路径长度，N记录后继顶点。
·用递推的方式生成一系列n*n方阵（0<=k<=n)，其中表示从vi到vj的途径顶点下标小于k的最短路径的长度。此处需要注意一下下标的对应关系：下标为0，表示不经过任何路径；下标为1，表示只能经过v0；下标为k，表示能经过v0，...，vk-1。k最大为n，因为n个顶点的编号从0到n-1。
·主要公式：
·有一处需要注意的点：根据严密的推导，可以证明，计算的过程中不会修改矩阵第k行或第k列的元素，因此可以直接只用一个表实现所有的。
·记录后继顶点，的值是从vi到vj的中间可经过顶点下标小于k的最短路径上，顶点vi的后继顶点vl的下标。
初始时，若i到j没有边，则令矩阵元素为-1，否则就令元素为j，表示vi的后继顶点是vj。
迭代计算A时，若新路径取代旧路径，则设置 ，表示在vi到vj的路径上vi的后继顶点，就是已知的vi到vk的路径上vi的后继顶点。
完整的算法如下：
def Floyd(graph):
vnum = graph.vertex_num()
a = [[graph.get_edge(i, j) for j in range(vnum)]
for i in range(vnum)] # create a copy the adjacent matrix
nvertex = [[-1 if a[i][j] == infinity else j
for j in range(vnum)]
for i in range(vnum)]
for k in range(vnum):
for i in range(vnum):
for j in range(vnum):
if a[i][j] > a[i][k] + a[k][j]:
a[i][j] = a[i][k] + a[k][j]
nvertex[i][j] = nvertex[i][k]
return (a, nvertex)
八、AOV网、拓扑排序与关键路径
8.1 拓扑排序算法
一个AOV网存在拓扑序列，当且仅当它不包含回路。
任何无回路AOV网N都可以做出拓扑序列，方法如下：
·从N中选择一个入度为0的顶点作为序列的下一顶点
·从N网中删除刚刚所选顶点及其所有的出边
·反复执行上面两步操作，直到已经选出图中的所有顶点，或者再也找不到入度为0的点。
如何寻找以及更新入度为0的点？
解决方法——用一个表indegree构造一个“栈”。用变量zerov记录“第一个”入度为0的顶点的下标，用indegree[zerov]记录下一个入度为0的顶点的下标，以此类推，设最后一个入度为0的顶点下标为v，则在indegree[v]中存入-1.
v入栈：indegree[v] = zerov zerov = v
v'出栈：v' = zerov zerov = indegree[zerov]
算法的基本工作过程：
·初始时，确定所有顶点的入度并存入indegree
·反复选择入度为0的顶点并维护0度表indegree
·返回拓扑序列，若失败则返回false
完整的算法如下：
def toposort(graph):
vnum = graph.vertex_num()
indegree = [0]*vnum
toposeq = []
zerov = -1
for vi in range(vnum):
for v, w in graph.out_edges(vi): indegree[v] += 1
for vi in range(vnum):
if indegree[vi] == 0:
indegree[vi] = zerov; zerov = vi
for n in range(vnum):
if zerov == -1: return False # Thereis no topo-seq
toposeq.append(zerov)
vi = zerov; zerov = indegree[zerov]
for v, w in graph.out_edges(vi):
indegree[v] -= 1
if indegree[v] == 0:
indegree[v] = zerov; zerov = v
return toposeq
8.2 关键路径算法
事件vj的最早可能发生时间ee[j]
)|
事件vi的最迟允许发生时间le[i]
)|
活动ak的最早可能开始时间e[k]=ee[i]，最迟允许开始时间 l [k] = le[j]-w(
当e[k] = l[k]，则称事件ak为关键活动。所有完全由关键活动构成的从初始点到终点的路径就是关键路径。关键路径可能不止一条，可以同时得到。
为生成正确的ee和le数据，计算需要按一定的顺序。对于ee，应按照拓扑顺序；对于le，应按照逆拓扑顺序。
综上，算法实现分为下面几步：
·生成拓扑序列
·生成ee表的值
·生成le表的值
·计算e和l，直接求出关键活动
完整的算法如下：
def criticalPath(graph):
toposeq = toposort(graph)
if toposeq == False:
return False # no topo-sequence, cannot continue
vnum = graph.vertex_num()
ee, le = [0]*vnum, [infinity]*vnum
crtPath = []
setEventE(vnum, graph, toposeq, ee)
setEventL(vnum, graph, toposeq, ee[vnum-1], le)
for i in range(vnum):
for j, w in graph.out_edges(i):
if ee[i] == le[j] - w: # a critical action
crtPath.append([i, j, ee[i]])
return crtPath # return the critical actions
def setEventE(vnum, graph, toposeq, ee):
for k in range(vnum-1):
i = toposeq[k]
for j, w in graph.out_edges(i):
if ee[i] + w > ee[j]:
ee[j] = ee[i] + w
def setEventL(vnum, graph, toposeq, eelast, le):
for i in range(vnum): le[i] = eelast
for k in range(vnum-2, -1, -1):
i = toposeq[k]
for j, w in graph.out_edges(i):
if le[j] - w < le[i]:
le[i] = le[j] - w
