MHB Explaining Breadth-first-Search Hello! (Thinking)

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The discussion centers on the Breadth-First Search (BFS) algorithm, explaining its mechanics and properties. Key points include the definition of the shortest path, denoted as δ, and how BFS guarantees that the distance d[v] found during the search is at least as long as the shortest path δ(s,v). The participants clarify that the queue structure in BFS maintains layers of vertices at similar distances from the starting vertex, with distance increments limited to one. They also address the possibility of cycles in graphs and the implications for path lengths, confirming that BFS can still yield the shortest path despite multiple routes. Overall, the conversation emphasizes understanding BFS's operational principles and its effectiveness in finding shortest paths in graphs.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Wave)

Given the following algorithm:
Code:
    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:

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)
 
Technology news on Phys.org
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.

evinda said:
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.

evinda said:
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.

evinda said:
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.
 
Evgeny.Makarov said:
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.

Evgeny.Makarov said:
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

Evgeny.Makarov said:
$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?
Evgeny.Makarov said:
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)
 

Attachments

  • path.png
    path.png
    1.4 KB · Views: 107
  • path.png
    path.png
    2 KB · Views: 110
evinda said:
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$.

evinda said:
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.

evinda said:
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.

evinda said:
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.
 
Evgeny.Makarov said:
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)

Evgeny.Makarov said:
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)
 
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.
 

Attachments

  • bfs.png
    bfs.png
    2.6 KB · Views: 99
Evgeny.Makarov said:
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)
 
Back
Top