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

Автор ZPetrovich, 9 лет назад, По-русски

Пытаюсь решить задачу. Есть матрица 2000x2000. Хочу представить ее ввиде графа и обходить с BFS/DFS. Есть лимит на время выполнения (2s). Простое создание вершин занимает более 2s! Но мне еще нужно создать Adjacency matrix + пройтись BFS/DFS + какая-то логика решения так что время еще будет увеличено! Вот так создаю вершины:

Map<Integer, Vertex> allVertices = new HashMap<>();

final long b = System.currentTimeMillis();
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < m; j++)
    {
        final int id = i * m + j + 1;
        Vertex v = allVertices.get(id);
        if (v == null)
        {
            v = new Vertex(id);
            allVertices.put(id, v);
        }
    }
}
final long a = System.currentTimeMillis();
final long d = a &mdash; b;
System.out.println(String.format("took <%s> ms", d));

class Vertex
{
    Color color;
    final int id;

    public Vertex(final int id)
    {
        this.id = id;
    }   
}

Нормально ли это использовать ООП для представления больших графов или нужны исключительно массивы?

Полный текст и комментарии »

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