首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >理解我的伪代码图算法的细节

理解我的伪代码图算法的细节
EN

Stack Overflow用户
提问于 2013-11-18 09:26:04
回答 1查看 274关注 0票数 0

下面是我的算法伪代码:

代码语言:javascript
复制
input: a  directed graph G=(V,E)
output: all source nodes of G
function sources(G)
  for all u in V: in[u]=0
  for all u in V:
    for all edges (u,w) in E
    in[w]=in[w]+1

  L = empty linked list
  for all u in V
    if in[u] is 0: add u to L
  return L

我遇到的问题是真正理解这个伪代码,如果它是用c++或java语法编写的,我想我会更容易掌握代码。我理解这段代码背后的逻辑以及它通常是如何工作的,但是我仍然无法理解这段伪代码的细节,特别是inw=inw+1是如何工作的。我知道这段代码表示对索引进行计数并将其存储在in[]数组中,但是如何不断地向inw中添加一个来表示对所有边的探索,从而表示图中的所有节点。有人能用通俗易懂的语言解释一下这个伪代码从第一个for循环开始到inw=inw+1的第4-7行吗?还有,我应该如何考虑u和w,u是整个图的源节点,还是它只表示一个非特定节点,它位于我们应该遍历的另一个非特定节点(w)之前,以便处理整个图?

EN

回答 1

Stack Overflow用户

发布于 2013-11-18 09:39:14

代码语言:javascript
复制
Line 1 - Specify your input
Line 2 - Specify your output
Line 3 - define a function that takes G
Line 4 - set the array in to have all zero values for the number of vertices
Lines 5-7 - This looks like it's counting the number of times an edge goes TO a vertice.
Line 8 - empty
Line 9 - Initialize an empty linked list
Line 10-11 - for all vertices, if you don't have an an inbound node (since you're in in[u]) add you to the linked list L. 
Line 12 - return the linked list L.

我认为这段psuedo-code所做的是尝试返回一个链表,其中包含所有未接收入站边的节点。然而,我对此并不乐观。你有没有更多的上下文(比如一本书,页码,或者它的URL?)

祝好运!

-Brian J. Stinar

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/20038569

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档