BFS: Breadth first search 基本事实 1. BFS(G, s) -Given a graph represented by adjacency- For each vertex u E VIGHsI list, Compute the out-degree and in degree of every vertices 雾 Transpose of a graph 3.ds=0 where E2 is a set of (u, v) such that there exists at least one w in V such that both 4. s=null (u, w) and (w v) are in V. Give an algorithm to compute it 6. Q enqueue(s) BES while(Q=φ For each v∈Adul 日目日回 BFS续] BFS[续 日回 1(②② Q=r,wl Q=v,t,x ①(0② Q=w3 清华大学 宋斌恒 13 基本事实 Given a graph represented by adjacency￾list, Compute the out-degree and in￾degree of every vertices. Transpose of a graph Square of a directed graph: G2=(V,E2), where E2 is a set of (u,v) such that there exists at least one w in V such that both (u,w) and (w,v) are in V. Give an algorithm to compute it. 清华大学 宋斌恒 14 BFS: Breadth first search BFS: Breadth first search 1. BFS(G,s) 1. For each vertex u ∈ V[G]-{s} 1. Color[u]=white 2. d[u]=∞ 3. π [u]=null 2. color[s]=grey 3. d[s]=0 4. π [s]=null 5. Q=φ 6. Q.enqueue(s) 清华大学 宋斌恒 15 BFS 7. while(Q != φ) 1. u=Q.dequeue() 2. For each v ∈ Adj[u] 1. If (color[v] == white) 1. color[v]=gray 2. d[v]=d[u]+1 3. π [v]=u 4. Q.enqueue(v) 3. color[u]=black 清华大学 宋斌恒 16 BFS ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ v w r t u x y s ∞ 0 ∞ ∞ ∞ ∞ ∞ ∞ v w r t u x y s Q={} Q={s} 清华大学 宋斌恒 17 BFS[续] 1 0 ∞ ∞ ∞ 1 ∞ ∞ v w r t u x y s Q={r,w} 1 0 ∞ ∞ 2 1 ∞ ∞ v w r t u x y s Q={w,v} 清华大学 宋斌恒 18 BFS[续] 1 0 2 ∞ 2 1 2 ∞ v w r t u x y s Q={v,t,x} 1 0 2 ∞ 2 1 2 ∞ v w r t u x y s Q={t,x}