2

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

解决方案：

寻找有向图的来源。我们将保留一个数组 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 到底是什么意思？我认为这意味着它计算每个节点的入度，但是我无法想象它到底是怎么做的，有人可以帮我想象一下这个方面吗

4

1 回答 1

4

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

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

考虑一个简单的图表：

a ---> b

邻接表表示为：

a: {b}
b: {}

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

对于a，它将在边缘上循环(a,b)并增加b的计数。

对于b，没有边。

Nowa的计数仍然为零，因此它是源顶点。

于 2013-11-01T08:21:55.833 回答