breadth-first search

<2023-05-30 Tue 01:22:15>
cs


an algorithm that finds the distances from a given vertex to all the other vertices in an unweighted undirected connected graph
the time complexity of is . after the execution of , the algorithm goes once through all the vertices, and twice (in an undirected graph) or once (in a directed graph) through every edge.
the time complexity of is
for each vertex , the values of the variables are changed once at most during the execution of the algorithm.
it follows trivially from the code
let be an undirected graph and let . the -th layer in relation to is the set of vertices whose distance from is equal to .
, here is the set of neighbors of
we denote the -th layer in relation to by or simply when is obviously assumed.
let be an undirected graph and let , during execution, is a sequence of actions which starts with a vertex whose distance from is being removed from and ends when the the last vertex whose distance from is is removed from and all of its neighbors have been scanned.
we denote the -th phase by
starts as get removed from and ends after all its neighbors have been scanned (the first iteration of the outer while loop in the algorithm).
let be a graph, assume is being applied in with the origin . for each vertex , and for each integer and , we define and so on.
  1. the vertex , such that , is in a good state if the following conditions are met:
    • \(d[w]\) is equal to the distance between \(s\) to \(w\), i.e. \(d[w]=\delta(s,w)\)
    • for every vertex \(w \in V - \{s\}\) the sequence of vertices \(p^l[w],\dots,p[w],w\) represents a *minimal* [[blk:1681766020][path]] from \(s\) to \(w\).
  2. the vertex , is in initial state, if ,
right after is done the origin vertex is in good state and the rest of the vertices are in initial state
let be an undirected graph and let be an arbitrary vertex in . let be the farthest vertex from in . let be the distance from to .
for each i, such that , before the start of , the following claims are satisfied:
  1. all the vertices in the levels are out of and theyre in good state.
  2. all the vertices in , and only those vertices, are in and they're in good state.
  3. all the vertices in are out of and are in initial state.
a proof by induction on .
base step: the first claim is true out of lack of candidates ( is an expression that we can safely ignore), the correctness of the second and third claims follows trivially from .
[[blk:1673212044][induction hypothesis]]: we assume that the claims 1,2,3 are all correct at the beginning of and prove the correctness of the claims for
proof of correctness of claim 1:
we need to prove that at the beginning of all the vertices in the levels are out of and all in good state.
  • according to induction hypothesis 1, at the beginning of all the vertices in the levels are out of and in good state.
  • according to induction hypothesis 2, at the beginning of all the vertices in are in and in good state.
  • during all the vertices in are removed from . according to lem-bfs-2, the variables of the vertices in dont change during .
the correctness of claim 1 follows.
proof of correctness of claim 2:
we need to prove that at the beginning of , the following is satisfied:
  1. all the vertices in are in and they're in good state.
  2. in there arent any other vertices left (beside 's).
proof of a:
for every vertex in :
  • according to def-bfs-layer, has atleast a single neighbor in .
  • according to induction hypothesis 3, at the beginning of , is out of and is in initial state.
  • according to induction hypothesis 2, at the beginning of all the vertices in are in and are in good state.
let be the first vertex in out of the neighbors of that are in . during , is removed from and its neighbors are scanned. because is the first neighbor of to be removed from , when the neighbors of are scanned would still be in initial state. when the algorithm scans it executes the following operations:
after those 3 operations are done, becomes would be in good state and is in , from here we can conclude that at the beginning of all the vertices in are in and in good state.
proof of b:
according to induction hypothesis 2, at the beginning of the vertices that are in are the vertices of . according to lem-bfs-2 the only vertices that are supposed to enter during are the vertices that are in initial state at the end of . according to induction hypotheses 1,2 and 3, the vertices that are in initial state at the beginning of are in . according to def-bfs-layer, for each of the vertices in there isnt a neighbor in and therefore none of these vertices enter during .
proof of correctness of claim 3:
we have to prove that at the beginning of all the vertices in are out of and in initial state.
  • according to induction hypothesis 1 at the beginning of all the vertices in are out of and in good state.
  • according to the proof of the second claim, at the beginning of all the vertices in and only those are in .
  • according to induction hypothesis 3 at the beginning of all the vertices in are out of and in initial state.
  • according to the proof of the second claim, during all the vertices in (and only them) are inserted into .
correctness of claim 3 follows.
for each vertex , at the end of :
  2. the edge is the last edge in the minimal path from to .
given the undirected graph , let , we define , write an algorithm that finds
  3. return