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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ The source vertex is a completely arbitrary vertex. $\endgroup$
    – Yuval Filmus
    Commented Sep 22, 2021 at 10:32

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Sep 22, 2021 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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