笔试算法题（50）：简介 - 广度优先 & 深度优先 & 最小生成树算法

 1 //BFS只能非递归实现，将queue替换成stack之后就是DFS
 2 procedure BFS(G,v):
 3    create a queue Q
 4    enqueue v onto Q
 5    mark v
 6    while Q is not empty:
 7       t ← Q.dequeue()
 8       if t is what we are looking for:
 9          return t
10       for all edges e in G.incidentEdges(t) do //遍历所有与t直接相连的边e
11          o ← G.opposite(t,e) //通过边e与t相连的顶点o
12          if o is not marked:
13             mark o
14             enqueue o onto Q
15 
16 //DFS递归实现
17 procedure DFS(G,v):
18    label v as explored
19    for all edges e in G.incidentEdges(v) do
20       if edge e is unexplored then
21          w ← G.opposite(v,e)
22          if vertex w is unexplored then
23             label e as a discovery edge
24             recursively call DFS(G,w) //递归调用没有访问的顶点w
25          else
26             label e as a back edge

 1 MST-PRIM(G,w,r)
 2    Q←V[G] //将G的所有节点记录到Q
 3    for 每个包含于Q的u
 4       do key[u]←∞ //初始化每个节点的key，表示到根节点r的最短距离
 5    key[r]←0 //处理根节点
 6    p[r]←NIL
 7    while Q≠空集
 8       do u←EXTRACT-MIN(Q) //根据节点的key值选取一个最小的节点
 9          for 每个包含于Adj[u]的节点v
10             do if v包含于Q and w(u,v)<key[v]
11                then p[v]←u
12                   key[v]←w(u,v) //使用节点间的距离赋值节点v的最短距离