Блог

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

Представьте график, содержащий направленные и неориентированные ребра, используя List

#java #algorithm #data-structures #graph

Вопрос:

Мне задали этот вопрос в одном из моих интервью в Google. Я не мог этого понять. Если кто-то может помочь, это было бы здорово 🙂

Предоставленный класс был

 class Node{
   int data,
   List<Node> outEdges;
}

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

 List<Integer> encode(Node root){
}

Node decode(List<Integer> graph){
}

Подсказка заключалась в том, что вы можете добавить свои собственные целые числа, если хотите

Комментарии:

1. Что ж, существует множество способов кодирования графика в список. Один из них может заключаться в том, чтобы в основном определить структуру списка, например, вы можете поместить в список пары, которые описывают ребро, например 1,2,2,1,2,3 , может означать такой график 1<->2->3 . Вы также можете добавить 3-е значение, которое в основном является логическим, описывающим, направлено ребро или нет, например, пример графика также может быть возвращен как 1,1,2,0,2,3 . Это может сэкономить место, если неориентированных ребер больше, чем направленных.

2. мы также должны представлять правильное направление между 2 ребрами. Я дал это решение, мы бы поставили 1, если есть прямое ребро, и -1, если его противоположность, и 0 для неориентированного. Но как мы должны пересечь корневой узел? можете ли вы завершить эти методы?

3. Также у нас нет никакой информации об узлах

4. Ну, в случае направленного ребра вы также используете соглашение о том, чтобы сначала поместить исходный узел, а затем целевой узел, например 1,2,3 2->3 1,3,2 , означало бы, что это будет означать, 3->2 но использование 1 и -1 для направления тоже хорошо.

5. Корень можно просто добавить в качестве первого элемента в списке, а также количество узлов. Однако, предполагая, что все узлы должны быть подключены к графику, на самом деле вам это не нужно, просто извлеките эту информацию из декодированного графика.

Ответ №1:

Вы могли бы просто поместить данные и все ребра в список и использовать null в качестве разделителя:

 private class IndexAndEdge {
    public Set<Integer> edges = new HashSet<>();
    public int index;
    public int data;
}

List<Integer> encode(Node root) {
    List<Integer> result = new ArrayList<>();
    Map<Node, IndexAndEdge> lookup = new HashMap<>();
    parse(root, lookup);
    result.add(lookup.size());
    lookup.values().stream()
        .sorted((a, b) -> Integer.compare(a.index, b.index))
        .forEach(iae -> {
            result.add(iae.data);
            result.addAll(iae.edges);
            result.add(null);
        });
    result.remove(result.size() - 1);
    return resu<
}

private int parse(Node node, Map<Node, IndexAndEdge> lookup) {
    if (lookup.containsKey(node))
        return lookup.get(node).index;
    IndexAndEdge iae = new IndexAndEdge();
    iae.index = lookup.size();
    iae.data = node.data;
    lookup.put(node, iae);
    for (Node n : node.outEdges)
        iae.edges.add(parse(n, lookup));
    return iae.index;
}

Node decode(List<Integer> graph) {
    Node[] nodes = new Node[graph.get(0)];
    for (int i = 0; i < nodes.length; i  ) {
        nodes[i] = new Node();
        nodes[i].outEdges = new ArrayList<>();
    }
    int index = 0;
    for (int i = 1; i < graph.size(); i  ) {
        Integer n = graph.get(i);
        if (n == null)
            index  ;
        else if (nodes[index].outEdges.isEmpty())
            nodes[index].data = n;
        else
            nodes[index].outEdges.add(nodes[n]);
    }
    return nodes[0];
}
Метки: , ,