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

How to erase edge from adjacency list of an undirected graph in O(1) for eular tour?
Автор _Muhammad, история, 5 лет назад, По-английски

Assalamualikum!

For finding eular cycle we need to erase edges from graph. But I don't know how to erase edges in O(1) for undirected graph. I can only erase edges in O(log(n)) using C++ set for adjacency list instead of vector.

But I need to erase edges in O(1) so that my eular cycle finding algorithm will run in O(N) instead of O(Nlog(N)). Please tell me how to do it.

Thanks In Advance.

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

All the times that I had to so something like that I always used vectors, and they always performed better than sets, you can try yourself in local.

g[i].erase(find(g[i].begin(),g[i].end(),val));
→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    But time complexity of find() is up to linear in the distance between first and last compares elements until a match is found. So time complexity will be up to O(n^2) in worst case.

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

Using set is unnecessary. vector can be thought of as a stack (and you can pop stuff off the stack in amortized O(1)). Just iterate through your adjacency list from back to front.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    But how it will work for undirected graph? Here we have to delete both u -> v and v -> u edge.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится

      Give every edge an id so u -> v and v -> u have same id. Then if you encounter an edge id you have already encountered, you can pop it without processing it.

      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just use linked lists or std::list so you can remove edges in $$$O(1)$$$ time. I implemented this kind of adjacency list in my solution to Tanya and Password which requires you to find Eulerian path in a directed graph.

For undirected graphs, there are ways to setup edges so that each edge contains a pointer to the reverse edge, meaning that when you delete one edge, you can also delete the node containing the reverse edge as well.

→ Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Well, you actually don't :)), at least right away. I erase the node (or edge) in a lazy manner. Firstly, in the adjacency list, I also store the edge's ID beside the node. Secondly, I declare a global array removed to mark removed edges. When you remove an edge, just mark it as removed. And then when you try to get the next edge to go to, you just continue to iterate the adjacency list of the current node until you find the unremoved one.

→ Ответить