Proof of BFS Algorithm
- From: berndlosert@xxxxxxxxxxxx
- Date: 30 Jun 2005 07:37:24 -0700
I've been given the following algorithm for breadth-first search that
contructs a spanning tree:
1. procedure bfs(V, E)
2. // V = vertices ordered v[1], ... v[n]; E = edges
3. // V' = vertices of spanning tree T; E'= edges of spanning tree T
4. // v[1] is the root of the spanning tree
5. // S is an ordered list
6. S := (v[1])
7. V' := {v[1]}
8. E' := null
9. while true do
10. begin
11. for each x in S, in order, do
12. for each y in V - V', in order, do
13. if (x, y) is an edge then
14. add edge (x, y) to E' and y to V'
15. if no edges were added then
16. return T
17. S := children of S ordered consistently with the
18. original vertex ordering
19. end
20. end bfs
I'm supposed to prove that this algorithm correctly contructs a
spanning tree. Here are my thoughts:
I'm going to prove this by contradiction. Let G be a connected graph.
Suppose bfs(G) generates not a spanning tree but either: (1) a tree
that doesn't span all vertices or (2) something else that is not a tree
at all.
Case (1) - If bfs generated a tree that didn't span all vertices, that
means that the algorithm skipped a vertex in step 17. But this can't be
since S will always contain the children of the vertices in S from the
previous iteration and since it starts with v[1], the algorithm
effectively goes through each vertex.
Case (2) - If the algorithm didn't generate a tree, then the result
contains a cycle. This is only possible if in step 14, the edge (x,y)
was added to E' for a y that was already in V' but this is impossible
because in step 12, the loop considers only the vertices in V - V'.
Will these arguments suffice?
.
- Prev by Date: Re: ZFC
- Next by Date: Re: Disjoint circle merge NP complete for L^n error?
- Previous by thread: Call for Participation: Unconventional Computing 2005
- Index(es):
Relevant Pages
|
