algorithm - 返回有向图的源节点

Question

有向图中的源是没有边进入的节点。给出线性时间算法它将邻接列表格式的有向图作为输入，并输出其所有源。

解决方法:

寻找有向图的来源。我们将保留一个数组 in[u]，其中包含每个节点的入度(入边数)。为一个来源，这个值为零。

function sources(G)
Input: Directed graph G = (V,E)
Output: A list of G's source nodes
for all u ∈ V : in[u] = 0
for all u ∈ V :
    for all edges (u,w) ∈ E:
      in[w] = in[w] + 1

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

关于上面的代码，我特别不明白的是第一个代码块中最内层的 for 循环 in[w] = in[w]+1 到底是什么意思？我认为这意味着它计算每个节点的入度，但我无法想象它到底是怎么做的，有人可以帮我想象一下这方面吗

Answer 1

in[w] = in[w] + 1 增加了进入 w 的边数。

也许一个例子会有所帮助:

考虑一个简单的图表:

a ---> b

邻接表表示为:

a: {b}
b: {}

现在算法将遍历所有顶点。

对于a，它将遍历边(a,b)并增加b的计数。

对于b，没有边。

现在 a 的计数仍然为零，因此它是一个源顶点。