мета-данные страницы
Загрузка не удалась. Возможно, проблемы с правами доступа?
no way to compare when less than two revisions
Различия
Показаны различия между двумя версиями страницы.
— | java:elective:lesson6 [10/04/2013 17:56] (текущий) – создано nbazhenov | ||
---|---|---|---|
Строка 1: | Строка 1: | ||
+ | ====== Семинар 6 ====== | ||
+ | Начальные сведения о графах можно найти {{: | ||
+ | |||
+ | ===== Задание 6.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< | ||
+ | |||
+ | public void addVertex(Integer vertexNumber){ | ||
+ | if (!hasVertex(vertexNumber)) { | ||
+ | verticesMap.put(vertexNumber, | ||
+ | } | ||
+ | } | ||
+ | |||
+ | public boolean hasVertex(Integer vertexNumber) { | ||
+ | return verticesMap.containsKey(vertexNumber); | ||
+ | } | ||
+ | |||
+ | public boolean hasEdge(Integer vertexNumber1, | ||
+ | if (!hasVertex(vertexNumber1)) return false; | ||
+ | List< | ||
+ | return Collections.binarySearch(edges, | ||
+ | } | ||
+ | |||
+ | public void addEdge(Integer vertexNumber1, | ||
+ | if (!hasVertex(vertexNumber1)) addVertex(vertexNumber1); | ||
+ | if (!hasVertex(vertexNumber2)) addVertex(vertexNumber2); | ||
+ | List< | ||
+ | List< | ||
+ | edges1.add(vertexNumber2); | ||
+ | edges2.add(vertexNumber1); | ||
+ | Collections.sort(edges1); | ||
+ | Collections.sort(edges2); | ||
+ | } | ||
+ | |||
+ | public Map< | ||
+ | return verticesMap; | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Пример использования класса '' | ||
+ | |||
+ | <code java> | ||
+ | Random random = new Random(); | ||
+ | UndirectedGraph graph = new UndirectedGraph(); | ||
+ | int numberOfVertices = 10; | ||
+ | |||
+ | for(int i = 0; i < numberOfVertices; | ||
+ | graph.addVertex(new Integer(i)); | ||
+ | |||
+ | for(int i = 0; i < numberOfVertices; | ||
+ | for(int j = i + 1; j < numberOfVertices; | ||
+ | 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()); | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Реализуйте алгоритм поиска в ширину, |