мета-данные страницы
  •  
Загрузка не удалась. Возможно, проблемы с правами доступа?
no way to compare when less than two revisions

Различия

Показаны различия между двумя версиями страницы.


—java:elective:lesson6 [10/04/2013 17:56] (текущий) – создано nbazhenov
Строка 1: Строка 1:
 +====== Семинар 6 ======
  
 +Начальные сведения о графах можно найти {{:java:elective:kormen_p.88-91.pdf|здесь}}.
 +
 +===== Задание 6.1 =====
 +
 +Перед началом работы рекомендуется прочитать {{:java:elective:kormen_p.436-441.pdf|раздел 23.1}}.
 +
 +Приведем одну из возможных реализаций неориентированного графа в виде списков смежных вершин: 
 +
 +<code java>
 +import java.util.ArrayList;
 +import java.util.Collections;
 +import java.util.HashMap;
 +import java.util.List;
 +import java.util.Map;
 +
 +public class UndirectedGraph {
 +
 +    private HashMap<Integer, List<Integer>> verticesMap = new HashMap<Integer, List<Integer>>();
 +
 +    public void addVertex(Integer vertexNumber){
 + if (!hasVertex(vertexNumber)) {
 +            verticesMap.put(vertexNumber, new ArrayList<Integer>());
 +        }
 +    }
 + 
 +    public boolean hasVertex(Integer vertexNumber) {
 +        return verticesMap.containsKey(vertexNumber);
 +    }
 + 
 +    public boolean hasEdge(Integer vertexNumber1, Integer vertexNumber2) {
 +        if (!hasVertex(vertexNumber1)) return false;
 +        List<Integer> edges = verticesMap.get(vertexNumber1);
 +        return Collections.binarySearch(edges, vertexNumber2) >= 0;
 +    }
 + 
 +    public void addEdge(Integer vertexNumber1, Integer vertexNumber2) {
 +        if (!hasVertex(vertexNumber1)) addVertex(vertexNumber1);
 +        if (!hasVertex(vertexNumber2)) addVertex(vertexNumber2);
 +        List<Integer> edges1 = verticesMap.get(vertexNumber1);
 +        List<Integer> edges2 = verticesMap.get(vertexNumber2);
 +        edges1.add(vertexNumber2);
 +        edges2.add(vertexNumber1);
 +        Collections.sort(edges1);
 +        Collections.sort(edges2);
 +    }
 + 
 +    public Map<Integer, List<Integer>> getVerticesMap() {
 +        return verticesMap;
 +    }
 +}
 +</code>
 +
 +Пример использования класса ''UndirectedGraph'':
 +
 +<code java>
 +Random random = new Random();
 +UndirectedGraph graph = new UndirectedGraph();
 +int numberOfVertices = 10;
 +
 +for(int i = 0; i < numberOfVertices; i++) // добавление вершин графа
 + graph.addVertex(new Integer(i));
 +
 +for(int i = 0; i < numberOfVertices; i++)
 + for(int j = i + 1; j < numberOfVertices; j++){ // добавление ребер графа (случайным образом)
 + if(random.nextBoolean())
 + graph.addEdge(new Integer(i), new Integer(j));
 + }
 +
 +Iterator iterator = graph.getVerticesMap().keySet().iterator();
 +Object key;
 +
 +while(iterator.hasNext()){// печать списков смежных вершин
 + key = iterator.next();
 + System.out.println(key.toString() + ": " + graph.getVerticesMap().get(key).toString());
 +}
 +</code>
 +
 +Реализуйте алгоритм поиска в ширину, описанный в {{:java:elective:kormen_p.436-441.pdf|разделе 23.2}}.