1
$\begingroup$

In graph theory, a source of a directed graph $D = (V(D), E(D))$ is a vertex of it whose in-degree is zero.

The book CLRS makes these statements:

Given a graph $G = (V, E)$ and a distinguished source vertex $s$, breadth-first search systematically explores the edges of $G$ to “discover” every vertex that is reachable from $s$.

I know this is an amateur question but does source have the same meaning here (at least when the graph is directed) or it's just some word the book uses without any particular reason? Maybe by source it means a root.

$\endgroup$
1
  • 2
    $\begingroup$ The source vertex is a completely arbitrary vertex. $\endgroup$ Sep 22 '21 at 10:32
3
$\begingroup$

In that context source is just a way to give a specific name to the vertex $s$. It makes sense to use that word since it is the vertex from which all shortest-paths computed using BFS emanate.

$\endgroup$
1
  • $\begingroup$ @YuvalFilmus Another thing I noticed is that if the graph is directed then at the end of the algorithm we'll get an $s$-branching (an oriented $s$-tree in which the in-degree of every vertex other than the root (s) is zero). So $s$ isn't a source (from a graph-theoretic point of view) in the original directed graph but is indeed a source in the $s$-branching we have found. $\endgroup$
    – Emad
    Sep 22 '21 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.