设计流媒体算法来验证有向图是否具有母顶？
我有以下问题：
给定一个定向图G和一个节点。 如何设计流算法来验证s节点是否是母顶顶点？ （母顶顶点是一个顶点，我们可以通过它来达到图的所有其他顶点。）
我需要多少次读取图G的输入以找出答案？
我不知道该如何从这个问题开始。有人可以帮助我吗？
提前致谢！
编辑： 抱歉，没有解释什么是流算法。以下是流算法的描述。
“流算法”是用于处理数据流的算法，其中将输入作为一系列项目呈现，并且只能在几个通过中进行检查（通常只有一个）。在大多数模型中，这些算法都可以访问有限的内存（通常在流中的大小和/或最大值的对数）。他们的处理时间也可能有限。
I have the following question:
Given a directed graph G and a node S.
How can I devise a streaming algorithm to verify whether S node is a mother vertex?
(A Mother Vertex is a vertex through which we can reach all the other vertices of the Graph.)
How many time do I need to read the input of graph G to figure out the answer?
I don't know how to start with this problem.Can someone help me with this?
Thanks in advance!
Edit:
Sorry for not explaining what is a streaming algorithm. The following is the description of streaming algorithm.
"Streaming algorithm" are algorithms for processing data streams in which the input is presented as a sequence of items and can be examined in only a few passes (typically just one). In most models, these algorithms have access to limited memory (generally logarithmic in the size of and/or the maximum value in the stream). They may also have limited processing time per item.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您需要确定是否可以从S。
You need to determine if every vertex is reachable from S. To do this, perform a depth first search and check that every vertex was visited.