Explaining Breadth-first-Search Hello! (Thinking)

[evinda]

Hello! (Wave)

Given the following algorithm:

    Breadthfirstsearch(G,s)
    for each u ∈ V \ {s}
         color[u]<-white
         d[u]<-oo
         p[u]<-Ø
    color[s]<-gray
    d[s]<-0
    p[s]<-Ø
    Q<-Ø 
    Insert(Q,s)
    while Q ≠ Ø
           u<-Del(Q)
           for each v  ∈ Adj(u)
              if color[v]=white then
                 color[v]<-gray
                 d[v]=d[u]+1
                 p[v]<-u
                 Insert(Q,v)
    
           color[u]<-black

and this definition:

Spoiler

With $\delta (s,v)$ we symbolize the length of the shortest path from vertex $s$ to vertex $u$.If $v$ is not accessible from $s$,we set $\delta (s,v)=+\infty$.

there are the following sentences:

• For each edge $(u,v) \in E$, $\delta (s,v) \leq \delta (s,u)+1$
  $$$$
  
• At the end of the bread-first search, $d[v] \geq \delta (s,v), \forall v \in V $.
  $$$$
• Suppose that during the implementation of the breadth-first-search,the queue $Q$ contains the vertices $v_1,v_2, \dots ,v_r$ ,where $v_1$ is the head of the queue.Then:
  $$d[v_r] \leq d[v_1]+1 \ \text{ and } \ d[v_i] \leq d[v_{i+1}],i=1,2, \dots ,r-1$$

Could you explain me the above sentences? (Thinking)

 

[Evgeny.Makarov]

A lot can be written about this, but appropriate help depends on what you understand. Please write whether you understand the algorithm and are able to simulate its work, for example, on the graph shown http://web.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch14.html#QQ1-46-92. Do you know how a queue works? I had to look up which side of the queue is called "the head": see, for example, here, though it also has to be described in your textbook.

For each edge $(u,v) \in E$, $\delta (s,v) \leq \delta (s,u)+1$

Do you understand what $\delta$ is? Do you know what the "shortest path" means? If you know the relevant concepts, the answer should be obvious.

At the end of the bread-first search, $d[v] \geq \delta (s,v), \forall v \in V $.

$d[v]$ denotes the length of the path between $s$ and $v$ along which the vertex $v$ was found. Of course, it is not shorter than the shortest path.

Suppose that during the implementation of the breadth-first-search,the queue $Q$ contains the vertices $v_1,v_2, \dots ,v_r$ ,where $v_1$ is the head of the queue.Then:
$$d[v_r] \leq d[v_1]+1 \ \text{ and } \ d[v_i] \leq d[v_{i+1}],i=1,2, \dots ,r-1$$

This property justifies the name "breadth-first". It says that for different vertices $v$ in the queue, the length of the path from $v$ to $s$ along which $v$ was found differs at most by 1. That is, vertices in the queue form a single "layer" of the graph and are at approximately the same distance from the starting vertex. More can be said, but I'll wait for you to describe exactly what you understand.

P.S.

Hint 1: In a typed text, every period and comma must be followed by a space.

Hint 2: The tag [SPOILER] ("spoiler") is primarily for solutions that you want to hide from others.

 

[evinda]

A lot can be written about this, but appropriate help depends on what you understand. Please write whether you understand the algorithm and are able to simulate its work, for example, on the graph shown http://web.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch14.html#QQ1-46-92. Do you know how a queue works? I had to look up which side of the queue is called "the head": see, for example, here, though it also has to be described in your textbook.

I have understood the algorithm and I have seen an example,where it is applied.

Do you understand what $\delta$ is? Do you know what the "shortest path" means? If you know the relevant concepts, the answer should be obvious.

I have understood that $\delta(s,v)$ is the shortest path from the vertex $u$ to the vertex $v$ and $\delta(s,u)$ is the shortest path from the vertex $s$ to the vertex $u$..But..can we only have a graph like the following:

View attachment 3061

or is it also possible that there are,for example, two or more ways from $s$ to $v$ and therefore,that we have cycles? (Thinking)

For example,could we have something like that?

View attachment 3062

$d[v]$ denotes the length of the path between $s$ and $v$ along which the vertex $v$ was found. Of course, it is not shorter than the shortest path.

Applying the breadth-first search,don't we get with $d[v]$ again the shortest path from the vertex $s$ to the vertex $v$? Or am I wrong?

