0

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

Суть задачи: Нужно найти такой кратчайший маршрут по графу, что бы он проходил по всем ребрам, в оба направления, сам граф задается списком ребер ( матрицей смежности тоже вариант)

Подскажите алгоритм работы

1
  • Вариант найти путь обхода в одном направлении (пройти по каждому ребру один раз в любую строну), а затем повторить путь в обратном не подходит? Ведь в обеих случаях путь будет кратчайшим, а каждое ребро окажется пройденным два раза.
    – Mark
    10 окт 2018 в 17:19

2 ответа 2

2

Эйлеров путь как раз то. Он проходит по всем рёбрам по одному разу, т.е. короче сделать нельзя.

Надо только модифицировать граф - разделить каждое ребро на две противоположно направленных дуги.

A - B     A    =>  B
|             <=
|         ^ |        
C         | v
           С 

А дальше - алгоритм Хирхольцера, например. В трёх словах его описание

2
  • Т.е. из неориентированого графа сделать ориентированый?
    – BogdanBida
    13 окт 2018 в 16:19
  • Да, именно так.
    – MBo
    13 окт 2018 в 16:34
1

Есть такой вариант с использованием стека. Начинаете идти с любой вершины. Идете по ребрам, которые еще вообще не использованы, в соседние вершины. Каждую вершину закидываете в стек. Когда не можете найти свободное ребро начинаете скидывать со стека (как бы идти назад) и опять проверяете на наличие полностью пустых вершин (ведь наверняка у какой-то вершины до были несколько пустых ребер. В итоге вы обойдете все ребра и ваш стек станет пустым. Вы обошли весь граф. Поздравления и овации.

Код на java, здесь большой класс InputReader для быстрого чтения:

public class TwiceEdgesTraversal {

public static void main(String[] args) {
    InputReader in = new InputReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    Solver solver = new Solver();
    solver.solve(in, out);
    out.close();
}

private static class Solver {

    private List<List<Integer>> g;
    private boolean[][] were;
    private List<Integer> ans;

    private void route(Stack<Integer> st) {
        if (st.empty())
            return;

        int v = st.peek();
        ans.add(v);

        for (int u : g.get(v)) {
            if (!were[v][u] && !were[u][v]) {
                were[v][u] = true;
                st.add(u);
                route(st);
                return;
            }
        }

        st.pop();
        route(st);
    }

    private void solve(InputReader in, PrintWriter out) {
        int n = in.nextInt();
        int m = in.nextInt();

        g = new ArrayList<>();
        for (int i = 0; i <= n; i++)
            g.add(new ArrayList<>());

        were = new boolean[n + 1][n + 1];

        for (int i = 0; i < m; i++) {
            int v = in.nextInt();
            int u = in.nextInt();
            g.get(v).add(u);
            g.get(u).add(v);
        }

        Stack<Integer> st = new Stack<>();
        st.add(1);

        ans = new ArrayList<>();

        route(st);

        out.println(ans.size() - 1);
        for (int v : ans)
            out.println(v);
    }
}

private static class InputReader {
    private BufferedReader br;
    private StringTokenizer st;

    public InputReader(InputStream stream) {
        br = new BufferedReader(new InputStreamReader(stream));
    }

    private int nextInt() {
        return Integer.parseInt(next());
    }

    private long nextLong() {
        return Long.parseLong(next());
    }

    private double nextDouble() {
        return Double.parseDouble(next());
    }

    private String nextLine() {
        String s = "";
        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return s;
    }

    private String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
}
}

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.