Различия

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

Ссылка на это сравнение

java:elective:lesson6 [10/04/2013 17:56] (текущий)
Николай Баженов создано
Строка 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}}.
CC Attribution-Noncommercial 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0