This property justifies the name "breadth-first". It says that for different vertices $v$ in the queue, the length of the path from $v$ to $s$ along which $v$ was found differs at most by 1. That is, vertices in the queue form a single "layer" of the graph and are at approximately the same distance from the starting vertex.

I am confused about this. (Speechless) Could you explain it further to me? (Blush)

 

[Evgeny.Makarov]

can we only have a graph like the following:

View attachment 3061

or is it also possible that there are,for example, two or more ways from $s$ to $v$ and therefore,that we have cycles?

Yes, we can have such graph. Note that $\delta(s,v)=3$ and $\delta(s,u)=2$, so $\delta(s,v)\le\delta(s,u)+1$, as required. It does not matter if there are one or several paths from $s$ to $v$.

For example,could we have something like that?

View attachment 3062

Yes, this graph is also possible. Here $\delta(s,v)=2$ and $\delta(s,u)=2$, so again $\delta(s,v)\le\delta(s,u)+1$. In general, $\delta(s,u)=n$ means, in particular, that there exists a path $p$ from $s$ to $u$ of length $n$. Also, the condition $(u,v) \in E$ means that there is an edge from $u$ to $v$. If we add $v$ to $p$, we get a path of length $n+1$ from $s$ to $v$. Now, this new path may not be the shortest one, as in your second example, but in any case the shortest path from $s$ to $v$ must not be longer than $n+1$ (the length of some path).

To be pedantic, we need to check whether the definition of a path allows repeated vertices. Wikipedia says that most authors require that all vertices in a path must be distinct. Vertices can be repeated in a walk, which is a more general concept. If so, then adding $v$ to $p$ above may not produce a path if $v$ is already present in $p$. However, then the shortest path from $s$ to $v$ does not exceed $n$, so $\delta(s,v)\le n+1$ holds.

Applying the breadth-first search,don't we get with $d[v]$ again the shortest path from the vertex $s$ to the vertex $v$?

You are right. What I said is a weaker statement and is also right.

I am confused about this.

If the queue is $v_1,\dots,v_r$ (the left end is the head from where items are dequeued, and the right end is the tail to where new items are enqueued), then statement 3 says that there exists an $n$ such that either $(d[v_1],\dots,d[v_r])=(n,\dots,n)$ or $(d[v_1],\dots,d[v_r])=(n,\dots,n,n+1,\dots,n+1)$. Thus, $v_1,\dots,v_r$ is a "layer" of vertices at about the same distance from $s$. Depth-first search works as if edges of the graph were pipes and we poured water into $s$. Suppose that water passes one pipe (edge) per second. Then $n$ seconds later water will reach the vertices that form the queue at some point.

To prove statement 3, show that it is an invariant. That is, show that if it holds before each queue operation, then it holds after it as well.

 

[evinda]

Yes, we can have such graph. Note that $\delta(s,v)=3$ and $\delta(s,u)=2$, so $\delta(s,v)\le\delta(s,u)+1$, as required. It does not matter if there are one or several paths from $s$ to $v$.

Yes, this graph is also possible. Here $\delta(s,v)=2$ and $\delta(s,u)=2$, so again $\delta(s,v)\le\delta(s,u)+1$. In general, $\delta(s,u)=n$ means, in particular, that there exists a path $p$ from $s$ to $u$ of length $n$. Also, the condition $(u,v) \in E$ means that there is an edge from $u$ to $v$. If we add $v$ to $p$, we get a path of length $n+1$ from $s$ to $v$. Now, this new path may not be the shortest one, as in your second example, but in any case the shortest path from $s$ to $v$ must not be longer than $n+1$ (the length of some path).

To be pedantic, we need to check whether the definition of a path allows repeated vertices. Wikipedia says that most authors require that all vertices in a path must be distinct. Vertices can be repeated in a walk, which is a more general concept. If so, then adding $v$ to $p$ above may not produce a path if $v$ is already present in $p$. However, then the shortest path from $s$ to $v$ does not exceed $n$, so $\delta(s,v)\le n+1$ holds.

You are right. What I said is a weaker statement and is also right.

I understand! (Nod)

If the queue is $v_1,\dots,v_r$ (the left end is the head from where items are dequeued, and the right end is the tail to where new items are enqueued), then statement 3 says that there exists an $n$ such that either $(d[v_1],\dots,d[v_r])=(n,\dots,n)$ or $(d[v_1],\dots,d[v_r])=(n,\dots,n,n+1,\dots,n+1)$. Thus, $v_1,\dots,v_r$ is a "layer" of vertices at about the same distance from $s$. Depth-first search works as if edges of the graph were pipes and we poured water into $s$. Suppose that water passes one pipe (edge) per second. Then $n$ seconds later water will reach the vertices that form the queue at some point.

