一、广度优先搜索
什么是广度优先搜索？ 在给定图G=（V,E)后和一个特定的源顶点s的情况下，广度优先搜索，系统的探索G中的边，以期发现从s可以到达的所有顶点，并计算s到所有这些可达顶点之间的距离（即最少的边数） 广度优先搜索的作用？个人从定义理解就是，计算出s可以到达的所有顶点，并且计算出到这些顶点的距离（最短路径上的边数，如果边没有权重，这个结果将更有意义）。另一方面，通过广度优先搜索，我们可以判断一个无向图是否是连通图。 广度优先搜索算法： 1、算法导论书上实现BFS算法，本人用python实现。 代码介绍：类G是图的邻接表表示方式，这里是一个有向图，有10个顶点，G的vector数组存储每个顶点可出发的边。BFS函数：color数组存储每个顶点的颜色，parent数组存储每个顶点的父母，distance存储s到该顶点的距离，不可达填None 代码改进：这里可以BFS算法走完后，我们可以通过parent数组打印出，顶点到s的最短路径（可能有多个，在这里我们只能打印出一条，这是一个局限）。 算法分析： 运行时间O(V+E)V是顶点数，E是边数 额外存储 3*vclass G:
number = 10
vector=[]
time = 0 def __init__(self): for n in range( 0,self.number): print n self.vector.append( [n*2%10,0]) returndef BFS(G1,s): color = [] parent = [] distance = [] for n in range(0,G1.number): color.append("white") parent.append(None) distance.append(None) color[s] = "gray" parent[s] = None distance[s] = 0
que = []（注意这边使用数组做的一个队列：先进先出） que.append(s) while len(que) != 0: u = que[0] que = que[1:] for item in G1.vector[u]: if color[item] == "white": color[item] = "gray" distance[item]= distance[u] + 1 parent[item] = u que.append(item) color[u] = "black" print distance returna1 = G()BFS(a1,1)
2、算法导论习题：如果把迷宫看成一个连通的无向图，设计一条路径，走出迷宫？（各位大虾指教）
二、深度优先搜索
什么是深度优先搜索？简述：对每个可能的分支路径深入到不能再深入为止。 算法导论上定义：在深度优先搜索中，对于新发现的顶点，如果他还有以此为起点的而未探测到的边，就沿此边继续搜索下去。当顶点v的所有边都被探索过后，搜索将回朔到发现丁v有起始点的边。这一过程一直进行下去，知道发现从源顶点可达的所有顶点为止。 深度优先搜索的作用？1、深度优先搜索可以进行拓扑排序。 （拓扑排序对有向图意义比较大）2、可以判断一个有向无回图是否有回路 3、对边分类成 树边、反向边、正向边、交叉边（如果一个有向图有反向边，则该图有回路） 1、算法导论的 深度优先搜索算法：代码介绍：类G通过邻接表方式标示图（详见上面定义），数组color存储节点颜色，表示节点状态；数组parent存储节点的父母；数组d存储节点的发现时间（发现节点为白色）；数组f存储节点搜索结束时间（节点颜色变为黑色）。
代码改进：通过d、v两个数组，我们能够对G进行拓扑排序
算法分析：
O(v+E)
额外存储：4*V
def DFS(G1):
color = []
parent = []
d = []
f = []
for i in range(0,G1.number):
color.append("white")
parent.append(None)
d.append(-1)
f.append(-1)
for n in range (0,G1.number):
if color[n] == "white":
DFS_vist(G1,n,d,f,color,parent)
print d
print f
return
def DFS_vist(G1,n,d,f,color,parent):
color[n] = "gray"
G1.time = G1.time + 1
d[n] = G1.time
for v in G1.vector[n]:
if color[v] == "white":
parent[v] = n
DFS_vist(G1,v,d,f,color,parent)
color[n] = "black"
G1.time = G1.time + 1
f[n] = G1.time
return
a2 = G()
DFS(a2)
2、习题：不采用递归实现DFS算法（可参考广度优先搜索） 本人实现方法：
def DFS_2(G1):
G1.time = 0
color = []
parent = []
d = []
stack = []
f = []
for i in range(0,G1.number):
color.append("white")
parent.append(None)
d.append(-1)
f.append(-1)
stack.append(i)
while len(stack) > 0:
u = stack.pop()
vNext = None
if color[u] != "black":
for v in G1.vector[u]:
if color[v] == "white":
vNext = v
break;
else:
continue
if color[u] == "white":
G1.time = G1.time + 1
d[u] = G1.time
color[u] = "gray"
elif color[u] == "gray" and vNext == None:
G1.time = G1.time + 1
f[u] = G1.time
color[u] = "black"
if vNext != None:
color[vNext] = "gray"
G1.time = G1.time + 1
d[vNext] = G1.time
stack.append(u)
stack.append(vNext)
print d
print f
return
3、习题：如何证明一个有向图是单连通，即存在一条唯一的简单路径（路径上的顶点不重复），该路径经过所有顶点 。 一种假设解决方法：求出图存在的所有拓扑排序，找出相邻点之间有边（方向前指后）的拓扑排序，如果只有一条这种拓扑排序，则证明是单连通，否则不是。
三、拓扑排序
什么是拓扑排序？对有向无回图进行拓扑排序后，如果图G包含边（u，v），那么拓扑排序中u在v的前面 拓扑排序的作用？1、可以表达顶点之间的顺序，如果映射到实际情况中，能反应事物之前的先后顺寻（比如，先穿内衣再穿外套） 1、算法导论给出的拓扑排序算法： 对图进行深度优先搜索 在搜索过程中，如果一个顶点搜索结束（颜色变为black），则将顶点插入结果序列的最前端 最后这个结果序列就是图的拓扑排序 2、习题：另一种拓扑排序算法,重复寻找一个入度为0的顶点，将该顶点、以及所有的出边删除。解释如何来实现这一想法，才能使得它的运行时间为O（v+e）？如果G中包含回路，这个算法运行时会发生什么。 算法分析： 计算顶点入度，计算次数 E（边数） 寻找入读为0，比较次数V（顶点数） while循环内部for循环执行次数：E for循环其他部分：V 所以可以得出时间为O（E+v） 额外存储：3*Vdef top_sort(G1):
#初始化入度表为0 inDegree = [0 for i in range(0,G1.number)]
#计算顶点入度 for n in range(0,G1.number): for v in G1.vector[n]: inDegree[v] = inDegree[v] + 1 print inDegree stack = []
#将入度为0的压入stack for n in range(0,G1.number): if inDegree[n] == 0: stack.append(n) print stack ret = [] while len(stack) != 0: u = stack.pop() ret.append(u) for v in G1.vector[u]: inDegree[v] = inDegree[v] - 1 if inDegree[v] == 0: stack.append(v) print ret