下面是我的算法伪代码:
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)之前,以便处理整个图?
发布于 2013-11-18 09:39:14
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
https://stackoverflow.com/questions/20038569
复制相似问题