To prove statement 3, show that it is an invariant. That is, show that if it holds before each queue operation, then it holds after it as well.

Could you explain it to me,using an example? (Sweating) (Blush)

 

[Evgeny.Makarov]

Consider the following graph.

View attachment 3079

Suppose the initial vertex $s$ is $A$. I will write vertices in the queue together with their corresponding values of $d$, e.g., $(A,0)$. Then the states of the queue at the beginning of each iteration of the $\colorbox{LightGray}{$\texttt{while}$}$ loop (i.e., immediately below the line $\colorbox{LightGray}{$\texttt{while Q ≠ Ø}$}$) are as follows.

\begin{array}{c|llll}
\text{Iteration #} & \text{Queue}\\
\hline
1&(A,0)\\
2&(B,1) & (C,1) & (D,1)\\
3&(C,1) & (D,1) & (E,2)\\
4&(D,1) & (E,2) & (F,2) & (G,2)\\
5&(E,2) & (F,2) & (G,2)\\
6&(F,2) & (G,2)\\
7&(G,2) & (H,3)\\
8&(H,3)
\end{array}

Recall that new items are added to the queue on the right and old items are removed on the left. You can verify that $d[v_i]\le d[v_{i+1}]$ for $i=1,\dots,r-1$ ($r$ is the number of items in the queue), but there is at most one increase by 1, i.e., either $d[v_1]=\dots=d[v_r]$ or $d[v_r]=d[v_1]+1$. This is property 3 in your question. At step 5, for example, the queue contains all vertices that are distance 2 from $A$. The algorithm goes through vertices based on their distance: first through all vertices at distance 1, then through all vertices at distance 2 and so on. This is why it is called breadth-first, and this distinguishes is from depth-first search, which goes to some vertices at arbitrary distance (depth) before exploring some other vertices located at smaller distances.

Now, take into account that if $(u,d)$ is the first element of the queue and is removed by the while loop, then adjacent vertices that are added to the end of the queue during that iteration have the form $(v,d+1)$ for some $v$. Show that if a queue satisfies property 3, then removing a vertex from the head does not break that property, and adding adjacent vertices to the end of the queue does not break it either because of the remark above.

 

[evinda]

Consider the following graph.

View attachment 3079

Suppose the initial vertex $s$ is $A$. I will write vertices in the queue together with their corresponding values of $d$, e.g., $(A,0)$. Then the states of the queue at the beginning of each iteration of the $\colorbox{LightGray}{$\texttt{while}$}$ loop (i.e., immediately below the line $\colorbox{LightGray}{$\texttt{while Q ≠ Ø}$}$) are as follows.

\begin{array}{c|llll}
\text{Iteration #} & \text{Queue}\\
\hline
1&(A,0)\\
2&(B,1) & (C,1) & (D,1)\\
3&(C,1) & (D,1) & (E,2)\\
4&(D,1) & (E,2) & (F,2) & (G,2)\\
5&(E,2) & (F,2) & (G,2)\\
6&(F,2) & (G,2)\\
7&(G,2) & (H,3)\\
8&(H,3)
\end{array}

Recall that new items are added to the queue on the right and old items are removed on the left. You can verify that $d[v_i]\le d[v_{i+1}]$ for $i=1,\dots,r-1$ ($r$ is the number of items in the queue), but there is at most one increase by 1, i.e., either $d[v_1]=\dots=d[v_r]$ or $d[v_r]=d[v_1]+1$. This is property 3 in your question. At step 5, for example, the queue contains all vertices that are distance 2 from $A$. The algorithm goes through vertices based on their distance: first through all vertices at distance 1, then through all vertices at distance 2 and so on. This is why it is called breadth-first, and this distinguishes is from depth-first search, which goes to some vertices at arbitrary distance (depth) before exploring some other vertices located at smaller distances.

Now, take into account that if $(u,d)$ is the first element of the queue and is removed by the while loop, then adjacent vertices that are added to the end of the queue during that iteration have the form $(v,d+1)$ for some $v$. Show that if a queue satisfies property 3, then removing a vertex from the head does not break that property, and adding adjacent vertices to the end of the queue does not break it either because of the remark above.

I got it now! (Happy) Thank you very much! (Clapping)