Напишите алгоритм, чтобы найти путь, который пересекает все ребра ориентированного графа G ровно один раз.

Question

... При необходимости вы можете посещать узлы несколько раз. Покажите сложность вашего алгоритма во время выполнения. Этот граф не обязательно сильно связан, но начиная с узла должен существовать такой путь.

До сих пор мой подход состоял в том, чтобы повторно DFS на не посещаемых узлах находить узел с наибольшим номером записи, поскольку это будет частью исходного узла в мета-графе.

Затем неоднократно DFS включается обратный график, чтобы найти мета-граф узла стока.

Затем запускайте алгоритм пути Эйлера, пока мы не исчерпаем все ребра, возвращаясь назад, если путь ведет в тупик.

Я не могу понять, как действовать отсюда.

Привет, я придумал это. Может кто-нибудь, пожалуйста, проверьте это?

function edge_dfs(vertex u, graph, path, num_edges) {

    if num_edges == 0 { // Found a path. 
        return true;
    }


    for all neighbors n of u {

        if exists((u, n)) == true {
            num_edges--
            exists((u, n)) = false
            path.append((n))
            if edge_dfs(n, g, p, num_edges) == true:
                return true
            else:
                num_edges++ // Backtrack if this edge was unsuccessful. 
                exists((u, n)) = true
                path.pop()
        }
    }

    return false // No neighbors or No valid paths from this vertex. 
}


repeatedly do dfs and fine a source component
node: call it s. 

path = array{s}
exists((u, v)) = true for all edges (u, v) in graph
num_edges = number of edges in graph

if edge_dfs(s, graph, path, num_edges) == true:
    Path is the elements in array 'path' in order. 
else:
    Such a path does not exist. 

И это O (| E | + | V |), поскольку это просто DFS всех ребер.