Посещение ребер в графе

Я использую алгоритм DFS и хочу пометить каждое ребро как посещенное,подход будет состоять в том,чтобы искать узел и заменять его некоторым sentinel,но это будет дорого стоить, если я сделаю список смежности для хранения значения, соответствующего посещенному узлу, что увеличит время поиска, матрица будет потреблять много места. каков наилучший алгоритм для этого?

1 ответ

  1. Вам просто нужно поддерживать набор пар вершин. Например, на Java HashMap<Pair<Vertex, Vertex>>. В Python, один Setиз 2-элементных кортежей.

    Посещение ребра происходит при перечислении потомков только что обнаруженной вершины и добавлении их в стек DFS. Если вы используете рекурсивный DFS, то это, как вы делаете рекурсивный вызов на каждом потомке. Вот версия стека:

    dfs(graph)
      visitedVertices = \emptyset
      visitedEdges = \emptyset
      // Try all vertices as search roots
      for each vertex r in graph
        push r onto empty stack
        while notEmpty(stack)
          u = pop stack
          if u not in visitedVertices
            add u to visitedVertices
            foreach v such that u->v is in graph
              add (u,v) to visitedEdges // Visit the edge
              push v on stack 
    

    Сказав это, я не уверен, почему вы хотите сделать это. Правильно реализованный DFS естественно пересекает каждое ребро ровно один раз. Вы можете доказать это себе, посмотрев на алгоритм выше. Посещение (u,v)возможно только в том случае, если uвы никогда не были посещены раньше.

    Возможно, у вас есть какой-то другой поток, который наблюдает за ходом поиска или фактически добавляет другую информацию к краям, когда вы посещаете?