Блог пользователя etal

How would you contract a graph to its SCC's efficiently?
Автор etal, 11 лет назад, По-английски

As you know, given a directed graph there are several algorithms that efficiently divide the graph into Strongly Connected Components. Once you have them you can construct a new graph where each vertex corresponds to a SCC and there is a directed edge from u to v iff there exists an edge that goes from a vertex in SCC u to SCC v. Do you know a way to create the adjacency list of this new graph efficiently stored in a vector<vector>?

The only solution I've come up with is doing a vector<set > G and forall edge (a->b) in the old graph inserting comp[b] in G[comp[a]] and once you've done that copy the set into a vector<vector >.

Thank you!

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Here is an alternative:

fill(mark, false)
for c in components
  for v in c
    for u in original_edges(v)
      if non mark[comp(u)]
        add_comp_edge(c, comp(u))
      mark[comp(u)] = true

  for v in c
    for u in original_edges(v)
      mark[comp(u)] = false
→ Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

O(V+E) code

→ Ответить