algorithm - 打印每个顶点的入度和出度

Question

我正在为这个算法问题苦苦挣扎:

我将如何编写一个 theta(m+n) 算法来打印 m 边 n 顶点有向图中每个顶点的入度和出度，其中有向图使用邻接表表示。

Answer 1

注意:为简洁起见，我使用“O”代替 theta。

不需要 BFS。

如果您的邻接列表包含有向边列表，请维护两个顶点计数映射，一个用于入度，一个用于出度。每个顶点最初应映射到零。然后遍历每条边 u,v 并递增出度 (u) 和入度 (v)。遍历所有边后，您可以遍历每个顶点，并打印其映射结果。遍历每条边是 O(m)，遍历每个顶点(一次初始化映射，一次实际打印它们)是 O(n)。它们的总和是 O(m+n)。

示例代码:

#python-ish, untested

V = set([1,2,3,4,5])
#{(u,v}
E = set([(1,2),(1,3),(2,3)])

in_degree_count = {}
out_degree_count = {}

#initialize the mappings to 0
#O(n)
for u in V:
  in_degree_count[u] = 0
  out_degree_count[u] = 0

#iterate through each edge, incrementing the respective mappings for u,v
#O(m)
for u,v in E:
  out_degree_count[u] += 1
  in_degree_count[v] += 1

#iterate through each vertex to print them
#O(n)
for u in V:
  print 'out_degree({0}):'.format(u), out_degree_count[u]
  print 'in_degree({0}):'.format(u), in_degree_count[u]

您可以为顶点计数映射使用任何关联映射。如果您使用 HashMap ，您将获得摊销的常数时间操作，并且它不会影响整个算法的复杂性。但是，如果您知道顶点在一个没有间隙的范围内，例如 [1,n]，那么您可以使用一个计数数组，索引代表具有它的值的顶点。所以:

in_degrees = [0] * (n + 1) #array/list of zeros, of size n,
                           # index 0 is disregarded since there is no vertex named 0
in_degree[1] = 0 # will mean that vertex `1` has an in-degree of zero.
etc.

这显然为您提供了恒定时间映射操作。