打印in-degree和每个顶点的out-degree

Question

我正在努力解决这个算法问题:

我如何编写一个theta(m+n)算法来打印m边,n-顶点有向图中每个顶点的入度和出度,其中有向图用相邻列表表示.

Answer 1

注意:为简洁起见,我使用"O"代替theta.

不需要BFS.

在你的邻居列表由向边的列表的情况下,维护两个顶点计数的映射,一个为度,和一个用于出度.每个顶点应该最初映射到零.然后迭代每个边,u,v并递增out-degree(u)和in-degree(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]

您可以将任何关联映射用于顶点计数映射.如果使用散列映射,您将获得摊销的常量时间操作,并且它将不会影响整个算法的复杂性.但是,如果您知道顶点位于没有间隙的范围内,例如[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.

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