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

Автор Infoshoc, 10 лет назад, перевод, По-русски

Всем привет! Однажды я изучал Эйлеров Цикл и алгоритм его нахождения, но не нашел соответствующей задачи онлайн. Сейчас я решаю другую задачу, в которой поиск Эйлерова цикла только часть задания и хочу проверить мои умения в реализации алгоритма на более простых задачах.

Вопрос: кто-то может мне посоветовать задачу связанную с поиском Эйлерового цикла?

Зарание спасибо.

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

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks! It really helped me! Do you know any other tasks on this topic? It is very strange, that this problem is not tagged with "Eulerian path"!

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

      You may misunderstand the meaning of tags. Eulerian path is too specific to be a tag. In fact, the general algorithm to find Eulerian path is a kind of DFS. So this is tagged with dfs and similar, and graphs certainly.

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

        Yes. You are definitely right. Probably this is the reason why it is so hard for me to find problem of searching Eulerian path...

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

can you give me any link for learning Eulerian path algorithm

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    For me, the most useful one was Wikipedia

    But as far as I understood, in order to use this algorithm, you have to check, if there is Eulerian path (using properties: for undirected graph — the graph should be connected (and probably has vertices without edges) and <= 2 vertices should have odd degree. for directed graph — the graph should be strongly connected, and all vertexes but two has in degree == out degree and two have degrees differ by one for path, and for cycle all vertices should have the same in and out degree.

    And if you are using algo for searching cycle in order to find path, you should add edge and afterwards extract it.

    Prove me someone if I was wrong, please! And tell me if someone using simpler methods?

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится