Depth-First Search Algorithm Proof Problem I have the solution to the first part

Question

Depth-First Search Algorithm Proof Problem I have the solution to the first part of this problem but i am so confused in understanding it. If someone coud provide an example of some sort with a step by step that would be helpful, and try explaining it in mor clearer terms. Heres the question (its in two parts!): Let v be a vertex in a graph G that is label by the depth-first search algorithm Prove that the algorithm labels ail vertices adjacent to v. Prove that if G is connected the depth-first algorithm labels every vertex of G.

Explanation / Answer

>Clearly DFS(x) is called for a vertex x only if visited(x)==0. The moment it's called, visited(x) is set to
>Therefore the DFS(x) cannot be called more than once for any vertex x. Furthermore, the loop "for all v...DFS(v)" ensures that it will be called for every vertex at least once.
>DFS(v) is called exactly once for each vertex v
>the body of the loop is executed once for all the edges out of v.
>Basic DFS algorithm: Each vertex has a binary field called
"visited(v)". Here's the algorithm in pseudo-code:
for all v in V do visited(v) = 0
for all v in V do if (visited(v)==0) DFS(v)
DFS(v)
{
visited(v) = 1
for all w in adj(v) do if (visited(w)==0) DFS(w)
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.