习题

算法

for each w from 0 to |V| - 1 //初始化标志数组
	flag[w] = false 

for each vertex u in V[G] //对于图G的每个顶点u
	for each v in adj[u] //顶点u的每条出边<u, v>
		for each w in adj[v] //顶点v的每条出边<v, w>
			if flag[w] == false
				flag[w] = true //设置标志
				add edge(u, w) to E2 //添加边<u, w>到图G的平方
	
	//清除标志的时间复杂度与边数相关
	for each v in adj[u]
		for each w in adj[v]
			flag[w] = false //清除标志			
				

总结

计算图G的k次幂可考虑反复平方法