6

我想制作一个图形算法来更新/计算节点的值作为相邻节点f(n)的每个值的函数。f(n)

  • 图是有向的。
  • 每个节点都具有初始 f(n) 值。
  • 每条边都没有成本（0）。
  • 每个节点的值是其当前值和每个相邻节点的值的最大值（有向图，因此邻居是节点具有传入边的那些）。

更正式地说，

f(n) = max(f(n),max_i(f(n_i))), where i from neighbor 1 to neighbor k.

我可以想象一些这样做的方法，但是我不知道它们在多大程度上是最佳的。

任何人都可以提供建议和评论（您认为您的建议是否最佳）或建议任何我可以适应的现有图形算法？

4

1 回答 1

6

Claims:

  1. In each Strongly Connected Component V in the graph, the values of all vertices in this SCC have the same final score.
    "Proof" (guideline): by doing propogation in this SCC, you can iteratively set all the scores to the maximal value found in this SCC.

  2. In a DAG, the value of each vertex is max{v,parent(v) | for all parents of v} (definition) and the score can be found within a single iteration from the start to the end.
    "Proof" (guideline): There are no "back edges", so if you know the final values of all parents, you know the final value of each vertex. By induction (base is all sources) - you can get to the fact that a single iteration is enough to determine the final score.

  3. Also, it is known that the graph G' representing the SCC of a graph g is a DAG.

From the above we can derive a simple algorithm:

  1. Fing maximal SCCs in the graphs (can be done with Tarjan algorithm), and create the SCC graph. Let it be G'. Note that G' is a DAG.
  2. For each SCC V: set f'(V) = max{v | v in V} (intuitively - set the value of each SCC as the max value in this SCC).
  3. Topological sort the graph G'.
  4. Do a single traversal according to the topological sort found in (3) - and calculate the f'(V) for each vertex in G' according to its parents.
  5. Set f(v) = f'(V) (where v is in the SCC V)

Complexity:

  1. Tarjan and creating G' is O(V+E)
  2. Finding f' is also linear in the size of the graph - O(V+E)
  3. Topological sort runs in O(V+E)
  4. Single traversal - linear: O(V+E)
  5. Giving final scores: linear!

So the above algorithm is linear in the size of the graph - O(V+E)

于 2012-10-24T16:24:17.223 回答