2

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

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

4

2 回答 2

7

注意：为简洁起见，我使用“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]

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

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

于 2012-09-19T18:01:01.147 回答
1

为每个节点维护一个哈希表并将其初始化为零。做BFS，当你在哈希表中击中一个与当前顶点增量值相邻的顶点时（即被击中）。上述方法是针对顶点的入度。对于出度做同样的事情（即，当你有节点连接到它时，它的值加一并迭代 (BFS)) 。

于 2012-09-18T06:59:46.323 回答