Семинар 6

Начальные сведения о графах можно найти здесь.

Задание 6.1

Перед началом работы рекомендуется прочитать раздел 23.1.

Приведем одну из возможных реализаций неориентированного графа в виде списков смежных вершин:

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; } }

Пример использования класса UndirectedGraph:

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()); }

Реализуйте алгоритм поиска в ширину, описанный в разделе 23.2.