BandB.c

lowerBound = MST
upperBound = todos os vértices conectados na raiz

G = (V, E)

e[] = sort(E) //as arestas serão usadas para particionar o espaço de soluções

bestSoFar = upperBound(G)
live[] = branch(e.dequeue()) //aqui gera as possibilidade: 1- com p0, 2 - sem p0

while Live not Empty and time < 1hour {
	P = live.dequeue()
	B = branch(P, e.dequeue())
	for i in B {
		LB(i) = lowerBound(i)
		
		if LB(i) == S //is a feasible solution S 
		and S < bestSoFar {
			bestSoFar = S
			continue
		}

		if LB(i) >= bestSoFar {
			stop branching in i
		} else {
			live.enqueue(branch(i))
		}
	}
}
return bestSoFar